О концентрации значений  j-хроматических чисел случайных гиперграфов

Обложка

Цитировать

Полный текст

Аннотация

Работа посвящена изучению предельного поведения \(j\)-хроматических чисел случайного k-однородного гиперграфа в биномиальной модели \(H(n,k,p)\). Рассматривается разреженный случай, когда среднее число ребер является линейной функцией от числа вершин \(n\), т.е. равно \(cn\), где \(c > 0\) не зависит от \(n\). Доказано, что при всех достаточно больших значениях \(c\) величина \(j\)-хроматического числа \(H(n,k,p)\) с вероятностью, стремящейся к 1, концентрируется в одном или двух соседних значениях.

Об авторах

И. О. Денисов

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

Email: shabanov.da@mipt.ru
Россия, Москва

Д. А. Шабанов

Национальный исследовательский университет “Высшая школа экономики”; Московский физико-технический институт (Национальный исследовательский университет)

Автор, ответственный за переписку.
Email: shabanov.da@mipt.ru
Россия, Москва; Россия, Московская обл., Долгопрудный

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

  1. Grimmett G.R., McDiarmid C.J. On colouring random graphs // Math. Proc. Cambridge Philos. Soc. 1975. V. 77. P. 313–324. https://doi.org/10.1017/S0305004100051124
  2. Bollobás B. The chromatic number of random graphs // Combinatorica. 1988. V. 8. P. 49–56. https://doi.org/10.1007/BF02122551
  3. Łuczak T. The chromatic number of random graphs // Combinatorica. 1991. V. 11. № 1. P. 45–54. https://doi.org/10.1007/BF01375472
  4. Łuczak T. A note on the sharp concentration of the chromatic number of random graphs // Combinatorica. 1991. V. 11. № 3. P. 295–297. https://doi.org/10.1007/BF01205080
  5. Alon N., Krivelevich M. The concentration of the chromatic number of random graphs // Combinatorica. 1997. V. 17. № 3. P. 303–313. https://doi.org/10.1007/BF01215914
  6. Achlioptas D., Naor A. The two possible values of the chromatic number of a random graph // Annals of Mathematics. 2005. V. 162. № 3. P. 1335–1351. https://doi.org/10.4007/annals.2005.162.1335
  7. Coja-Oghlan A., Panagiotou K., Steger A. On the chromatic number of random graphs // Journal of Combinatorial Theory Series B. 2008. V. 98. P. 980–993. https://doi.org/10.1016/j.jctb.2007.11.009
  8. Kargaltsev S.A., Shabanov D.A., Shaikheeva T.M. Two values of the chromatic number of a sparse random graph // Acta Mathematica Universitatis Comenianae. 2019. V. 88. № 3. P. 849–854.
  9. Coja-Oghlan A., Vilenchik D. The Chromatic Number of Random Graphs for Most Average Degrees // International Mathematics Research Notices. 2015. V. 2016. No.19. P. 5801–5859. https://doi.org/10.1093/imrn/rnv333
  10. Coja-Oghlan A. Upper-bounding the k-colorability threshold by counting cover // Electronic Journal of Combinatorics. 2013. V. 20. № 3. Research paper № 32. https://doi.org/10.37236/3337
  11. Schmidt-Pruzan J., Shamir E., Upfal E. Random hypergraph coloring algorithms and the weak chromatic number // J. Graph Theory. 1985. V. 8. P. 347–362. https://doi.org/10.1002/jgt.3190090307
  12. Schmidt J. Probabilistic analysis of strong hypergraph coloring algorithms and the strong chromatic number // Discrete Mathematics. 1987. V. 66. P. 258–277. https://doi.org/10.1016/0012-365X(87)90101-4
  13. Shamir E. Chromatic number of random hypergraphs and associated graphs // Adv. Comput. Res. 1989. V. 5. P. 127–142.
  14. Krivelevich M., Sudakov B. The chromatic numbers of random hypergraphs // Random Structures and Algorithms. 1998. V. 12. № 4. P. 381–403. https://doi.org/10.1002/(sici)1098-2418(199807)12:4<381::aid-rsa5>3.0.co;2-p
  15. Dyer M., Frieze A., Greenhill C. On the chromatic number of a random hypergraph // Journal of Combinatorial Theory, Series B. 2015. V. 113. P. 68–122. https://doi.org/10.1016/j.jctb.2015.01.002
  16. Ayre P., Coja-Oghlan A., Greenhill C. Hypergraph coloring up to condensation // Random Structures and Algorithms. 2019. V. 54. № 4. P. 615–652. https://doi.org/10.1002/rsa.20824
  17. Shabanov D.A. Estimating the r-colorability threshold for a random hypergraph // Discrete Applied Mathematics. 2020. V. 282. P. 168–183. https://doi.org/10.1016/j.dam.2019.10.031
  18. Демидович Ю.А., Шабанов Д.А. О двух предельных значениях хроматического числа случайного гиперграфа // Теория вероятностей и ее применения. 2022. Т. 67. № 2. С. 223–246. https://doi.org/10.1137/S0040585X97T990861
  19. Семенов А.С., Шабанов Д.А. Оценки пороговых вероятностей для свойств раскрасок случайных гиперграфов // Проблемы передачи информации. 2022. Т. 58. № 1. С. 72–101. https://doi.org/10.1134/S0032946022010057
  20. Semenov A., Shabanov D. On the weak chromatic number of random hypergraphs // Discrete Applied Mathematics. 2020. V. 276. P. 134–154. https://doi.org/10.1016/j.dam.2019.03.025
  21. Матвеева Т.Г., Хузиева А.Э., Шабанов Д.А. О сильном хроматическом числе случайных гиперграфов // Доклады Российской академии наук. Математика, информатика, процессы управления. 2022. Т. 502. С. 37–41. https://doi.org/10.1134/s1064562422010094
  22. Hatami H., Molloy M. Sharp thresholds for constraint satisfaction problems and homomorphisms // Random Structures and Algorithms. 2008. V. 33. № 3. P. 310–332. https://doi.org/10.1002/rsa.20225

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

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

© И.О. Денисов, Д.А. Шабанов, 2023

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

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») на элемент с текстом «Принять и продолжить».