First-order zero-one law for~the~uniform~model of the random graph

M. E. Zhukovskii ; N. M. Sveshnikov

Sbornik. Mathematics, Tome 211 (2020) no. 7, pp. 956-966

Résumé

The paper considers the Erdős-Rényi random graph in the uniform model $G(n,m)$, where $m=m(n)$ is a sequence of nonnegative integers such that $m(n)\sim cn^{\alpha}(2-\varepsilon)n^2$ for some $c>0$, $\alpha\in[0,2]$, and $\varepsilon>0$. It is shown that $G(n,m)$ obeys the zero-one law for the first-order language if and only if either $\alpha\in\{0,2\}$, or $\alpha$ is irrational, or $\alpha\in(0,1)$ and $\alpha$ is not a number of the form $1-1/\ell$, $\ell\in\mathbb{N}$. Bibliography: 15 titles.

Détail

Keywords: zero-one law, first-order logic, uniform model of the random graph.