Geodesic
A weak zero-one law for sequences of random distance graphs
Sbornik. Mathematics, Tome 203 (2012) no. 7, pp. 1012-1044 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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. 
@article{SM_2012_203_7_a4,
     author = {M. E. Zhukovskii},
     title = {A weak zero-one law for~sequences of random distance graphs},
     journal = {Sbornik. Mathematics},
     pages = {1012--1044},
     year = {2012},
     volume = {203},
     number = {7},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SM_2012_203_7_a4/}
}
TY  - JOUR
AU  - M. E. Zhukovskii
TI  - A weak zero-one law for sequences of random distance graphs
JO  - Sbornik. Mathematics
PY  - 2012
SP  - 1012
EP  - 1044
VL  - 203
IS  - 7
UR  - http://geodesic.mathdoc.fr/item/SM_2012_203_7_a4/
LA  - en
ID  - SM_2012_203_7_a4
ER  - 
%0 Journal Article
%A M. E. Zhukovskii
%T A weak zero-one law for sequences of random distance graphs
%J Sbornik. Mathematics
%D 2012
%P 1012-1044
%V 203
%N 7
%U http://geodesic.mathdoc.fr/item/SM_2012_203_7_a4/
%G en
%F SM_2012_203_7_a4
M. E. Zhukovskii. A weak zero-one law for sequences of random distance graphs. Sbornik. Mathematics, Tome 203 (2012) no. 7, pp. 1012-1044. http://geodesic.mathdoc.fr/item/SM_2012_203_7_a4/

[1] V. A. Uspenskii, N. K. Vereschagin, V. E. Plisko, Vvodnyi kurs matematicheskoi logiki, Fizmatlit, M., 1997 | Zbl

[2] N. K. Vereschagin, A. Shen, Lektsii po matematicheskoi logike i teorii algoritmov, v. 2, Yazyki i ischisleniya, MTsNMO, M., 2000 | Zbl

[3] A. Ehrenfeucht, “An application of games to the completeness problem for formalized theories”, Fund. Math., 49 (1961), 129–141 | MR | Zbl

[4] Th. Shwentick, “On winning Ehrenfeucht games and monadic NP”, Ann. Pure Appl. Logic, 79:1 (1996), 61–92 | DOI | MR | Zbl

[5] V. F. Kolchin, Random graphs, Cambridge Univ. Press, Cambridge, 2009 | MR | MR | Zbl | Zbl

[6] B. Bollobás, Random graphs, Cambridge Stud. Adv. Math., 73, Cambridge Univ. Press, Cambridge, 2001 | MR | Zbl

[7] N. Alon, J. H. Spencer, The probabilistic method, Wiley-Intersci. Ser. Discrete Math. Optim., Wiley, New York, 2000 | MR | Zbl

[8] Yu. V. Glebskii, D. I. Kogan, M. I. Liogonkii, V. A. Talanov, “Ob'em i dolya vypolnimosti formul uzkogo ischisleniya predikatov”, Kibernetika, 2 (1969), 17–27 | MR | Zbl

[9] R. Fagin, “Probabilities on finite models”, J. Symbolic Logic, 41:1 (1976), 50–58 | DOI | MR | Zbl

[10] S. Shelah, J. Spencer, “Zero-one laws for sparse random graphs”, J. Amer. Math. Soc., 1:1 (1988), 97–115 | DOI | MR | Zbl

[11] M. E. Zhukovskii, “Zero-one laws for first-order formulas with a bounded quantifier depth”, Dokl. Math., 83:1 (2011), 8–11 | DOI | MR | Zbl

[12] A. M. Raigorodskii, “Borsuk's problem and the chromatic numbers of some metric spaces”, Russian Math. Surveys, 56:1 (2001), 103–139 | DOI | MR | Zbl

[13] A. M. Raigorodskii, Lineino-algebraicheskii metod v kombinatorike, MTsNMO, M., 2007

[14] K. A. Mikhailov, A. M. Raigorodskii, “On the Ramsey numbers for complete distance graphs with vertices in $\{0,1\}^n$”, Sb. Math., 200:12 (2009), 1789–1806 | DOI | MR | Zbl

[15] P. Frankl, R. M. Wilson, “Intersection theorems with geometric consequences”, Combinatorica, 1:4 (1981), 357–368 | DOI | MR | Zbl

[16] J. Kahn, G. Kalai, “A counterexample to Borsuk's conjecture”, Bull. Amer. Math. Soc. (N.S.), 29:1 (1993), 60–62 | DOI | MR | Zbl

[17] M. E. Zhukovskii, “The weak zero-one laws for the random distance graphs”, Dokl. Math., 81:1 (2010), 51–54 | DOI | MR | Zbl

[18] M. E. Zhukovskii, “The weak zero-one law for the random distance graphs”, Theory Probab. Appl., 55:2 (2011), 356–360 | DOI | MR | Zbl