First-order properties of Erdos-Renyi random graphs

Combinatorics Seminar
Tuesday, December 9, 2014 - 13:35
1 hour (actually 50 minutes)
Skiles 005
MIPT, Moscow, Russia
In the talk, an asymptotic behaviour of first order properties of the Erdos-Renyi random graph G(n,p) will be considered. The random graph obeys the zero-one law if for each first-order property L either its probability tends to 0 or tends to 1. The random graph obeys the zero-one k-law if for each property L which can be expressed by first-order formula with quantifier depth at most k either its probability tends to 0 or tends to 1. Zero-one laws were proved for different classes of functions p=p(n). The class n^{-a} is at the top of interest. In 1988 S. Shelah and J.H. Spencer proved that the random graph G(n,n^{-a}) obeys zero-one law if a is positive and irrational. If a is rational from the interval (0,1], then G(n,n^{-a}) does not obey the zero-one law. I obtain zero-one k-laws for some rational a from (0,1]. For any first-order property L let us consider the set S(L) of a from (0,1) such that a probability of G(n,n^{-a}) to satisfy L does not converges or its limit is not zero or one. Spencer proved that there exists L such that S(L) is infinite. Recently in the joint work with Spencer we obtain new results on a distribution of elements of S(L) and its limit points.