When does the zero-one k-law fail?
- Authors: Zhukovskii M.E.1, Medvedeva A.E.2
-
Affiliations:
- Moscow Institute of Physics and Technology
- Derzhavin Tambov State University
- Issue: Vol 99, No 3-4 (2016)
- Pages: 362-367
- Section: Article
- URL: https://journals.rcsi.science/0001-4346/article/view/149199
- DOI: https://doi.org/10.1134/S0001434616030032
- ID: 149199
Cite item
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/(2k−1 + a/b), where a > 2k−1, the zero-one k-law holds. Moreover, this law does not hold for b = 1 and a ≤ 2k−1 − 2. It is proved that the k-law also fails for b > 1 and a ≤ 2k−1 − (b + 1)2.
About the authors
M. E. Zhukovskii
Moscow Institute of Physics and Technology
Author for correspondence.
Email: zhukmax@gmail.com
Russian Federation, Dolgoprudnyi
A. E. Medvedeva
Derzhavin Tambov State University
Email: zhukmax@gmail.com
Russian Federation, Tambov
Supplementary files
