When does the zero-one k-law fail?

Аннотация

The limit probabilities of the first-order properties of a random graph in the Erdős–Rényi model G(n, n^−α), α ∈ (0, 1), are studied. A random graph G(n, n^−α) is said to obey the zero-one k-law if, given any property expressed by a formula of quantifier depth at most k, the probability of this property tends to either 0 or 1. As is known, for α = 1− 1/(2^k−1 + a/b), where a > 2^k−1, the zero-one k-law holds. Moreover, this law does not hold for b = 1 and a ≤ 2^k−1 − 2. It is proved that the k-law also fails for b > 1 and a ≤ 2^k−1 − (b + 1)².