О концентрации значений  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