- PII
- 10.31857/S2686954322600756-1
- DOI
- 10.31857/S2686954322600756
- Publication type
- Status
- Published
- Authors
- Volume/ Edition
- Volume 509 / Issue number 1
- Pages
- 28-35
- Abstract
- 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.
- Keywords
- случайный гиперграф раскраски гиперграфов <span class="inline-formula"><span class="math">\(j\)</span></span>-хроматическое число пороговые вероятности метод второго момента
- Date of publication
- 17.09.2025
- Year of publication
- 2025
- Number of purchasers
- 0
- Views
- 13
References
- 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:43.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
