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

Аннотация

The paper considers the Erdős-Renyi 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.