1. On the zero-one 4-law for the Erdős-Rényi random graphs.
- Author
-
Zhukovskii, M.
- Subjects
- *
ZERO-one laws (Probability) , *RANDOM graphs , *INTEGERS , *FIRST-order logic , *PROBABILITY theory , *MATHEMATICAL analysis - 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. Earlier, the author obtained zero-one k-laws for any positive integer k ≥ 3, which describe the behavior of the probabilities of the first-order properties expressed by formulas of quantifier depth bounded by k for α in the interval (0, 1/( k − 2)] and k ≥ 4 in the interval (1 − 1/2, 1). This result is improved for k = 4. Moreover, it is proved that, for any k ≥ 4, the zero-one k-law does not hold at the lower boundary of the interval (1 − 1/2, 1). [ABSTRACT FROM AUTHOR]
- Published
- 2015
- Full Text
- View/download PDF