Document Open Access Logo

Improved Bounds for Coloring Locally Sparse Hypergraphs

Author Fotis Iliopoulos

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2021.39.pdf
  • Filesize: 0.64 MB
  • 16 pages

Document Identifiers

Author Details

Fotis Iliopoulos
  • Institute for Advanced Study, Princeton, NJ, USA
  • Princeton University, NJ, USA

Funding

This material is based upon work directly supported by the IAS Fund for Math and indirectly supported by the National Science Foundation Grant No. CCF-1900460. Any opinions, findings and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation. This work is also supported by the Simons Collaboration on Algorithms and Geometry

Acknowledgements

The author is grateful to Dimitris Achlioptas, Irit Dinur and anonymous reviewers for detailed comments and feedback.

Cite AsGet BibTex

Fotis Iliopoulos. Improved Bounds for Coloring Locally Sparse Hypergraphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 39:1-39:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2021.39

Abstract

We show that, for every k ≥ 2, every k-uniform hypergaph of degree Δ and girth at least 5 is efficiently (1+o(1))(k-1) (Δ / ln Δ)^{1/(k-1)}-list colorable. As an application we obtain the currently best deterministic algorithm for list-coloring random hypergraphs of bounded average degree.

Subject Classification

ACM Subject Classification
  • Theory of computation → Generating random combinatorial structures
  • Theory of computation → Pseudorandomness and derandomization
  • Theory of computation → Random search heuristics
  • Theory of computation → Random network models
