RUS  ENG
Full version
JOURNALS // Matematicheskii Sbornik // Archive

Mat. Sb., 2012 Volume 203, Number 7, Pages 95–128 (Mi sm7698)

This article is cited in 6 papers

A weak zero-one law for sequences of random distance graphs

M. E. Zhukovskii

M. V. Lomonosov Moscow State University, Faculty of Mechanics and Mathematics

Abstract: We study zero-one laws for properties of random distance graphs. Properties written in a first-order language are considered. For $p(N)$ such that $pN^{\alpha}\to\infty$ as $N\to\infty$, and $(1-\nobreak p)N^{\alpha}\to\infty$ as $N\to\infty$ for any $\alpha>0$, we succeed in refuting the law. In this connection, we consider a weak zero-one $j$-law. For this law, we obtain results for random distance graphs which are similar to the assertions concerning the classical zero-one law for random graphs.
Bibliography: 18 titles.

Keywords: zero-one laws, first-order language, random graphs, distance graphs, Ehrenfeucht game.

UDC: 519.179.4

MSC: Primary 05C80; Secondary 03C13, 60F20

Received: 25.02.2010 and 21.08.2011

DOI: 10.4213/sm7698


 English version:
Sbornik: Mathematics, 2012, 203:7, 1012–1044

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025