ON EMBEDDING RANDOM GRAPHS INTO DISTANCE GRAPHS AND GRAPHS OF DIAMETERS IN EUCLIDEAN SPACES
https://doi.org/10.22405/2226-8383-2015-16-2-133-143
Abstract
the realization of a random graph by geometric graphs in the space Rd. 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 � 3.
Supporting agencies: This work was supported by RFBR grant N 15-01-03530 and grant NSH-2964.2014.1 for support of leading scientific schools.
About the Authors
A. V. Krot
Московский физико-технический институт
Russian Federation
Russian Federation
A. M. Raigorodskii
Московский государственный университет имени М. В. Ломоносова
Russian Federation
Russian Federation
References
1. Sz´ekely, L. A. 2002, "Erd˝os on unit distances and the Szemer´edi–Trotter theorems" , Paul Erd˝os and his Mathematics, Bolyai Series Budapest, J. Bolyai Math. Soc., Springer, vol. 11, pp. 649 – 666.
2. Raigorodskii, A. M. 2014, "Cliques and cycles in distance graphs and graphs of diameters" , Discrete Geometry and Algebraic Combinatorics, AMS, Contemporary Mathematics, vol. 625, pp. 93 – 109.
3. Raigorodskii, A. M. 2013, "Coloring Distance Graphs and Graphs of Diameters" , Thirty Essays on Geometric Graph Theory, J. Pach ed., Springer, P. 429 – 460.
4. Raigorodskii, A. M. 2001, "The Borsuk problem and the chromatic numbers of some metric spaces" , Uspekhi Mat. Nauk, vol. 56, № 1, pp. 107 – 146; English transl. in Russian Math. Surveys, vol. 56, № 1, pp. 103 – 139.
5. Boltyanski, V. G., Martini, H. & Soltan, P. S. 1997, "Excursions into combinatorial geometry" , Universitext, Springer, Berlin.
6. Bollob´as, B. 2001, "Random Graphs" , Cambridge Univ. Press, Second Edition.
7. Kokotkin, A. A. & Raigorodskii, A. M. 2013, "On large subgraphs of a distance graph having small chromatic numbers" , Contemp Math. Fundam. Directions, vol. 51, pp. 64 – 73; English transl. in preparation.
8. Raigorodskii, A. M. & Nagaeva, S. V. 2009, "On the realization of random graphs as distance graphs in spaces of fixed dimension" , Doklady of the Russian Acad. Sci., vol. 424, № 3, pp. 315 – 317; English transl. in Doklady Math., vol. 79, № 1, pp. 63 – 65.
9. Raigorodskii, A. M. 2007, "On a series of Ramsey-type problems in combinatorial geometry" , Doklady of the Russian Acad. Sci., vol. 413, № 2, pp. 171 – 173; English transl. in Doklady Math., vol. 75, № 2, pp. 221 – 223.
10. Kupavskii, A. B. & Titova, M. V. 2013, "Distance Ramsey Numbers" , Doklady of the Russian Acad. Sci., vol. 449, № 3, pp. 267 – 270. English transl. in Doklady Math.
11. Alon, N. & Kupavskii, A. 2014, "Two notions of unit distance graphs" , J. Comb. Theory, Ser. A., vol. 125, pp. 1 – 17.
12. Kupavskiy, A. B., Raigorodskii, A. M. & Titova, M. V. 2013, "New bounds for the distance Ramsey number" , Discrete Mathematics, vol. 313, № 22, pp. 2566 – 2574.
13. Erd˝os, P. 1946, "On sets of distances of n points" , Amer. Math. Monthly, vol. 53, pp. 248 – 250.
14. Raigorodskii, A. M. 2011, "Models of random graphs" , Moscow Centre for Continuous Mathematical Education (MCCME), Moscow, Russia, (book in Russian).
15. Maehara, H., Reiterman, J., R¨odl, V. & Sˇinˇajov´a, E. 1988, "Embedding of trees in Euclidean spaces" , Graphs and Combinatorics, vol. 4, pp. 43 – 47.
16. Schramm, O. 1988, "Illuminating sets of constant width" , Mathematika, vol. 35, pp. 180 – 189.
17. Bourgain, J. & Lindenstrauss, J. 1991, "On covering a set in Rd by balls of the same diameter" , Geometric Aspects of Functional Analysis (J. Lindenstrauss and V. Milman, eds.), Lecture Notes in Math., 1469, Springer-Verlag, Berlin, pp. 138 – 144.
18. Lassak, M. 1982, "An estimate concerning Borsuk’s partition problem" , Bull. Acad. Polon. Sci. Ser. Math., vol. 30, pp. 449 – 451.
Review
For citations:
Krot A.V., Raigorodskii A.M. ON EMBEDDING RANDOM GRAPHS INTO DISTANCE GRAPHS AND GRAPHS OF DIAMETERS IN EUCLIDEAN SPACES. Chebyshevskii Sbornik. 2015;16(2):133-143. (In Russ.) https://doi.org/10.22405/2226-8383-2015-16-2-133-143
Views:
402
Email this article 