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

封面

如何引用文章

全文:

开放存取 开放存取
受限制的访问 ##reader.subscriptionAccessGranted##
受限制的访问 订阅存取

详细

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

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

##common.cookie##