First-order properties of bounded quantifier depth of very sparse random graphs

M. E. Zhukovskii ; L. B. Ostrovskii

Izvestiya. Mathematics , Tome 81 (2017) no. 6, pp. 1155-1167

Résumé

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.

Détail

Keywords: Erdős–Rényi random graph, first-order properties, zero-one law, Ehrenfeucht game.