When does the zero-one \(k\)-law fail? (Q325618): Difference between revisions

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 within 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\). It is now a classic result that as long as \(\min \{p, 1-p \} n^{\alpha} \to \infty\) for any \(\alpha >0\), the 0-1 law holds. This condition was weakened to all \(p\) that satisfy \(p=n^{-\alpha}\) but for \(\alpha\) irrational. However, if \(\alpha \in (0,1]\cap \mathbb{Q}\), then \(G(n,n^{-\alpha})\) fails to satisfy the 0-1 law. This notion can be extended to the so-called 0-1 \(k\)-law, which regards the class of properties that can be expressed through first-order formulae where the depth of their quantifiers is bounded by \(k\). The first author showed that for any \(k\geq 3\) and any \(\alpha \in (0, 1/(k-2))\), the random graph \(G(n,p)\) obeys the 0-1 \(k\)-law, whereas this is not the case for \(\alpha = 1/(k-2)\). When \(\alpha\) is close to 1, it has been shown that the 0-1 \(k\)-law holds when \(\alpha = 1 - \frac{1}{2^{k-1} + \beta}\), where \(\beta\) is a rational fraction whose numerator exceeds \(2^{k-1}\). The main result of this paper settles the case where \(\beta = a/b\) with \(a,b \in \mathbb{N}\) and \(a\leq 2^{k-1}\). In fact, it is shown that for \(k\geq 5\) if \(a =1,2,\ldots, 2^{k-1} -(b+1)^2\), then \(G(n,n^{-\alpha})\) does not satisfy the 0-1 \(k\)-law.