ON THE STRUCTURE OF THE SET OF PANCHROMATIC COLORINGS OF A RANDOM HYPERGRAPH

Cover Page

Cite item

Full Text

Open Access Open Access
Restricted Access Access granted
Restricted Access Subscription Access

Abstract

The paper deals with the structure of the set of panchromatic colorings with three colors of a random hypergraph in the uniform model \(H(n,k,m)\). It is well known that the property of the existence of a panchromatic coloring with given number of colors r has the sharp threshold, i.e. there exists the threshold value \({{\hat {m}}_{r}} = {{\hat {m}}_{r}}(n)\) such that for any \(\varepsilon > 0\), if \(m\;\leqslant \;(1 - \varepsilon ){{\hat {m}}_{r}}\) then the random hypergraph \(H(n,k,m)\) admits this coloring with probability tending to 1, but if \(m\; \geqslant \;(1 + \varepsilon ){{\hat {m}}_{r}}\) then, vice versa, it does not admit this coloring with probability tending to 1. We study the algorithmic threshold for the property of panchromatic coloring with three colors and prove that if the parameter m is slightly less than \({{\widehat m}_{3}}\), then the set of panchromatic 3-colorings of \(H(n,k,m)\) although it is not empty with a probability tending to 1, but at the same time it obeys the shattering effect, first described in the work of D. Achlioptas and A. Coja-Oghlan in 2008.

About the authors

D. N. Tyapkin

National Research University “Higher School of Economics”, Faculty of Computer Science, Moscow Institute of Physics
and Technology, Laboratory of Combinatorial and Geometric Structures

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

D. A. Shabanov

Moscow Institute of Physics and Technology, Laboratory of Combinatorial and Geometric Structures, National Research University “Higher School of Economics”, Faculty of Computer Science

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

References

  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

Supplementary files

Supplementary Files
Action
1. JATS XML
Download

Copyright (c) 2023 Д.Н. Тяпкин, Д.А. Шабанов