ON THE CONCENTRATION OF VALUES OF j-CHROMATIC NUMBERS OF RANDOM HYPERGRAPHS

Мұқаба

Дәйексөз келтіру

Толық мәтін

Ашық рұқсат Ашық рұқсат
Рұқсат жабық Рұқсат берілді
Рұқсат жабық Тек жазылушылар үшін

Аннотация

The paper deals with the study of the limit distribution of the \(j\)-chromatic numbers of a random k-uniform hypergraph in the binomial model \(H(n,k,p)\). We consider the sparse case when the expected number of edges is a linear function of the number of vertices \(n\), i.e. is equal to \(cn\) for \(c > 0\) not depending on \(n\). We prove that for all large enough values of \(c\), the \(j\)-chromatic number of \(H(n,k,p)\) is concentrated in one or two consecutive numbers with probability tending to 1.

Авторлар туралы

I. Denisov

Lomonosov Moscow State University

Email: shabanov.da@mipt.ru
Russian Federation, Moscow

D. Shabanov

HSE University; Moscow Institute of Physics and Technology

Хат алмасуға жауапты Автор.
Email: shabanov.da@mipt.ru
Russian Federation, Moscow; Russian Federation, Moscow, Dolgoprudny

Әдебиет тізімі

  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