Abstract:
Studying zero-one laws for random graphs was initiated by Glebskii Y. et al. in [1]. In this work the authors proved the zero-one law for Erdös-Rényi random graph $G(n,p)$. Later S. Shelah and J. Spencer expanded the class of functions $p(n)$, for which $G(n,p)$ follows the zero-one law (see [2]). Zero-one laws for random distance graphs have been considered for the rst time by M. Zhukovskii (see [3]). In [4] we studied the zero-one law for a more general model of random distance graphs.
Let $\{G_n=(V_n, E_n)\}^{\infty}_{n-1}$ be a a sequence of distance graphs and $p=p(n)$ be a function of $n$. The random distance graph $G(G_n,p)$ is the probabilistic space $(\Omega_{G_n}, F_{G_n}, P_{G_{n}p})$, where
\begin{gather*}
\Omega_{G_n}=\{G=(V,E):V=V_n, E \subseteq E_n\},
\\
F_{G_n}=2^{\Omega_{G_n}}, F_{G_{n,p}}(G)=p^{|E|}(1-p)^{|E_n|-|E|}.
\end{gather*}
We say sequence $G(G_n, p)$ follows zero-one $k$-law if for any first-order property $L$ with quantier depth at most $k$ the probability $P_{G_{n},p}(L)$ of the event "$G(G_n,p)$ possesses property $L$" tends either to $0$ or to $1$ as $n \to \infty$. We say sequence $G(G_n, p)$ follows extended zero-one $k$-law if for any first-order property $L$ with quantier depth at most $k$ any partial limit of the sequence $\{P_{G_{n},p}(L)\}^{\infty}_{n=1}$ equals either $0$ or $1$.
We obtain conditions on the sequence $\{G_n\}^{\infty}_{n=1}$ under which one of the following three mutually exclusive cases occurs:
zero-one k-law holds;
zero-one k-law doesn't hold, but extended zero-one k-law holds;
Y. V. Glebskii, D. I. Kogan, M. I. Liagonkii, V. A. Talanov, “Range and degree of realizability of formulas the restricted predicate calculus”, Cybernetics, 5 (1969), 142154
S. Shelah, J. H. Spencer, “Zero-one laws for sparse random graphs”, J. Amer. Math. Soc., 1 (1988), 97115