chebЧебышевский сборникChebyshevskii Sbornik2226-8383Tula State Lev Tolstoy Pedagogical University10.22405/2226-8383-2015-16-2-133-143cheb-172Research ArticleСтатьиArticleО РЕАЛИЗАЦИИ СЛУЧАЙНЫХ ГРАФОВ ГРАФАМИ РАССТОЯНИЙ И ДИАМЕТРОВ В ЕВКЛИДОВЫХ ПРОСТРАНСТВАХON EMBEDDING RANDOM GRAPHS INTO DISTANCE GRAPHS AND GRAPHS OF DIAMETERS IN EUCLIDEAN SPACESКротА. В.KrotA. V.РайгородскийА. М.RaigorodskiiA. M.Московский физико-технический институтRussian FederationМосковский государственный университет имени М. В. ЛомоносоваRussian Federation201504072016162133143Copyright © Крот А.В., Райгородский А.М., 20162016Крот А.В., Райгородский А.М.Krot A.V., Raigorodskii A.M.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.chebsbornik.ru/jour/article/view/172

В данной работе рассматривается задача об отыскании пороговых вероятностей для реализации случайного графа геометрическим графом в пространстве Rd. В случае графов диаметров доказывается асимптоти­ ка для пороговой вероятности на плоскости, а также точное по порядку выражение для d � 3.

 

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.

 

дистанционный графграф диаметровслучайный графdistance graphdiameter graphrandom graphНастоящая работа выполнена при финансовой поддержке гранта РФФИ N 15-01-03530 и гранта НШ-2964.2014.1 поддержки ведущих научных школThis work was supported by RFBR grant N 15-01-03530 and grant NSH-2964.2014.1 for support of leading scientific schools.ReferencesL. A. Sz´ekely 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. 2002. Vol. 11. P. 649 – 666.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.A. M. Raigorodskii Cliques and cycles in distance graphs and graphs of diameters // “Discrete Geometry and Algebraic Combinatorics”, AMS, Contemporary Mathematics. 2014. Vol. 625. P. 93 – 109.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.A. M. Raigorodskii Coloring Distance Graphs and Graphs of Diameters // Thirty Essays on Geometric Graph Theory, J. Pach ed., Springer. 2013. P. 429 – 460.Raigorodskii, A. M. 2013, "Coloring Distance Graphs and Graphs of Diameters" , Thirty Essays on Geometric Graph Theory, J. Pach ed., Springer, P. 429 – 460.А. М. Райгородский Проблема Борсука и хроматические числа метрических пространств // Успехи мат. наук. 2001. Т. 56, вып. 1. С. 107 – 146.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.V. G. Boltyanski, H. Martini, P. S. Soltan Excursions into combinatorial geometry. Universitext, Springer, Berlin, 1997.Boltyanski, V. G., Martini, H. & Soltan, P. S. 1997, "Excursions into combinatorial geometry" , Universitext, Springer, Berlin.B. Bollob´as Random Graphs. Cambridge Univ. Press, Second Edition. 2001.Bollob´as, B. 2001, "Random Graphs" , Cambridge Univ. Press, Second Edition.А. А. Кокоткин, А. М. Райгородский О больших подграфах графа расстояний, имеющих маленькое хроматическое число // Современная математика. Фундаментальные направления. 2013. Т. 51. С. 64 – 73.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.А. М. Райгородский, С. В. Нагаева О реализации случайных графов графами расстояний в пространствах фиксированной размерности // Доклады РАН. 2009. Т. 424, № 3. С. 315 – 317.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.А. М. Райгородский Об одной серии задач рамсеевского типа в комбинаторной геометрии // Доклады РАН. 2007. Т. 413, № 2. С. 171 – 173.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.А. Б. Купавский, М. В. Титова Дистанционные числа Рамсея // Доклады РАН. 2013. Т. 449, № 3. С. 267 – 270.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.N. Alon, A. Kupavskii Two notions of unit distance graphs // J. Comb. Theory, Ser. A. 2014. Vol. 125. P. 1 – 17.Alon, N. & Kupavskii, A. 2014, "Two notions of unit distance graphs" , J. Comb. Theory, Ser. A., vol. 125, pp. 1 – 17.A. B. Kupavskiy, A. M. Raigorodskii, M. V. Titova New bounds for the distance Ramsey number // Discrete Mathematics. 2013. Vol. 313, № 22. P. 2566 – 2574.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.P. Erd˝os On sets of distances of n points // Amer. Math. Monthly. 1946. Vol. 53. P. 248 – 250.Erd˝os, P. 1946, "On sets of distances of n points" , Amer. Math. Monthly, vol. 53, pp. 248 – 250.А. М. Райгородский Модели случайных графов. М.: МЦНМО. 2011.Raigorodskii, A. M. 2011, "Models of random graphs" , Moscow Centre for Continuous Mathematical Education (MCCME), Moscow, Russia, (book in Russian).H. Maehara, J. Reiterman, V. R¨odl, E. Sˇinˇajov´a Embedding of trees in Euclidean spaces // Graphs and Combinatorics. 1988. Vol. 4. P. 43 – 47.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.O. Schramm Illuminating sets of constant width // Mathematika. 1988. Vol. 35. P. 180 – 189.Schramm, O. 1988, "Illuminating sets of constant width" , Mathematika, vol. 35, pp. 180 – 189.J. Bourgain, J. Lindenstrauss 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, 1991. P. 138 – 144.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.M. Lassak An estimate concerning Borsuk’s partition problem // Bull. Acad. Polon. Sci. Ser. Math. 1982. Vol. 30. P. 449 – 451.Lassak, M. 1982, "An estimate concerning Borsuk’s partition problem" , Bull. Acad. Polon. Sci. Ser. Math., vol. 30, pp. 449 – 451.

The authors declare that there are no conflicts of interest present.