- Код статьи
- 10.31857/S2686954323600179-1
- DOI
- 10.31857/S2686954323600179
- Тип публикации
- Статус публикации
- Опубликовано
- Авторы
- Том/ Выпуск
- Том 512 / Номер выпуска 1
- Страницы
- 52-57
- Аннотация
- В работе исследуется структура множества полноцветных раскрасок в три цвета у случайного гиперграфа в равномерной модели \(H(n,k,m)\). Хорошо известно, что свойство наличия полноцветной раскраски в заданное число цветов r имеет точную пороговую функцию, такое пороговое значение \({{\hat {m}}_{r}} = {{\hat {m}}_{r}}(n)\), что для любого \(\varepsilon > 0\) при \(m\;\leqslant \;(1 - \varepsilon ){{\hat {m}}_{r}}\) случайный гиперграф \(H(n,k,m)\) с вероятностью, стремящейся к 1 при \(n \to \infty \), обладает подобной раскраской, а при \(m\; \geqslant \;(1 + \varepsilon ){{\hat {m}}_{r}}\) – наоборот, не обладает подобной раскраской с вероятностью, стремящейся к 1. Мы исследуем алгоритмическую границу для свойства полноцветной раскраски в три цвета и доказываем, что если параметр m принимает значения несколько меньше, чем \({{\hat {m}}_{3}}\), то множество трехцветных полноцветных раскрасок \(H(n,k,m)\) хоть и не пусто с вероятностью, стремящейся к 1, но при этом подчиняется эффекту шаттеринга, впервые описанного в работе Д. Аклиоптаса и А. Койя-Оглана 2008 г.
- Ключевые слова
- случайный гиперграф раскраски гиперграфов полноцветные раскраски шаттеринг
- Дата публикации
- 17.09.2025
- Год выхода
- 2025
- Всего подписок
- 0
- Всего просмотров
- 11
Библиография
- 1. Krzakala F., Montanari A., Ricci-Tersenghi F., Semerjian G., Zdeborová L. Gibbs states and the set of solutions of random constraint satisfaction problems // Proceedings of the National Academy of Sciences. 2007. V. 104. № 25. P. 10318–10323. https://doi.org/10.1073/pnas.0703685104
- 2. Karp R.M. Reducibility among Combinatorial Problems // Complexity of Computer Computations: Proceedings of a symposium on the Complexity of Computer Computations. Springer US. 1972. P. 85–103. https://doi.org/10.1007/978-1-4684-2001-2_9
- 3. Dinur I., Regev O. Smyth C. The hardness of 3-Uniform hypergraph coloring // The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings. 2002. P. 33–40. https://doi.org/10.1109/SFCS.2002.1181880
- 4. Lund C., Yannakakis M. On the hardness of approximating minimization problems // J. ACM. 1994. V. 41. № 5. P. 960–981. https://doi.org/10.1145/185675.306789
- 5. Alon N., Spencer J. A note on coloring random -sets // unpublished manuscript, http://www.cs.tau.ac.il/?nogaa/PDFS/kset2.pdf.
- 6. Achlioptas D., Kim J.H., Krivelevich M., Tetali P. Two-colorings random hypergraphs // Random Structures and Algorithms. 2002. V. 20. № 2. P. 249–259. https://doi.org/10.1002/rsa.997
- 7. Achlioptas D., Moore C. Random -SAT: two moments suffice to cross a sharp threshold // SIAM Journal on Computing. 2005. V. 36. № 3. P. 740–762.
- 8. Coja-Oghlan A., Zdeborová L. The condensation transition in random hypergraph 2-coloring // Proc. 23rd Annual ACM–SIAM Symposium on Discrete Algorithms. SIAM. 2012. P.241–250.
- 9. Coja-Oghlan A., Panagiotou K. Catching the k-NAESAT threshold // Proc. 44th STOC. 2012. P. 899–908.
- 10. Achlioptas D., Molloy M., The analysis of a list-coloring algorithm on a random graph // Proceedings 38th Annual Symposium on Foundations of Computer Science. 1997. P. 204–212.
- 11. Coja-Oghlan A., Vilenchik D. The Chromatic Number of Random Graphs for Most Average Degrees // International Mathematics Research Notices. 2015. V. 2016. № 19. P. 5801–5859. https://doi.org/10.1093/imrn/rnv333
- 12. 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
- 13. Achlioptas D., Coja-Oghlan A. Algorithmic Barriers from Phase Transitions // 49th Annual IEEE Symposium on Foundations of Computer Science. 2008. P. 793–802.
- 14. Erdős P., Lovász L. Problems and results on 3-chromatic hypergraphs and some related questions // Infinite and Finite Sets. Colloquia Mathematica Societatis Janos Bolyai. 1973. V. 10. P. 609–627.
- 15. Guruswami V., Saket R. Hardness of Rainbow Coloring Hypergraphs // 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017). Leibniz International Proceedings in Informatics (LIPIcs). 2018. V. 93. P. 33:01–33:15. https://doi.org/10.4230/LIPIcs.FSTTCS.2017.33
- 16. Kravtsov D.A., Krokhmal N.E., Shabanov D.A. Panchromatic 3-colorings of random hypergraphs // European Journal of Combinatorics. 2019. V. 78. P. 28–43. https://doi.org/10.1016/j.ejc.2019.01.006
- 17. Кравцов Д.А., Крохмаль Н.Е., Шабанов Д.А. Полноцветные раскраски случайных гиперграфов // Дискретная математика. 2019. Т. 31. №2. С. 84–113. https://doi.org/10.1515/dma-2021-0003
- 18. Ayre P., Greenhill C. Rigid Colorings of Hypergraphs and Contiguity // SIAM Journal on Discrete Mathematics. 2019. V. 33. № 3. P. 1575–1606. https://doi.org/10.1137/18M1207211
- 19. 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
