Geodesic
Small subgraphs and their extensions in a random distance graph
Sbornik. Mathematics, Tome 209 (2018) no. 2, pp. 163-186 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

Some statements related to the distribution of small subgraphs in a sequence of random distance graphs are established. A result on the threshold function for the property of containing a fixed strictly balanced graph was proved before, and stronger generalizations of this result are obtained here. Bibliography: 21 titles.
Keywords: distance graph, small subgraphs, extension properties, threshold function, random graph. 
@article{SM_2018_209_2_a1,
     author = {A. V. Burkin and M. E. Zhukovskii},
     title = {Small subgraphs and their extensions in a~random distance graph},
     journal = {Sbornik. Mathematics},
     pages = {163--186},
     year = {2018},
     volume = {209},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SM_2018_209_2_a1/}
}
TY  - JOUR
AU  - A. V. Burkin
AU  - M. E. Zhukovskii
TI  - Small subgraphs and their extensions in a random distance graph
JO  - Sbornik. Mathematics
PY  - 2018
SP  - 163
EP  - 186
VL  - 209
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/SM_2018_209_2_a1/
LA  - en
ID  - SM_2018_209_2_a1
ER  - 
%0 Journal Article
%A A. V. Burkin
%A M. E. Zhukovskii
%T Small subgraphs and their extensions in a random distance graph
%J Sbornik. Mathematics
%D 2018
%P 163-186
%V 209
%N 2
%U http://geodesic.mathdoc.fr/item/SM_2018_209_2_a1/
%G en
%F SM_2018_209_2_a1
A. V. Burkin; M. E. Zhukovskii. Small subgraphs and their extensions in a random distance graph. Sbornik. Mathematics, Tome 209 (2018) no. 2, pp. 163-186. http://geodesic.mathdoc.fr/item/SM_2018_209_2_a1/

[1] P. Erdős, A. Rényi, “On random graphs. I”, Publ. Math. Debrecen, 6 (1959), 290–297 | MR | Zbl

[2] P. Erdős, A. Rényi, “On the evolution of random graphs”, Magyar Tud. Akad. Mat. Kutató Int. Közl., 5 (1960), 17–61 | MR | Zbl

[3] B. Bollobás, “Threshold functions for small subgraphs”, Math. Proc. Cambridge Philos. Soc., 90:2 (1981), 197–206 | DOI | MR | Zbl

[4] A. Ruciński, A. Vince, “Balanced graphs and the problem of subgraphs of random graphs”, Proceedings of the 16th Southeastern international conference on combinatorics, graph theory and computing (Boca Raton, Fla., 1985), Congr. Numer., 49 (1985), 181–190 | MR | Zbl

[5] J. Spencer, “Threshold functions for extension statements”, J. Combin. Theory Ser. A, 53:2 (1990), 286–305 | DOI | MR | Zbl

[6] B. Bollobás, Random graphs, Cambridge Stud. Adv. Math., 73, 2nd ed., Cambridge Univ. Press, Cambridge, 2001, xviii+498 pp. | DOI | MR | Zbl

[7] S. Janson, T. Łuczak, A. Ruciński, Random graphs, Wiley-Intersci. Ser. Discrete Math. Optim., Wiley-Interscience [John Wiley Sons], New York, 2000, xii+333 pp. | DOI | MR | Zbl

[8] A. M. Raigorodskii, Modeli sluchainykh grafov, MTsNMO, M., 2011, 136 pp.

[9] V. F. Kolchin, Random graphs, Encyclopedia Math. Appl., 53, Cambridge Univ. Press, Cambridge, 1999, xii+252 pp. | MR | MR | Zbl | Zbl

[10] N. Alon, J. H. Spencer, The probabilistic method, Wiley-Intersci. Ser. Discrete Math. Optim., 3rd ed., John Wiley Sons, Inc., Hoboken, NJ, 2008, xviii+352 pp. | DOI | MR | Zbl

[11] A. R. Yarmukhametov, “O svyaznosti sluchainykh distantsionnykh grafov spetsialnogo vida”, Chebyshevskii sb., 10:1 (2009), 95–108 | MR

[12] M. E. Zhukovskii, “On the probability of the occurrence of a copy of a fixed graph in a random distance graph”, Math. Notes, 92:6 (2012), 756–766 | DOI | DOI | MR | Zbl

[13] M. E. Zhukovskii, “On a sequence of random distance graphs subject to the zero-one law”, Problems Inform. Transmission, 47:3 (2011), 251–268 | DOI | MR | Zbl

[14] S. N. Popova, “Zero-one law for random distance graphs with vertices in $\{-1,0,1\}^n$”, Problems Inform. Transmission, 50:1 (2014), 57–78 | DOI | MR | Zbl

[15] A. M. Raigorodskii, Lineino-algebraicheskii metod v kombinatorike, MTsNMO, M., 2007, 138 pp. | Zbl

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

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

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

[19] P. Brass, W. O. J. Moser, J. Pach, Research problems in discrete geometry, Springer, New York, 2005, xii+499 pp. | DOI | MR | Zbl

[20] M. E. Zhukovskii, A. M. Raigorodskii, “Random graphs: models and asymptotic characteristics”, Russian Math. Surveys, 70:1 (2015), 33–81 | DOI | DOI | MR | Zbl

[21] M. E. Zhukovskii, “A weak zero-one law for sequences of random distance graphs”, Sb. Math., 203:7 (2012), 1012–1044 | DOI | DOI | MR | Zbl