show/hide this revision's text 3 deleted 83 characters in body

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?Can we recursively axiomatize infinitely likely SO properties by complete theory?

Thanks for any answers and comments.
show/hide this revision's text 2 added 10 characters in body

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 graphsgraph 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? Can we recursively axiomatize infinitely likely SO properties by complete theory?

Thanks for any answers and comments.
show/hide this revision's text 1

Statistics for Second order properties of Random graphs

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 graphs? 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? Can we recursively axiomatize infinitely likely SO properties by complete theory?

Thanks for any answers and comments.