Geodesic
On embedding random graphs into distance graphs and graphs of diameters in Euclidean spaces
Čebyševskij sbornik, Tome 16 (2015) no. 2, pp. 133-143.

Voir la notice de l'article provenant de la source Math-Net.Ru

In this paper we consider the problem of finding the probability threshold for the realization of a random graph by geometric graphs in the space ${\mathbb R}^d$. In the case of graphs of diameters we prove asymptotic behavior for the threshold probability on the plane, as well as the exact expression in the case $d \ge 3$. Bibliography: 18 titles.
Keywords: distance graph, diameter graph, random graph. 
@article{CHEB_2015_16_2_a8,
     author = {A. V. Krot and A. M. Raigorodskii},
     title = {On embedding random graphs into distance graphs and graphs of diameters in {Euclidean} spaces},
     journal = {\v{C}eby\v{s}evskij sbornik},
     pages = {133--143},
     publisher = {mathdoc},
     volume = {16},
     number = {2},
     year = {2015},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/CHEB_2015_16_2_a8/}
}
TY  - JOUR
AU  - A. V. Krot
AU  - A. M. Raigorodskii
TI  - On embedding random graphs into distance graphs and graphs of diameters in Euclidean spaces
JO  - Čebyševskij sbornik
PY  - 2015
SP  - 133
EP  - 143
VL  - 16
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/CHEB_2015_16_2_a8/
LA  - ru
ID  - CHEB_2015_16_2_a8
ER  - 
%0 Journal Article
%A A. V. Krot
%A A. M. Raigorodskii
%T On embedding random graphs into distance graphs and graphs of diameters in Euclidean spaces
%J Čebyševskij sbornik
%D 2015
%P 133-143
%V 16
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/CHEB_2015_16_2_a8/
%G ru
%F CHEB_2015_16_2_a8
A. V. Krot; A. M. Raigorodskii. On embedding random graphs into distance graphs and graphs of diameters in Euclidean spaces. Čebyševskij sbornik, Tome 16 (2015) no. 2, pp. 133-143. http://geodesic.mathdoc.fr/item/CHEB_2015_16_2_a8/

[1] L. A. Székely, “Erdős on unit distances and the Szemerédi–Trotter theorems”, Paul Erdős and his Mathematics, Bolyai Series Budapest, J. Bolyai Math. Soc., 11, Springer, 2002, 649–666 | MR | Zbl

[2] A. M. Raigorodskii, “Cliques and cycles in distance graphs and graphs of diameters”, Discrete Geometry and Algebraic Combinatorics, Contemporary Mathematics, 625, AMS, 2014, 93–109 | MR

[3] A. M. Raigorodskii, “Coloring Distance Graphs and Graphs of Diameters”, Thirty Essays on Geometric Graph Theory, ed. J. Pach, Springer, 2013, 429–460 | MR | Zbl

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

[5] V. G. Boltyanski, H. Martini, P. S. Soltan, Excursions into combinatorial geometry, Universitext, Springer, Berlin, 1997 | MR | Zbl

[6] B. Bollobás, Random Graphs, Second Edition, Cambridge Univ. Press, 2001 | MR | Zbl

[7] Kokotkin A. A., Raigorodskii A. M., “On large subgraphs of a distance graph having small chromatic numbers”, Contemp Math. Fundam. Directions, 51 (2013), 64–73 | MR

[8] Raigorodskii A. M., Nagaeva S. V., “On the realization of random graphs as distance graphs in spaces of fixed dimension”, Doklady Math., 79:1 (2009), 63–65 | DOI | MR | Zbl

[9] Raigorodskii A. M., “On a series of Ramsey-type problems in combinatorial geometry”, Doklady Math., 75:2 (2007), 221–223 | DOI | MR | Zbl

[10] Kupavskii A. B., Titova M. V., “Distance Ramsey Numbers”, Doklady of the Russian Acad. Sci., 449:3 (2013), 267–270 | DOI | Zbl

[11] N. Alon, A. Kupavskii, “Two notions of unit distance graphs”, J. Comb. Theory, Ser. A, 125 (2014), 1–17 | DOI | MR | Zbl

[12] A. B. Kupavskiy, A. M. Raigorodskii, M. V. Titova, “New bounds for the distance Ramsey number”, Discrete Mathematics, 313:22 (2013), 2566–2574 | DOI | MR

[13] P. Erdős, “On sets of distances of $n$ points”, Amer. Math. Monthly, 53 (1946), 248–250 | DOI | MR | Zbl

[14] Raigorodskii A. M., Models of random graphs, MCCME, M., 2011 (in Russian)

[15] H. Maehara, J. Reiterman, V. Rödl, E. Šiňajová, “Embedding of trees in Euclidean spaces”, Graphs and Combinatorics, 4 (1988), 43–47 | DOI | MR | Zbl

[16] O. Schramm, “Illuminating sets of constant width”, Mathematika, 35 (1988), 180–189 | DOI | MR | Zbl

[17] J. Bourgain, J. Lindenstrauss, “On covering a set in $ {\mathbb R}^d $ by balls of the same diameter”, Geometric Aspects of Functional Analysis, Lecture Notes in Math., 1469, eds. J. Lindenstrauss, V. Milman, Springer-Verlag, Berlin, 1991, 138–144 | MR

[18] M. Lassak, “An estimate concerning Borsuk's partition problem”, Bull. Acad. Polon. Sci. Ser. Math., 30 (1982), 449–451 | MR | Zbl