When does the zero-one k-law fail?


Cite item

Full Text

Open Access Open Access
Restricted Access Access granted
Restricted Access Subscription Access

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

Supplementary Files
Action
1. JATS XML

Copyright (c) 2016 Pleiades Publishing, Ltd.