We study asymptotical behaviour of the probabilities of first-order properties for Erdös Rényi random graphs G(N; p). It was proved by Y.V. Glebskii, D.I. Kogan, M.I. Liagonkii and V.A. Talanov in 1969 (and independently in 1976 by R. Fagin) that for any first order property L either almost ‘‘all graphs’’ satisfy this property as N tends to infinity or ‘‘almost all’’ graphs don't satisfy the property. In other words, if p doesn't depend on N, then for any first-order property L either the random graph satisfies the property L almost surely or it doesn't satisfy (in such cases the random graph is said to obey zero-one law). We consider the probabilities p = p(N), where p(N) = N-α, N ∈ N, for α∈ (0; 1). The zero-one law for such probabilities was proved by S. Shelah and J.H. Spencer. When α∈ (0; 1) is rational the zero-one law in ordinary sense for these graphs doesn't hold. Let k be a positive integer. Denote by Lk the class of the first-order properties of graphs defined by formulae with quantifier depth bounded by the number k (the sentences are of a finite length). Let us say that the random graph obeys zero-one k-law, if for any first-order property L∈ Lk either the random graph satisfies the property L almost surely or it doesn't satisfy. We consider set Sk = [0,1/(k-2)]∪ [1-(1/2{k-1}),1] and find subsets S¹k and S²k⊂Sk such that for any α∈ S¹k random graph G(N;N-α) obeys zero-one k-law and for any α∈ S²k the random graph doesn't obey zero-one k-law.
The talk is based on two papers: