Графы Джонсона, их случайные подграфы и некоторые их экстремальные характеристики

Обложка
  • Авторы: Райгородский А.М.1,2,3,4, Синельников-Мурылев П.С.5
  • Учреждения:
    1. Московский физико-технический институт (национальный исследовательский университет), кафедра дискретной математики и лаборатория продвинутой комбинаторики исетевых приложений
    2. Московский государственный университет им. М. В. Ломоносова, механико-математический факультет
    3. Кавказский математический центр Адыгейского государственного университета
    4. Бурятский государственный университет, Институт математики и информатики
  • Выпуск: Том 80, № 3 (2025)
  • Страницы: 113-176
  • Раздел: Статьи
  • URL: https://bakhtiniada.ru/0042-1316/article/view/306757
  • DOI: https://doi.org/10.4213/rm10233
  • ID: 306757

Цитировать

Полный текст

Открытый доступ Открытый доступ
Доступ закрыт Доступ предоставлен
Доступ закрыт Только для подписчиков

Аннотация

Одним из очень важных объектов современной теории графов является так называемый граф Джонсона $G(n,r,s)$. Его вершинами служат все $C_n^r$ подмножеств мощности $r$ множества $\{1,…,n\}$, а ребром две вершины соединяются тогда и только тогда, когда пересечение соответствующих подмножеств имеет мощность $s$. Такие графы играют огромную роль в теории кодирования, в экстремальной комбинаторике и теории Рамсея, в комбинаторной геометрии и др. В обзоре рассказывается о применениях этих графов и о нескольких их характеристиках, среди которых число независимости, кликовое число и хроматическое число. Также мы уделяем внимание большому и активно развивающемуся в последнее время разделу теории, связанному с рассмотрением случайных подграфов графов Джонсона. Библиография: 135 названий.

Об авторах

Андрей Михайлович Райгородский

Московский физико-технический институт (национальный исследовательский университет), кафедра дискретной математики и лаборатория продвинутой комбинаторики исетевых приложений; Московский государственный университет им. М. В. Ломоносова, механико-математический факультет; Кавказский математический центр Адыгейского государственного университета; Бурятский государственный университет, Институт математики и информатики

Email: mraigor@yandex.ru

доктор физико-математических наук, профессор

Петр Сергеевич Синельников-Мурылев

Автор, ответственный за переписку.
Email: petya670@gmail.com

без ученой степени, без звания

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

  1. Ф. Дж. Мак-Вильямс, Н. Дж. А. Слоэн, Теория кодов, исправляющих ошибки, Части I, II, Связь, М., 1979, 744 с.
  2. M. Kneser, “Aufgabe 360”, Jahresber. Dtsch. Math.-Ver., 58:2 (1956), 27
  3. А. М. Райгородский, Гипотеза Кнезера и топологические методы в комбинаторике, МЦНМО, М., 2011, 32 с.
  4. J. Matoušek, Using the {B}orsuk–{U}lam theorem, Lectures on topological methods in combinatorics and geometry, Universitext, Springer-Verlag, Berlin, 2003, xii+196 pp.
  5. М. Холл, Комбинаторика, Мир, М., 1970, 424 с.
  6. P. Erdős, G. Szekeres, “A combinatorial problem in geometry”, Compos. Math., 2 (1935), 463–470
  7. S. P. Radziszowski, “Small Ramsey numbers”, Electron. J. Combin., 1 (1994), Dynamic Survey 1, 30 pp.
  8. R. L. Graham, B. L. Rothschild, J. H. Spencer, Ramsey theory, Wiley-Intersci. Ser. Discrete Math. Optim., 2nd ed., John Wiley & Sons, Inc., New York, 1990, xii+196 pp.
  9. M. Campos, S. Griffiths, R. Morris, J. Sahasrabudhe, An exponential improvement for diagonal Ramsey, 2023, 57 pp.
  10. P. Gupta, N. Ndiaye, S. Norin, L. Wei, Optimizing the CGMS upper bound on Ramsey numbers, 2024, 18 pp.
  11. P. Balister, B. Bollobas, M. Campos, S. Griffiths, E. Hurley, R. Morris, J. Sahasrabudhe, M. Tiba, Upper bounds for multicolour Ramsey numbers, 2024, 17 pp.
  12. Н. Алон, Дж. Спенсер, Вероятностный метод, Бином. Лаборатория знаний, М., 2007, 320 с.
  13. А. М. Райгородский, Линейно-алгебраический метод в комбинаторике, 2-е изд., МЦНМО, М., 2007, 136 с.
  14. А. М. Райгородский, “Проблема Борсука и хроматические числа некоторых метрических пространств”, УМН, 56:1(337) (2001), 107–146
  15. A. M. Raigorodskii, “Coloring distance graphs and graphs of diameters”, Thirty essays on geometric graph theory, Springer, New York, 2013, 429–460
  16. A. M. Raigorodskii, “Cliques and cycles in distance graphs and graphs of diameters”, Discrete geometry and algebraic combinatorics, Contemp. Math., 625, Amer. Math. Soc., Providence, RI, 2014, 93–109
  17. П. Брасс, У. Мозер, Я. Пах, Открытые проблемы дискретной геометрии, МЦНМО, М., 2021, 448 с.
  18. A. Soifer, The mathematical coloring book. Mathematics of coloring and the colorful life of its creators, Springer, New York, 2009, xxx+607 pp.
  19. V. Boltyanski, H. Martini, P. S. Soltan, Excursions into combinatorial geometry, Universitext, Springer-Verlag, Berlin, 1997, xiv+418 pp.
  20. D. G. Larman, C. A. Rogers, “The realization of distances within sets in Euclidean space”, Mathematika, 19 (1972), 1–24
  21. R. Prosanov, “A new proof of the Larman–Rogers upper bound for the chromatic number of the Euclidean space”, Discrete Appl. Math., 276 (2020), 115–120
  22. N. G. de Bruijn, P. Erdős, “A colour problem for infinite graphs and a problem in the theory of relations”, Nederl. Akad. Wetensch. Proc. Ser. A, 54, = Indagationes Math., 13 (1951), 371–373
  23. P. Shuldiner, R. W. Oldford, The clique structure of Johnson graphs, 2022, 14 pp.
  24. А. С. Гусев, “Кликовые числа случайных подграфов некоторых дистанционных графов”, Пробл. передачи информ., 54:2 (2018), 73–85
  25. S. F. Jorgensen, On the clique covering numbers of Johnson graphs, 2025, 13 pp.
  26. Ф. Харари, Теория графов, 2-е изд., Едиториал УРСС, М., 2003, 300 с.
  27. C. J. Colbourn, J. H. Dinitz (eds.), Handbook of combinatorial designs, Discrete Math. Appl. (Boca Raton), 2nd ed., Chapman & Hall/CRC, Boca Raton, FL, 2007, xxii+984 pp.
  28. P. Keevash, The existence of designs, 2024 (v1 – 2014), 55 pp.
  29. P. Keevash, The existence of designs II, 2018, 64 pp.
  30. V. Rödl, “On a packing and covering problem”, European J. Combin., 6:1 (1985), 69–78
  31. P. Frankl, Z. Füredi, “Forbidding just one intersection”, J. Combin. Theory Ser. A, 39:2 (1985), 160–176
  32. P. Frankl, R. Wilson, “Intersection theorems with geometric consequences”, Combinatorica, 1:4 (1981), 357–368
  33. Z. Nagy, “A certain constructive estimate of the Ramsey number”, (Hungarian), Mat. Lapok, 23 (1972), 301–302
  34. P. Erdős, Chao Ko, R. Rado, “Intersection theorems for systems of finite sets”, Quart. J. Math. Oxford Ser. (2), 12 (1961), 313–320
  35. P. Keevash, D. Mubayi, R. M. Wilson, “Set systems with no singleton intersection”, SIAM J. Discrete Math., 20:4 (2006), 1031–1041
  36. Л. И. Боголюбский, А. М. Райгородский, “Замечание о нижних оценках хроматических чисел пространств малой размерности с метриками $ell_1$ и $ell_2$”, Матем. заметки, 105:2 (2019), 187–213
  37. A. Passuello, Semidefinite programming in combinatorial optimization with applications to coding theory and geometry, Ph.D. thesis, Univ. Bordeaux I, 2013, xvi+98 pp.
  38. R. Ahlswede, L. H. Khachatrian, “The complete intersection theorem for systems of finite sets”, European J. Combin., 18:2 (1997), 125–136
  39. P. Frankl, “The Erdős–Ko–Rado theorem is true for $n=ckt$”, Combinatorics (Keszthely, 1976), v. 1, Colloq. Math. Soc. Janos Bolyai, 18, North-Holland Publishing Co., Amsterdam–New York, 1978, 365–375
  40. R. M. Wilson, “The exact bound in the Erdős–Ko–Rado theorem”, Combinatorica, 4:2-3 (1984), 247–257
  41. N. N. Kuzjurin, “On the difference between asymptotically good packings and coverings”, European J. Combin., 16:1 (1995), 35–40
  42. R. C. Baker, G. Harman, J. Pintz, “The difference between consecutive primes. II”, Proc. London Math. Soc. (3), 83:3 (2001), 532–562
  43. D. Ellis, N. Keller, N. Lifshitz, “Stability for the complete intersection theorem, and the forbidden intersection problem of Erdős and Sos”, J. Eur. Math. Soc. (JEMS), 26:5 (2024), 1611–1654
  44. N. Keller, N. Lifshitz, “The junta method for hypergraphs and the Erdős–Chvatal simplex conjecture”, Adv. Math., 392 (2021), 107991, 95 pp.
  45. A. Kupavskii, D. Zakharov, “Spread approximations for forbidden intersections problems”, Adv. Math., 445 (2024), 109653, 29 pp.
  46. D. Cherkashin, “On set systems without singleton intersections”, Discrete Math. Lett., 14 (2024), 85–88
  47. Е. И. Пономаренко, А. М. Райгородский, “Новые оценки в задаче о числе ребер гиперграфа с запретами на пересечения”, Пробл. передачи информ., 49:4 (2013), 98–104
  48. A. Kupavskii, A. Sagdeev, D. Zakharov, Cutting corners, 2022, 16 pp.
  49. А. М. Райгородский, А. А. Сагдеев, “Об одной оценке в экстремальной комбинаторике”, Докл. РАН, 478:3 (2018), 271–273
  50. А. В. Бобу, А. Э. Куприянов, А. М. Райгородский, “Асимптотическое исследование задачи о максимальном числе ребер однородного гиперграфа с одним запрещенным пересечением”, Матем. сб., 207:5 (2016), 17–42
  51. P. Frankl, V. Rödl, “Forbidden intersections”, Trans. Amer. Math. Soc., 300:1 (1987), 259–286
  52. А. Е. Звонарeв, А. М. Райгородский, Д. В. Самиров, А. А. Харламова, “О хроматическом числе пространства с запрещенным равносторонним треугольником”, Матем. сб., 205:9 (2014), 97–120
  53. А. Е. Звонарев, А. М. Райгородский, “Улучшения теоремы Франкла–Рeдля о числе ребер гиперграфа с запрещенным пересечением и их следствия в задаче о хроматическом числе пространства с запрещенным равносторонним треугольником”, Геометрия, топология и приложения, Сборник статей. К 70-летию со дня рождения профессора Николая Петровича Долбилина, Труды МИАН, 288, МАИК “Наука/Интерпериодика”, М., 2015, 109–119
  54. А. А. Сагдеев, “Улучшенная теорема Франкла–Рeдля и некоторые ее геометрические следствия”, Пробл. передачи информ., 54:2 (2018), 45–72
  55. А. А. Сагдеев, “О теореме Франкла–Рэдла”, Изв. РАН. Сер. матем., 82:6 (2018), 128–157
  56. А. А. Сагдеев, “Об одной теореме Франкла–Уилсона”, Пробл. передачи информ., 55:4 (2019), 86–106
  57. P. Keevash, E. Long, “Frankl–Rödl-type theorems for codes and permutations”, Trans. Amer. Math. Soc., 369:2 (2017), 1147–1162
  58. T. Etzion, S. Bitan, “On the chromatic number, colorings, and codes of the Johnson graph”, Discrete Appl. Math., 70:2 (1996), 163–175
  59. A. E. Brouwer, T. Etzion, “Some new distance-4 constant weight codes”, Adv. Math. Commun., 5:3 (2011), 417–424
  60. Д. В. Карпов, Теория графов, МЦНМО, М., 2022, 560 с.
  61. А. М. Райгородский, “Еще немного о математике раскрасок”, Матем. просв., сер. 3, 31, МЦНМО, М., 2023, 55–73
  62. А. М. Райгородский, “Проблемы Борсука и Грюнбаума для решетчатых многогранников”, Изв. РАН. Сер. матем., 69:3 (2005), 81–108
  63. А. М. Райгородский, Системы общих представителей в комбинаторике и их приложения в геометрии, МЦНМО, М., 2023, 136 с.
  64. Д. Цветкович, М. Дуб, Х. Захс, Спектры графов. Теория и применение, Наук. думка, Киев, 1984, 384 с.
  65. А. Э. Гутерман, В. К. Любимов, А. М. Райгородский, А. С. Усачев, “О числах независимости дистанционных графов с вершинами в ${-1,0,1}^n$: оценки, гипотезы и приложения к проблемам Нельсона–Эрдеша–Хадвигера и Борсука”, Совр. матем. и ее приложения, 65 (2009), 82–100
  66. А. В. Бобу, О. А. Костина, А. Э. Куприянов, “Числа независимости и хроматические числа некоторых дистанционных графов”, Пробл. передачи информ., 51:2 (2015), 86–98
  67. J. Balogh, D. Cherkashin, S. Kiselev, “Coloring general Kneser graphs and hypergraphs via high-discrepancy hypergraphs”, European J. Combin., 79 (2019), 228–236
  68. G. M. Ziegler, “Coloring Hamming graphs, optimal binary codes, and the 0/1-Borsuk problem in low dimensions”, Computational discrete mathematics, Lecture Notes in Comput. Sci., 2122, LNCS Tutor., Springer-Verlag, Berlin, 2001, 159–171
  69. А. Б. Купавский, А. М. Райгородский, “О хроматическом числе $mathbb R^9$”, Фундамент. и прикл. матем., 14:5 (2008), 139–154
  70. A. Sidorenko, “What we know and what we do not know about Turan numbers”, Graphs Combin., 11:2 (1995), 179–199
  71. O. Pikhurko, “Constructions of Turan systems that are tight up to a multiplicative constant”, Adv. Math., 464 (2025), 110148, 11 pp.
  72. J. Balogh, A. Kostochka, A. Raigorodskii, “Coloring some finite sets in ${mathbb R}^n$”, Discuss. Math. Graph Theory, 33:1 (2013), 25–31
  73. LXXV Московская математическая олимпиада. Задачи и решения, МЦНМО, М., 2012, 71 с.
  74. D. Zakharov, “Chromatic numbers of Kneser-type graphs”, J. Combin. Theory Ser. A, 172 (2020), 105188, 16 pp.
  75. Д. А. Захаров, “О хроматических числах некоторых дистанционных графов”, Матем. заметки, 107:2 (2020), 210–220
  76. B. Bollobas, Random graphs, Cambridge Stud. Adv. Math., 73, 2nd ed., Cambridge Univ. Press, Cambridge, 2001, xviii+498 pp.
  77. S. Janson, T. Łuczak, A. Rucinski, Random graphs, Wiley-Intersci. Ser. Discrete Math. Optim., Wiley-Interscience [John Wiley & Sons], New York, 2000, xii+333 pp.
  78. A. Frieze, M. Karonski, Introduction to random graphs, Cambridge Univ. Press, Cambridge, 2016, xvii+464 pp.
  79. В. Ф. Колчин, Случайные графы, Физматлит, М., 2000, 256 с.
  80. R. Durrett, Random graph dynamics, Camb. Ser. Stat. Probab. Math., Cambridge Univ. Press, Cambridge, 2007, x+212 pp.
  81. R. van der Hofstad, Random graphs and complex networks, v. 1, Camb. Ser. Stat. Probab. Math., 43, Cambridge Univ. Press, Cambridge, 2017, xvi+321 pp.
  82. А. М. Райгородский, Модели интернета, 2-е изд., Интеллект, Долгопрудный, 2019, 64 с.
  83. А. М. Райгородский, Модели случайных графов, 3-е изд., МЦНМО, М., 2025, 135 с.
  84. P. Erdős, A. Renyi, “On random graphs. I”, Publ. Math. Debrecen, 6 (1959), 290–297
  85. P. Erdős, A. Renyi, “On the evolution of random graphs”, Magyar Tud. Akad. Mat. Kutato Int. Közl., 5 (1960), 17–61
  86. P. Erdős, A. Renyi, “On the evolution of random graphs”, Bull. Inst. Internat. Statist., 38:4 (1961), 343–347
  87. M. Krivelevich, B. Sudakov, “Pseudo-random graphs”, More sets, graphs and numbers, Bolyai Soc. Math. Stud., 15, Springer, Berlin, 2006, 199–262
  88. Ю. Д. Буртин, “О вероятности связности случайного подграфа $n$-мерного куба”, Пробл. передачи информ., 13:2 (1977), 90–95
  89. Л. И. Боголюбский, А. С. Гусев, М. М. Пядeркин, А. М. Райгородский, “Числа независимости и хроматические числа случайных подграфов в некоторых последовательностях графов”, Докл. РАН, 457:4 (2014), 383–387
  90. Л. И. Боголюбский, А. С. Гусев, М. М. Пядeркин, А. М. Райгородский, “Числа независимости и хроматические числа случайных подграфов некоторых дистанционных графов”, Матем. сб., 206:10 (2015), 3–36
  91. М. Е. Жуковский, А. М. Райгородский, “Случайные графы: модели и предельные характеристики”, УМН, 70:1(421) (2015), 35–88
  92. А. Р. Ярмухаметов, “Гигантская и мелкие компоненты в случайных дистанционных графах специального вида”, Матем. заметки, 92:6 (2012), 949–953
  93. M. Koshelev, “Spectrum of Johnson graphs”, Discrete Math., 346:3 (2023), 113262, 22 pp.
  94. B. Bollobas, P. Erdős, “Cliques in random graphs”, Math. Proc. Cambridge Philos. Soc., 80:3 (1976), 419–427
  95. D. W. Matula, “On the complete subgraphs of a random graph”, Proceedings of the second Chapel Hill conference on combinatorial mathematics and its applications (Univ. North Carolina, Chapel Hill, NC, 1970)), Univ. North Carolina, Chapel Hill, NC, 1970, 356–369
  96. A. M. Frieze, “On the independence number of random graphs”, Discrete Math., 81:2 (1990), 171–175
  97. V. Dani, C. Moore, “Independent sets in random graphs from the weighted second moment method”, Approximation, randomization, and combinatorial optimization, Lecture Notes in Comput. Sci., 6845, Springer, Heidelberg, 2011, 472–482
  98. T. Bohman, J. Hofstad, Two-point concentration of the independence number of the random graph, 2024 (v1 – 2022), 28 pp.
  99. М. М. Пядeркин, “О пороговой вероятности для устойчивости независимых множеств в дистанционном графе”, Матем. заметки, 106:2 (2019), 280–294
  100. A. J. W. Hilton, E. C. Milner, “Some intersection theorems for systems of finite sets”, Quart. J. Math. Oxford Ser. (2), 18 (1967), 369–384
  101. P. Frankl, “On intersecting families of finite sets”, J. Combin. Theory Ser. A, 24:2 (1978), 146–161
  102. P. Frankl, “A simple proof of the Hilton–Milner theorem”, Mosc. J. Comb. Number Theory, 8:2 (2019), 97–101
  103. J. Balogh, T. Bohman, D. Mubayi, “Erdős–Ko–Rado in random hypergraphs”, Combin. Probab. Comput., 18:5 (2009), 629–646
  104. B. Bollobas, B. P. Narayanan, A. M. Raigorodskii, “On the stability of the Erdős–Ko–Rado theorem”, J. Combin. Theory Ser. A, 137 (2016), 64–78
  105. J. Balogh, R. A. Krueger, Haoran Luo, “Sharp threshold for the Erdős–Ko–Rado theorem”, Random Structures Algorithms, 62:1 (2023), 3–28
  106. M. M. Pyaderkin, “On the stability of some Erdős–Ko–Rado type results”, Discrete Math., 340:4 (2017), 822–831
  107. Ф. А. Пушняков, “О количествах ребер в порожденных подграфах некоторых дистанционных графов”, Матем. заметки, 105:4 (2019), 592–602
  108. Н. А. Дубинин, Е. А. Неустроева, А. М. Райгородский, Я. К. Шубин, “Нижние и верхние оценки минимального числа ребер в некоторых подграфах графа Джонсона”, Матем. сб., 215:5 (2024), 71–95
  109. Н. М. Деревянко, С. Г. Киселев, “Числа независимости случайных подграфов некоторого дистанционного графа”, Пробл. передачи информ., 53:4 (2017), 3–15
  110. М. М. Пядeркин, “Числа независимости случайных подграфов некоторого дистанционного графа”, Матем. заметки, 99:2 (2016), 288–297
  111. M. Krivelevich, B. Sudakov, Van H. Vu, N. C. Wormald, “On the probability of independent sets in random graphs”, Random Structures Algorithms, 22:1 (2003), 1–14
  112. А. Райгородский, “Об одной ‘олимпиадной’ задаче про графы”, Квант, 2017, № 2, 2–8
  113. А. М. Райгородский, “Об устойчивости числа независимости случайного подграфа”, Докл. РАН, 477:6 (2017), 649–651
  114. E. Surya, L. Warnke, “On the concentration of the chromatic number of random graphs”, Electron. J. Combin., 31:1 (2024), P1.44, 18 pp.
  115. А. С. Гусев, “Новая верхняя оценка хроматического числа случайного подграфа дистанционного графа”, Матем. заметки, 97:3 (2015), 342–349
  116. M. M. Pyaderkin, “On the chromatic number of random subgraphs of a certain distance graph”, Discrete Appl. Math., 267 (2019), 209–214
  117. С. Г. Киселев, А. М. Райгородский, “О хроматическом числе случайного подграфа кнезеровского графа”, Докл. РАН, 476:4 (2017), 375–376
  118. A. Kupavskii, “On random subgraphs of Kneser and Schrijver graphs”, J. Combin. Theory Ser. A, 141 (2016), 8–15
  119. M. Alishahi, H. Hajiabolhassan, “Chromatic number of random Kneser hypergraphs”, J. Combin. Theory Ser. A, 154 (2018), 1–20
  120. A. Kupavskii, “Random Kneser graphs and hypergraphs”, Electron. J. Combin., 25:4 (2018), 4.52, 16 pp.
  121. S. Kiselev, A. Kupavskii, “Sharp bounds for the chromatic number of random Kneser graphs”, J. Combin. Theory Ser. B, 157 (2022), 96–122
  122. P. Erdős, “Graph theory and probability”, Canad. J. Math., 11 (1959), 34–38
  123. А. М. Райгородский, “Графы с большим хроматическим числом и большим обхватом”, Матем. просв., сер. 3, 20, МЦНМО, М., 2016, 228–237
  124. А. М. Райгородский, “О дистанционных графах, имеющих большое хроматическое число, но не содержащих больших симплексов”, УМН, 62:6(378) (2007), 187–188
  125. Е. Е. Демeхин, А. М. Райгородский, О. И. Рубанов, “Дистанционные графы, имеющие большое хроматическое число и не содержащие клик или циклов заданного размера”, Матем. сб., 204:4 (2013), 49–78
  126. А. А. Сагдеев, “О нижних оценках хроматических чисел дистанционных графов с большим обхватом”, Матем. заметки, 101:3 (2017), 430–445
  127. Р. И. Просанов, “Контрпримеры к гипотезе Борсука, имеющие большой обхват”, Матем. заметки, 105:6 (2019), 890–898
  128. А. Б. Купавский, “Явные и вероятностные конструкции дистанционных графов с маленьким кликовым и большим хроматическим числами”, Изв. РАН. Сер. матем., 78:1 (2014), 65–98
  129. M. Bucic, J. Davies, Geometric graphs with exponential chromatic number and arbitrary girth, 2024 (v1 – 2023), 53 pp.
  130. К. А. Михайлов, А. М. Райгородский, “О числах Рамсея для полных дистанционных графов с вершинами в ${0,1}^n$”, Матем. сб., 200:12 (2009), 63–80
  131. В. С. Карась, А. М. Райгородский, “О числах Рамсея для произвольных последовательностей графов”, Докл. РАН. Матем., информ., проц. упр., 502 (2022), 19–22
  132. А. М. Райгородский, “Об одной серии задач рамсеевского типа в комбинаторной геометрии”, Докл. РАН, 413:2 (2007), 171–173
  133. А. М. Райгородский, М. В. Титова, “О дистанционных подграфах графов в пространствах малых размерностей”, Совр. матем. и ее приложения, 76 (2012), 75–83
  134. A. B. Kupavskii, A. M. Raigorodskii, M. V. Titova, “New bounds for the distance Ramsey number”, Discrete Math., 313:22 (2013), 2566–2574
  135. N. Alon, A. Kupavskii, “Two notions of unit distance graphs”, The seventh European conference on combinatorics, graph theory and applications, CRM Series, 16, Edizioni della Normale, Pisa, 2013, 105–110

