|
This article is cited in 4 scientific papers (total in 4 papers)
When Does the Zero-One $k$-Law Fail?
M. E. Zhukovskiia, A. E. Medvedevab a Moscow Institute of Physics and Technology (State University), Dolgoprudny, Moscow region
b Tambov State University
Abstract:
The limit probabilities of the first-order properties of a random graph in the Erdős–Rényi model $G(n,n^{-\alpha})$, $\alpha\in(0,1)$, are studied. A random graph $G(n,n^{-\alpha})$ 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 $\alpha=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 \le 2^{k-1}-2$. It is proved that the $k$-law also fails for $b>1$ and $a \le 2^{k-1}-(b+1)^2$.
Keywords:
zero-one $k$-law, Erdős–Rényi random graph, first-order property.
Received: 08.07.2015 Revised: 16.10.2015
Citation:
M. E. Zhukovskii, A. E. Medvedeva, “When Does the Zero-One $k$-Law Fail?”, Mat. Zametki, 99:3 (2016), 342–349; Math. Notes, 99:3 (2016), 362–367
Linking options:
https://www.mathnet.ru/eng/mzm10853https://doi.org/10.4213/mzm10853 https://www.mathnet.ru/eng/mzm/v99/i3/p342
|
Statistics & downloads: |
Abstract page: | 529 | Full-text PDF : | 60 | References: | 89 | First page: | 67 |
|