On the validity of 0-1 law for shallow first order properties of very sparse random graphs

R. R. Shefrukova

Čebyševskij sbornik, Tome 25 (2024) no. 3, pp. 299-334

Résumé

In the binomial random graph $G(n,p)$ edges between every pair of vertices appear independently with probability $p$. The random graph obeys $0$-$1$ $k$-law, if, for every first order sentence, the probability that $G(n,p)$ satisfies it is either $0$ or $1$ in the limit (as $n\to\infty$). This paper addresses the following question: given a small $k$ and any $\ell$, does $G(n,n^{-l-1/\ell})$ satisfy $0$-$1$ $k$-law? We answer this question for $k=3$ and all $\ell$. We also prove that for $k=4$ and $\ell\in[1,40]\cup\{72\}$ $0$-$1$ $k$-law does not hold.

Détail

Keywords: Random graph, first order logic, $0$-$1$ law, quantifier depth, Ehrenfeucht game.
Mots-clés : binomial random graph