## We found a match

Your institution may have access to this item. Find your institution then sign in to continue.

- Title
# When does the zero-one k-law fail?

- Authors
## Zhukovskii, M.; Medvedeva, A.

- Abstract
## 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).

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

- Publication
## Mathematical Notes, 2016, Vol 99, Issue 3/4, p362

- ISSN
## 0001-4346

- Publication type
## Academic Journal

- DOI
## 10.1134/S0001434616030032