## Zero-one k-laws for G(n,n^{−α})

We study asymptotical behavior of the probabilities of first-order
properties for Erdős-Rényi random graphs *G(n,p(n))* with
*p(n)=n*^{-α}, *α ∈ (0,1)*. The following zero-one law
was proved in 1988 by S. Shelah and J.H. Spencer [1]: if
*α* is irrational then for any first-order property *L*
either the random graph satisfies the property *L* asymptotically
almost surely or it doesn't satisfy (in such cases the random
graph is said to *obey zero-one law*. When *α ∈ (0,1)*
is rational the zero-one law 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. Since 2010 we prove
several zero-one $k$-laws for rational *α* from
*I*_{k}=(0, 1/(k-2)] ∪ [1-1/(2^{k-1}), 1). For some
points from *I*_{k} we disprove the law. In particular, for
*α* ∈ (0, 1/(k-2)) ∪ *(1-1/2*^{k-2}*, 1)* zero-one
*k*-law holds. If *α* ∈ {1/(k-2), 1-1/(2^{k}-2)},
then zero-one law does not hold (in such cases we call the number
*α* *k*-critical).

We also disprove the law for some
*α* ∈ [2/(k-1), k/(k+1)]. From our results it
follows that zero-one 3-law holds for any *α* ∈ (0,1).
Therefore, there are no *3*-critical points in (0,1). Zero-one
*4*-law holds when *α* ∈ (0,1/2) ∪ (13/14,1). Numbers *1/2*
and *13/14* are *4*-critical. Moreover, we know some rational
*4*-critical and not *4*-critical numbers in *[7/8,13/14)*. The
number *2/3* is *4*-critical. Recently we obtain new results
concerning zero-one *4*-laws for the neighborhood of the number
*2/3*.

**References**

[1] S. Shelah, J.H. Spencer, Zero-one laws for sparse random graphs, J. Amer. Math. Soc.

1: 97–115, 1988.