|
This article is cited in 6 scientific papers (total 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.
Received: 25.02.2010 and 21.08.2011
Citation:
M. E. Zhukovskii, “A weak zero-one law for sequences of random distance graphs”, Mat. Sb., 203:7 (2012), 95–128; Sb. Math., 203:7 (2012), 1012–1044
Linking options:
https://www.mathnet.ru/eng/sm7698https://doi.org/10.1070/SM2012v203n07ABEH004252 https://www.mathnet.ru/eng/sm/v203/i7/p95
|
Statistics & downloads: |
Abstract page: | 616 | Russian version PDF: | 235 | English version PDF: | 9 | References: | 62 | First page: | 30 |
|