О РЕАЛИЗАЦИИ СЛУЧАЙНЫХ ГРАФОВ ГРАФАМИ РАССТОЯНИЙ И ДИАМЕТРОВ В ЕВКЛИДОВЫХ ПРОСТРАНСТВАХ
https://doi.org/10.22405/2226-8383-2015-16-2-133-143
Аннотация
В данной работе рассматривается задача об отыскании пороговых вероятностей для реализации случайного графа геометрическим графом в пространстве Rd. В случае графов диаметров доказывается асимптоти ка для пороговой вероятности на плоскости, а также точное по порядку выражение для d � 3.
При поддержке: Настоящая работа выполнена при финансовой поддержке гранта РФФИ N 15-01-03530 и гранта НШ-2964.2014.1 поддержки ведущих научных школ
Об авторах
А. В. Крот
Московский физико-технический институт
Россия
Россия
А. М. Райгородский
Московский государственный университет имени М. В. Ломоносова
Россия
Россия
Список литературы
1. L. 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.
2. 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.
3. A. M. Raigorodskii Coloring Distance Graphs and Graphs of Diameters // Thirty Essays on Geometric Graph Theory, J. Pach ed., Springer. 2013. P. 429 – 460.
4. А. М. Райгородский Проблема Борсука и хроматические числа метрических пространств // Успехи мат. наук. 2001. Т. 56, вып. 1. С. 107 – 146.
5. V. G. Boltyanski, H. Martini, P. S. Soltan Excursions into combinatorial geometry. Universitext, Springer, Berlin, 1997.
6. B. Bollob´as Random Graphs. Cambridge Univ. Press, Second Edition. 2001.
7. А. А. Кокоткин, А. М. Райгородский О больших подграфах графа расстояний, имеющих маленькое хроматическое число // Современная математика. Фундаментальные направления. 2013. Т. 51. С. 64 – 73.
8. А. М. Райгородский, С. В. Нагаева О реализации случайных графов графами расстояний в пространствах фиксированной размерности // Доклады РАН. 2009. Т. 424, № 3. С. 315 – 317.
9. А. М. Райгородский Об одной серии задач рамсеевского типа в комбинаторной геометрии // Доклады РАН. 2007. Т. 413, № 2. С. 171 – 173.
10. А. Б. Купавский, М. В. Титова Дистанционные числа Рамсея // Доклады РАН. 2013. Т. 449, № 3. С. 267 – 270.
11. N. Alon, A. Kupavskii Two notions of unit distance graphs // J. Comb. Theory, Ser. A. 2014. Vol. 125. P. 1 – 17.
12. 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.
13. P. Erd˝os On sets of distances of n points // Amer. Math. Monthly. 1946. Vol. 53. P. 248 – 250.
14. А. М. Райгородский Модели случайных графов. М.: МЦНМО. 2011.
15. 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.
16. O. Schramm Illuminating sets of constant width // Mathematika. 1988. Vol. 35. P. 180 – 189.
17. 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.
18. M. Lassak An estimate concerning Borsuk’s partition problem // Bull. Acad. Polon. Sci. Ser. Math. 1982. Vol. 30. P. 449 – 451.
Рецензия
Для цитирования:
Крот А.В., Райгородский А.М. О РЕАЛИЗАЦИИ СЛУЧАЙНЫХ ГРАФОВ ГРАФАМИ РАССТОЯНИЙ И ДИАМЕТРОВ В ЕВКЛИДОВЫХ ПРОСТРАНСТВАХ. Чебышевский сборник. 2015;16(2):133-143. https://doi.org/10.22405/2226-8383-2015-16-2-133-143
For citation:
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
Просмотров:
401
Послать статью по эл. почте 