Keywords
  • hypergaph coloring
  • semi-random method
  • locally sparse
  • random hypergraphs

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Dimitris Achlioptas and Amin Coja-Oghlan. Algorithmic barriers from phase transitions. In 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, October 25-28, 2008, Philadelphia, PA, USA, pages 793-802. IEEE Computer Society, 2008. URL: https://doi.org/10.1109/FOCS.2008.11.
  2. Dimitris Achlioptas, Fotis Iliopoulos, and Alistair Sinclair. Beyond the lovász local lemma: Point to set correlations and their algorithmic applications. In David Zuckerman, editor, 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9-12, 2019, pages 725-744. IEEE Computer Society, 2019. URL: https://doi.org/10.1109/FOCS.2019.00049.
  3. Dimitris Achlioptas and Michael Molloy. The analysis of a list-coloring algorithm on a random graph. In Proceedings 38th Annual Symposium on Foundations of Computer Science, pages 204-212. IEEE, 1997. Google Scholar
  4. Miklós Ajtai, János Komlós, Janos Pintz, Joel Spencer, and Endre Szemerédi. Extremal uncrowded hypergraphs. Journal of Combinatorial Theory, Series A, 32(3):321-335, 1982. Google Scholar
  5. Noga Alon and Michael Krivelevich. The concentration of the chromatic number of random graphs. Combinatorica, 17(3):303-313, 1997. Google Scholar
  6. Noga Alon, Michael Krivelevich, and Benny Sudakov. List coloring of random and pseudo-random graphs. Combinatorica, 19(4):453-472, 1999. Google Scholar
  7. Peter Ayre, Amin Coja-Oghlan, and Catherine Greenhill. Hypergraph coloring up to condensation. Random Structures & Algorithms, 54(4):615-652, 2019. Google Scholar
  8. Tom Bohman, Alan Frieze, and Dhruv Mubayi. Coloring h-free hypergraphs. Random Structures & Algorithms, 36(1):11-25, 2010. Google Scholar
  9. Karthekeyan Chandrasekaran, Navin Goyal, and Bernhard Haeupler. Deterministic algorithms for the Lovász local lemma. SIAM J. Comput., 42(6):2132-2155, 2013. URL: https://doi.org/10.1137/100799642.
  10. Ewan Davies, Ross J Kang, François Pirot, and Jean-Sébastien Sereni. An algorithmic framework for coloring locally sparse graphs. arXiv preprint arXiv:2004.07151, 2020. Google Scholar
  11. Paul Erdős and László Lovász. Problems and results on 3-chromatic hypergraphs and some related questions. In Infinite and finite sets (Colloq., Keszthely, 1973; dedicated to P. Erdős on his 60th birthday), Vol. II, pages 609-627. Colloq. Math. Soc. János Bolyai, Vol. 10. North-Holland, Amsterdam, 1975. Google Scholar
  12. Paul Erdös and Joel Spencer. Lopsided Lovász local lemma and latin transversals. Discrete Applied Mathematics, 30(2-3):151-154, 1991. URL: https://doi.org/10.1016/0166-218X(91)90040-4.
  13. Alan Frieze and Michał Karoński. Introduction to random graphs. Cambridge University Press, 2016. Google Scholar
  14. Alan Frieze and Dhruv Mubayi. Coloring simple hypergraphs. Journal of Combinatorial Theory, Series B, 103(6):767-794, 2013. Google Scholar
  15. Marylou Gabrié, Varsha Dani, Guilhem Semerjian, and Lenka Zdeborová. Phase transitions in the q-coloring of random hypergraphs. Journal of Physics A: Mathematical and Theoretical, 50(50):505002, 2017. Google Scholar
  16. A. Johansson. Asympotic choice number for triangle free graphs, 1996. Google Scholar
  17. A. Johansson. The choice number of sparse graphs. Unpublished manuscript, 1996. Google Scholar
  18. Jeff Kahn. Asymptotics of the chromatic index for multigraphs. Journal of Combinatorial Theory, Series B, 68(2):233-254, 1996. Google Scholar
  19. Jeff Kahn. Asymptotics of the list-chromatic index for multigraphs. Random Structures & Algorithms, 17(2):117-156, 2000. Google Scholar
  20. Jeong Han Kim. On Brooks' theorem for sparse graphs. Combinatorics, Probability and Computing, 4(2):97-132, 1995. Google Scholar
  21. János Komlós, János Pintz, and Endre Szemerédi. A lower bound for heilbronn’s problem. Journal of the London Mathematical Society, 2(1):13-24, 1982. Google Scholar
  22. Alexandr Kostochka, Dhruv Mubayi, Vojtěch Rödl, and Prasad Tetali. On the chromatic number of set systems. Random Structures & Algorithms, 19(2):87-98, 2001. Google Scholar
  23. Michael Krivelevich and Benny Sudakov. The chromatic numbers of random hypergraphs. Random Structures & Algorithms, 12(4):381-403, 1998. Google Scholar
  24. Hanno Lefmann. Sparse parity-check matrices over GF (q). Combinatorics, Probability and Computing, 14(1-2):147-169, 2005. Google Scholar
  25. Tomasz Łuczak. The chromatic number of random graphs. Combinatorica, 11(1):45-54, 1991. Google Scholar
  26. Michael Molloy. The list chromatic number of graphs with small clique number. Journal of Combinatorial Theory, Series B, 134:264-284, 2019. Google Scholar
  27. Michael Molloy and Bruce Reed. A bound on the total chromatic number. Combinatorica, 18(2):241-280, 1998. Google Scholar
  28. Michael Molloy and Bruce Reed. Graph colouring and the probabilistic method, volume 23 of Algorithms and Combinatorics. Springer-Verlag, Berlin, 2002. Google Scholar
  29. Robin A. Moser and Gábor Tardos. A constructive proof of the general Lovász local lemma. J. ACM, 57(2):Art. 11, 15, 2010. URL: https://doi.org/10.1145/1667053.1667060.
  30. Michel Talagrand. Concentration of measure and isoperimetric inequalities in product spaces. Publications Mathématiques de l'Institut des Hautes Etudes Scientifiques, 81(1):73-205, 1995. Google Scholar
  31. Van H Vu. On the choice number of random hypergraphs. Combinatorics Probability and Computing, 9(1):79-95, 2000. Google Scholar
  32. Van H Vu. A general upper bound on the list chromatic number of locally sparse graphs. Combinatorics, Probability and Computing, 11(1):103-111, 2002. Google Scholar
  33. Lenka Zdeborová and Florent Krzakala. Phase transitions in the coloring of random graphs. Physical Review E, 76(3):031131, 2007. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact