Preview

Чебышевский сборник

Расширенный поиск

О РЕАЛИЗАЦИИ СЛУЧАЙНЫХ ГРАФОВ ГРАФАМИ РАССТОЯНИЙ И ДИАМЕТРОВ В ЕВКЛИДОВЫХ ПРОСТРАНСТВАХ

https://doi.org/10.22405/2226-8383-2015-16-2-133-143

Полный текст:

Аннотация

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

 

Об авторах

А. В. Крот
Московский физико-технический институт
Россия


А. М. Райгородский
Московский государственный университет имени М. В. Ломоносова
Россия


Список литературы

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

Просмотров: 71


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 2226-8383 (Print)