Statistics for Second order properties of Random graphs

Question

Hi!

Let G(N) be the number of graphs with vertices {1, 2, ..., N} and GN(F) be the number of those of them which satisfy graph property F. There is a beautiful result by Glebskii and Fagin that limit of GN(F)/G(N) can be only 0 or 1 for any first order graph property F. The proof essentialy uses compactness and Vaught's test. So, any first order property is either infinitely likely or infinitely unlikely for large graphs. Moreover, there is an algorithm which, given any first order graph property F as input, decides which of this possibilities holds for F (infinitely likely properties can be axiomatized by complete recursive first order theory).

Questions. What about second order properties? More specificaly, what possibilities can be for probability of second order graph properties? Can we construct for any x from [0, 1] SO property with limit probability exactly x? What is the limit probability for connectedness of graph?

Thanks for any answers and comments.

Answer 1

The limit probability of connectedness is 1. The reason is that a sufficient condition for connectedness is that for any vertices x, y, there exists a vertex z connected to both x and y (i.e. all vertices have path length 2). This is a first-order property. It is easy verify that the probability of this stronger property tends to 1.

Also, note that not only first-order properties have the zero-one law, but also properties in the language where infinite conjunctions and disjunctions are allowed (this would include graph connectivity, for example)

Answer 2

Lots of work has been done on this topic; you might begin by checking the joint papers of Phokion Kolaitis and Moshe Vardi, for example:

Phokion G. Kolaitis, Moshe Y. Vardi: 0-1 Laws and Decision Problems for Fragments of Second-Order Logic Inf. Comput. 87(1/2): 301-337 (1990)

See Kolaitis's web page or http://www.informatik.uni-trier.de/~ley/db/indices/a-tree/k/Kolaitis:Phokion_G=.html

Answer 3

I would guess that if $N$ is vastly larger than $k$ then the number of edges mod $k$ is approximately equally distributed, let us say that $k=\ln(N)$. Could one say that "the number of edges, reduced mod $k$, is less tham $kx$" ?

If so this would give the strongest possible result that if you can describe $x$ in [0,1] then you can obtain it as a limit.

It's a cheap shot, but the number of properties is countable and the number of limits in [0,1] is not, so you can't get all the limits.