Abstract:
We say that a random graph obeys the zero-one $k$-law if every property
expressed by a first-order formula with quantifier depth at most $k$
holds with probability tending to $0$ or $1$. It is known that the
random graph $G(n,n^{-\alpha})$ obeys the zero-one $k$-law for every
$k\in\mathbb{N}$ and every positive irrational $\alpha$, as well as for all
rational $\alpha>1$ which are not of the form $1+1/l$ (for any positive
integer $l$). It is also known that for all other rational positive $\alpha$,
the random graph does not obey the zero-one $k$-law for sufficiently large $k$.
In this paper we put $\alpha=1+1/l$ and obtain upper and lower bounds for
the largest $k$ such that the zero-one $k$-law holds.
Keywords:Erdős–Rényi random graph, first-order properties, zero-one law, Ehrenfeucht game.