Property B: Two-Coloring Non-Uniform Hypergraphs

Authors Jaikumar Radhakrishnan, Aravind Srinivasan



PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2021.31.pdf
  • Filesize: 0.54 MB
  • 8 pages

Document Identifiers

Author Details

Jaikumar Radhakrishnan
  • School of Technology and Computer Science, Tata Institute of Fundamental Research, Mumbai, India
Aravind Srinivasan
  • Department of Computer Science and UMIACS, University of Maryland at College Park, MD, USA

Acknowledgements

We thank the reviewers of the current and previous versions of this paper for their constructive suggestions that helped us correct some errors and improve the presentation.

Cite AsGet BibTex

Jaikumar Radhakrishnan and Aravind Srinivasan. Property B: Two-Coloring Non-Uniform Hypergraphs. In 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 213, pp. 31:1-31:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.FSTTCS.2021.31

Abstract

The following is a classical question of Erdős (Nordisk Matematisk Tidskrift, 1963) and of Erdős and Lovász (Colloquia Mathematica Societatis János Bolyai, vol. 10, 1975). Given a hypergraph ℱ with minimum edge-size k, what is the largest function g(k) such that if the expected number of monochromatic edges in ℱ is at most g(k) when the vertices of ℱ are colored red and blue randomly and independently, then we are guaranteed that ℱ is two-colorable? Duraj, Gutowski and Kozik (ICALP 2018) have shown that g(k) ≥ Ω(log k). On the other hand, if ℱ is k-uniform, the lower bound on g(k) is much higher: g(k) ≥ Ω(√{k / log k}) (Radhakrishnan and Srinivasan, Rand. Struct. Alg., 2000). In order to bridge this gap, we define a family of locally-almost-uniform hypergraphs, for which we show, via the randomized algorithm of Cherkashin and Kozik (Rand. Struct. Alg., 2015), that g(k) can be much higher than Ω(log k), e.g., 2^Ω(√{log k}) under suitable conditions.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Combinatoric problems
Keywords
  • Hypergraph coloring
  • Propery B

Metrics

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

References

  1. Dimitris Achlioptas, Jeong Han Kim, Michael Krivelevich, and Prasad Tetali. Two-coloring random hypergraphs. Random Struct. Algorithms, 20(2):249-259, 2002. URL: https://doi.org/10.1002/rsa.997.
  2. J. Beck. On 3-chromatic hypergraphs. Discrete Mathematics, 24:127-137, 1978. Google Scholar
  3. F. Bernstein. Zur Theorie der trigonometrische Reihen. Leipz. Ber., 60:325-328, 1908. Google Scholar
  4. Amey Bhangale. Np-hardness of coloring 2-colorable hypergraph with poly-logarithmically many colors. In Ioannis Chatzigiannakis, Christos Kaklamanis, Dániel Marx, and Donald Sannella, editors, 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic, volume 107 of LIPIcs, pages 15:1-15:11. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.ICALP.2018.15.
  5. Danila D. Cherkashin and Jakub Kozik. A note on random greedy coloring of uniform hypergraphs. Random Struct. Algorithms, 47(3):407-413, 2015. URL: https://doi.org/10.1002/rsa.20556.
  6. Lech Duraj, Grzegorz Gutowski, and Jakub Kozik. A note on two-colorability of nonuniform hypergraphs. In Ioannis Chatzigiannakis, Christos Kaklamanis, Dániel Marx, and Donald Sannella, editors, 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic, volume 107 of LIPIcs, pages 46:1-46:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.ICALP.2018.46.
  7. P. Erdős. On a combinatorial problem, I. Nordisk Matematisk Tidskrift, 11:5-10, 1963. Google Scholar
  8. P. Erdős. On a combinatorial problem, II. Acta Mathematica of the Hungarian Academy of Sciences, 15:445-447, 1964. Google Scholar
  9. P. Erdős and L. 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), volume II, pages 609-627. North-Holland, Amsterdam, 1975. Volume 10 of Colloquia Mathematica Societatis János Bolyai. Google Scholar
  10. Jaikumar Radhakrishnan and Aravind Srinivasan. Improved bounds and algorithms for hypergraph 2-coloring. Random Struct. Algorithms, 16(1):4-32, 2000. URL: https://doi.org/10.1002/(SICI)1098-2418(200001)16:1%3C4::AID-RSA2%3E3.0.CO;2-2.
  11. Dmitry A. Shabanov. Around erdős-lovász problem on colorings of non-uniform hypergraphs. Discret. Math., 338(11):1976-1981, 2015. URL: https://doi.org/10.1016/j.disc.2015.04.017.
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