How Complex are Random Graphs in First Order Logic?

Details How Complex are Random Graphs in First Order Logic? How Complex are Random Graphs in First Order Logic?

2004-01-20

arxiv.org/abs/math/0401247v1

Mathematics

Combinatorics

27 pages

Scientific paper

It is not hard to write a first order formula which is true for a given graph G but is false for any graph not isomorphic to G. The smallest number $(G) of nested quantifiers in a such formula can serve as a measure for the ``first order complexity'' of G. Here, this parameter is studied for random graphs. We determine it asymptotically when the edge probability p is constant; in fact, D(G) is of order log n then. For very sparse graphs its magnitude is \Theta(n). On the other hand, for certain (carefully chosen) values of p the parameter D(G) can drop down to the very slow growing function log^* n, the inverse of the tower-function. The general picture, however, is still a mystery.

Affiliated with

Also associated with

No associations

Rating

How Complex are Random Graphs in First Order Logic? does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with How Complex are Random Graphs in First Order Logic?, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and How Complex are Random Graphs in First Order Logic? will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-392560