First-order properties of bounded quantifier depth of very sparse random graphs

We say that a random graph obeys the zero-one k-law if every property expressed by a first-order formula with quantifier depth at most k holds with probability tending to 0 or 1. It is known that the random graph G(n, n−α) obeys the zero-one k-law for every k ∈ N and every positive irrational α, as well as for all rational α > 1 which are not of the form 1 + 1/l (for any positive integer l). It is also known that for all other rational positive α, the random graph does not obey the zero-one k-law for sufficiently large k. In this paper we put α = 1 + 1/l and obtain upper and lower bounds for the largest k such that the zero-one k-law holds. © 2017 Russian Academy of Sciences (DoM).