Дополнительные файлы

Доп. файлы
Действие
1. JATS XML
Скачать

© Райгородский А.М., Синельников-Мурылев П.С., 2025

Согласие на обработку персональных данных с помощью сервиса «Яндекс.Метрика»

1. Я (далее – «Пользователь» или «Субъект персональных данных»), осуществляя использование сайта https://journals.rcsi.science/ (далее – «Сайт»), подтверждая свою полную дееспособность даю согласие на обработку персональных данных с использованием средств автоматизации Оператору - федеральному государственному бюджетному учреждению «Российский центр научной информации» (РЦНИ), далее – «Оператор», расположенному по адресу: 119991, г. Москва, Ленинский просп., д.32А, со следующими условиями.

2. Категории обрабатываемых данных: файлы «cookies» (куки-файлы). Файлы «cookie» – это небольшой текстовый файл, который веб-сервер может хранить в браузере Пользователя. Данные файлы веб-сервер загружает на устройство Пользователя при посещении им Сайта. При каждом следующем посещении Пользователем Сайта «cookie» файлы отправляются на Сайт Оператора. Данные файлы позволяют Сайту распознавать устройство Пользователя. Содержимое такого файла может как относиться, так и не относиться к персональным данным, в зависимости от того, содержит ли такой файл персональные данные или содержит обезличенные технические данные.

