|
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”, 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: | 624 | Russian version PDF: | 236 | English version PDF: | 17 | References: | 63 | First page: | 30 |
|