First-order properties of Erdos-Renyi random graphs
- Series
- Combinatorics Seminar
- Time
- Tuesday, December 9, 2014 - 13:35 for 1 hour (actually 50 minutes)
- Location
- Skiles 005
- Speaker
- Maksim Zhukovskii – 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.