Universal zero-one \(k\)-law (Q325661)

The authors of this paper consider the range of edge-densities in a binomial random graph \(G(n,p)\) for which the 0-1 law holds for the class of properties that can be expressed by first-order formulae. That is, for any property that belongs to this class, the probability that \(G(n,p)\) has it tends either to 0 or to 1 as \(n\to \infty\). This notion can be extended to the so-called 0-1 \(k\)-law, which is related to the class of properties that can be expressed through first-order formulae where the depth of their quantifiers is bounded by \(k\). The theme of this paper is the random graph \(G(n,n^{-\alpha})\) and in particular the existence of critical points for the exponent \(\alpha\). Roughly speaking, those are numbers such that if we choose \(\alpha\) close enough to them a 0-1 \(k\)-law is not satisfied. The paper identifies several intervals which are free from such critical points.