When does the zero-one k-law fail?

Zhukovskii, M.; Medvedeva, A.

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 a/ b), where a > 2, the zero-one k-law holds. Moreover, this law does not hold for b = 1 and a ≤ 2 − 2. It is proved that the k-law also fails for b > 1 and a ≤ 2 − ( b 1).

RANDOM graphs; PROBABILITY theory; SUBGRAPHS; GEOMETRIC vertices; EDGES (Geometry)

Mathematical Notes, 2016, Vol 99, Issue 3/4, p362

0001-4346

Academic Journal

10.1134/S0001434616030032