LIPIcs.ICALP.2018.46.pdf
- Filesize: 451 kB
- 13 pages
Document
A Note on Two-Colorability of Nonuniform Hypergraphs
Authors
Grzegorz Gutowski 
,
-
Part of:
Volume:
45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Colloquium on Automata, Languages, and Programming (ICALP) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2018-07-04
File
Document Identifiers
Author Details
Cite As Get BibTex
Lech Duraj, Grzegorz Gutowski, and Jakub Kozik. A Note on Two-Colorability of Nonuniform Hypergraphs. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 46:1-46:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.ICALP.2018.46
Abstract
For a hypergraph H, let q(H) denote the expected number of monochromatic edges when the color of each vertex in H is sampled uniformly at random from the set of size 2. Let s_{min}(H) denote the minimum size of an edge in H. Erdös asked in 1963 whether there exists an unbounded function g(k) such that any hypergraph H with s_{min}(H) >=slant k and q(H) <=slant g(k) is two colorable. Beck in 1978 answered this question in the affirmative for a function g(k) = Theta(log^* k). We improve this result by showing that, for an absolute constant delta>0, a version of random greedy coloring procedure is likely to find a proper two coloring for any hypergraph H with s_{min}(H) >=slant k and q(H) <=slant delta * log k.
Subject Classification
ACM Subject Classification
- Mathematics of computing → Combinatorics
- Mathematics of computing → Hypergraphs
- Mathematics of computing → Probabilistic algorithms
Keywords
- Property B
- Nonuniform Hypergraphs
- Hypergraph Coloring
- Random Greedy Coloring
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- József Beck. On 3-chromatic hypergraphs. Discrete Mathematics, 24(2):127-137, 1978. URL: http://dx.doi.org/10.1016/0012-365X(78)90191-7.
- Danila D. Cherkashin and Jakub Kozik. A note on random greedy coloring of uniform hypergraphs. Random Structures &Algorithms, 47(3):407-413, 2015. URL: http://dx.doi.org/10.1002/rsa.20556.
-
Paul Erdős. On a combinatorial problem. Nordisk Matematisk Tidskrift, 11:5-10, 40, 1963.
-
Paul Erdős. On a combinatorial problem. II. Acta Mathematica Academiae Scientiarum Hungaricae, 15:445-447, 1964.
-
Paul Erdős and András Hajnal. On a property of families of sets. Acta Mathematica Academiae Scientiarum Hungaricae, 12:87-123, 1961.
-
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, volume 10 of Colloquia Mathematica Societatis János Bolyai, pages 609-627. North-Holland, Amsterdam, 1975.
- Heidi Gebauer. On the construction of 3-chromatic hypergraphs with few edges. Journal of Combinatorial Theory. Series A, 120(7):1483-1490, 2013. URL: http://dx.doi.org/10.1016/j.jcta.2013.04.007.
-
László Lovász. Coverings and coloring of hypergraphs. In Proceedings of the Fourth Southeastern Conference on Combinatorics, Graph Theory, and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1973), pages 3-12, 1973.
- Linyuan Lu. On a problem of Erdős and Lovász on coloring non-uniform hypergraphs, 2008. URL: http://people.math.sc.edu/lu/papers/propertyB.pdf.
- Jaikumar Radhakrishnan and Aravind Srinivasan. Improved bounds and algorithms for hypergraph 2-coloring. Random Structures &Algorithms, 16(1):4-32, 2000. URL: http://dx.doi.org/10.1002/(SICI)1098-2418(200001)16:1<4::AID-RSA2>3.3.CO;2-U.
- Dmitry A. Shabanov. Around Erdős-Lovász problem on colorings of non-uniform hypergraphs. Discrete Mathematics, 338(11):1976-1981, 2015. URL: http://dx.doi.org/10.1016/j.disc.2015.04.017.