Zero-one k-laws and extended zero-one k-laws for random distance graphs

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 {Gn = (Vn, En)}n=1 be a a sequence of distance graphs and p = p(n) be a function of n. The random distance graph G(Gn,p) is the probabilistic space (ΩGn,FGn,ΡGnρ), where

ΩGn = {G = (V,E) : V = Vn, E ⊆ En},

FGn = 2 ΩGn, FGn,p(G) = p|E|(1-p)|En|-|E|.

We say sequence G(Gn, p) follows zero-one k-law if for any first-order property L with quantier depth at most k the probability PGn ,p(L) of the event "G(Gn ,p) possesses property L" tends either to 0 or to 1 as n → ∞. We say sequence G(Gn, 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 {PGn ,p(L)}n=1 equals either 0 or 1.

We obtain conditions on the sequence {Gn}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;

  • extended zero-one k-law doesn't hold.


[1] 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: 142154,1969. (Russian original: Kibernetica 5, 1727)

[2] S. Shelah, J.H. Spencer, Zero-one laws for sparse random graphs, J. Amer. Math. Soc. 1: 97115, 1988.

[3] M.E. Zhukovskii, On a sequence of random distance graphs subject to the zero-one law, Problems of Information Transmission 47(3): 251-268, 2011. (Russian original: Problemy Peredachi Informatsii, 47(3): 3958, 2011).

[4] S.N. Popova, Zero-one law for random distance graphs with vertices in {-1; 0; 1}n, Problems of Information Transmission 50(1), 2014. (Russian original: Problemy Peredachi Informatsii, 50(1): 79101, 2014).