1. На главную
  2. Электронные версии
  3. Доклады Российской академии наук. Математика, информатика, процессы управления
  4. T. 512, № 1, 2023

Доклады Российской академии наук. Математика, информатика, процессы управления, 2023, T. 512, № 1, стр. 52-57

О СТРУКТУРЕ МНОЖЕСТВА ПОЛНОЦВЕТНЫХ РАСКРАСОК СЛУЧАЙНОГО ГИПЕРГРАФА

Д. Н. Тяпкин 1, *, Д. А. Шабанов 2, **

1 Национальный исследовательский университет “Высшая школа экономики”, факультет компьютерных наук; Московский физико-технический институт, лаборатория комбинаторных и геометрических структур
Москва, Россия

2 Московский физико-технический институт, лаборатория комбинаторных и геометрических структур; Национальный исследовательский университет “Высшая школа экономики”, факультет компьютерных наук
Москва, Россия

* E-mail: dtyapkin@hse.ru
** E-mail: shabanov.da@mipt.ru

Поступила в редакцию 30.03.2023
После доработки 05.05.2023
Принята к публикации 20.05.2023

Аннотация

В работе исследуется структура множества полноцветных раскрасок в три цвета у случайного гиперграфа в равномерной модели $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 г.

Ключевые слова: случайный гиперграф, раскраски гиперграфов, полноцветные раскраски, шаттеринг

Список литературы

  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 $k$-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 $k$-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

Дополнительные материалы отсутствуют.

Инструменты

следующая статья выпуска предыдущая статья выпуска содержание выпуска

Доклады Российской академии наук. Математика, информатика, процессы управления

Архивы выпусков Информация о журнале Отправить рукопись в журнал