Abstract:
We study asymptotical behavior of the probabilities of first-order properties for Erdős–Rényi random graphs $G(n,p(n))$ with p$(n)=n^{-\alpha}$, $\alpha \in (0,1)$. The following zero-one law was proved in 1988 by S. Shelah and J. H. Spencer [1]: if $\alpha$ is irrational then for any first-order property $L$ either the random graph satisfies the property $L$ asymptotically almost surely or it doesn't satisfy (in such cases the random graph is said to obey zero-one law. When $\alpha \in (0,1)$ is rational the zero-one law for these graphs doesn't hold.
Let $k$ be a positive integer. Denote by $L_k$ the class of the first-order properties of graphs defined by formulae with quantifier depth bounded by the number $k$ (the sentences are of a finite length). Let us say that the random graph obey zero-one law, if for any first-order property $L \in L_k$ either the random graph satisfies the property $L$ almost surely or it doesn't satisfy. Since 2010 we prove several zero-one $k$-laws for rational $\alpha$ from $I_k=(0, 1/(k-2)] \cup [1-1/(2^{k-1}), 1)$. For some points from $I_k$ we disprove the law. In particular, for $\alpha \in (0, 1/(k-2)) \cup (1-1/2^{k-2}, 1)$ zero-one $k$-law holds. If $\alpha \in \{1/(k-2), 1-1/2^{k-2}\}$, then zero-one law does not hold (in such cases we call the number $\alpha$$k$-critical).
We also disprove the law for some $\alpha \in [2/(k-1), k/(k+1)]$. From our results it follows that zero-one 3-law holds for any $\alpha \in (0,1)$. Therefore, there are no 3-critical points in $(0,1)$. Zero-one $4$-law holds when $\alpha \in (0,1/2) \cup (13/14,1)$. Numbers $1/2$ and $13/14$ are $4$-critical. Moreover, we know some rational $4$-critical and not $4$-critical numbers in $[7/8,13/14)$. The number $2/3$ is $4$-critical. Recently we obtain new results concerning zero-one $4$-laws for the neighborhood of the number $2/3$.