###
On the zero-one k-law and its extensions

Maksim Zhukovskii

Moscow

#### Abstract.

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 L_{k} 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∈ L_{k} either the random graph satisfies the property L almost surely or it doesn't satisfy. We consider set S_{k} = [0,1/(k-2)]∪ [1-(1/2^{{k-1}}),1] and find subsets S¹_{k} and S²_{k}⊂S_{k} 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:

- M.E. Zhukovskii, Zero-one k-law, Discrete Mathematics, 2012, 312:1670-1688,
- M.E. Zhukovskii, Extension of zero-one k-law, 2013, arXiv:1304.0900.