Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4653182 | European Journal of Combinatorics | 2017 | 16 Pages |
Abstract
The presented paper is devoted to the asymptotical behavior of first-order properties of the Erdős–Rényi random graph. In previous works the zero–one kk-law was proved. This law describes asymptotical behavior of first-order properties which are expressed by formulae with a quantifier depth bounded by kk. The random graph G(N,N−α)G(N,N−α) obeys the law if α∈(0,1/(k−2))α∈(0,1/(k−2)). In this work we find new values of αα, which are close to 1, such that G(N,N−α)G(N,N−α) obeys the zero–one kk-law and, therefore, extend the previous result.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
M.E. Zhukovskii,