First-Order and Monadic Properties of Highly Sparse Random Graphs

Abstract—A random graph is said to obey the (monadic) zero–one k-law if, for any property expressed by a first-order formula (a second-order monadic formula) with a quantifier depth of at most k, the probability of the graph having this property tends to either zero or one. It is well known that the random graph G(n, n^–α) obeys the (monadic) zero–one k-law for any $k \in \mathbb{N}$ and any rational α > 1 other than 1 + 1/m (for any positive integer m). It is also well known that the random graph does not obey both k-laws for the other rational positive α and sufficiently large k. In this paper, we obtain lower and upper bounds on the largest $k$ at which both zero–one k-laws hold for $\alpha = 1 + 1{\text{/}}m$.