3. Цель обработки персональных данных: анализ пользовательской активности с помощью сервиса «Яндекс.Метрика».

4. Категории субъектов персональных данных: все Пользователи Сайта, которые дали согласие на обработку файлов «cookie».

5. Способы обработки: сбор, запись, систематизация, накопление, хранение, уточнение (обновление, изменение), извлечение, использование, передача (доступ, предоставление), блокирование, удаление, уничтожение персональных данных.

6. Срок обработки и хранения: до получения от Субъекта персональных данных требования о прекращении обработки/отзыва согласия.

7. Способ отзыва: заявление об отзыве в письменном виде путём его направления на адрес электронной почты Оператора: info@rcsi.science или путем письменного обращения по юридическому адресу: 119991, г. Москва, Ленинский просп., д.32А

8. Субъект персональных данных вправе запретить своему оборудованию прием этих данных или ограничить прием этих данных. При отказе от получения таких данных или при ограничении приема данных некоторые функции Сайта могут работать некорректно. Субъект персональных данных обязуется сам настроить свое оборудование таким способом, чтобы оно обеспечивало адекватный его желаниям режим работы и уровень защиты данных файлов «cookie», Оператор не предоставляет технологических и правовых консультаций на темы подобного характера.

9. Порядок уничтожения персональных данных при достижении цели их обработки или при наступлении иных законных оснований определяется Оператором в соответствии с законодательством Российской Федерации.

10. Я согласен/согласна квалифицировать в качестве своей простой электронной подписи под настоящим Согласием и под Политикой обработки персональных данных выполнение мною следующего действия на сайте: https://journals.rcsi.science/ нажатие мною на интерфейсе с текстом: «Сайт использует сервис «Яндекс.Метрика» (который использует файлы «cookie») на элемент с текстом «Принять и продолжить».