LIPIcs.ICALP.2021.89.pdf
- Filesize: 0.64 MB
- 9 pages
Document
Improving Gebauer’s Construction of 3-Chromatic Hypergraphs with Few Edges
Author
Jakub Kozik 
-
Part of:
Volume:
48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Colloquium on Automata, Languages, and Programming (ICALP) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2021-07-02
File
Document Identifiers
Author Details
Cite AsGet BibTex
Jakub Kozik. Improving Gebauer’s Construction of 3-Chromatic Hypergraphs with Few Edges. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 89:1-89:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ICALP.2021.89
https://doi.org/10.4230/LIPIcs.ICALP.2021.89
Abstract
In 1964 Erdős proved, by randomized construction, that the minimum number of edges in a k-graph that is not two colorable is O(k² 2^k). To this day, it is not known whether there exist such k-graphs with smaller number of edges. Known deterministic constructions use much larger number of edges. The most recent one by Gebauer requires 2^{k+Θ(k^{2/3})} edges. Applying a derandomization technique we reduce that number to 2^{k+Θ̃(k^{1/2})}.
Subject Classification
ACM Subject Classification
- Mathematics of computing → Hypergraphs
- Mathematics of computing → Probabilistic algorithms
- Theory of computation → Pseudorandomness and derandomization
Keywords
- Property B
- Hypergraph Coloring
- Deterministic Constructions
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: https://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: https://doi.org/10.1002/rsa.20556.
-
Paul Erdős. On a combinatorial problem. II. Acta Mathematica Academiae Scientiarum Hungaricae, 15:445-447, 1964.
- Ofer Gabber and Zvi Galil. Explicit constructions of linear-sized superconcentrators. J. Comput. System Sci., 22(3):407-420, 1981. Special issued dedicated to Michael Machtey. URL: https://doi.org/10.1016/0022-0000(81)90040-4.
- Heidi Gebauer. On the construction of 3-chromatic hypergraphs with few edges. Journal of Combinatorial Theory. Series A, 120(7):1483-1490, 2013. URL: https://doi.org/10.1016/j.jcta.2013.04.007.
- Nathan Linial, Michael Luby, Michael Saks, and David Zuckerman. Efficient construction of a small hitting set for combinatorial rectangles in high dimension. Combinatorica, 17(2):215-234, 1997. URL: https://doi.org/10.1007/BF01200907.
-
G. A. Margulis. Explicit constructions of expanders. Problemy Peredači Informacii, 9(4):71-80, 1973.
- Jaikumar Radhakrishnan and Aravind Srinivasan. Improved bounds and algorithms for hypergraph 2-coloring. Random Structures & Algorithms, 16(1):4-32, 2000. URL: https://doi.org/10.1002/(SICI)1098-2418(200001)16:1<4::AID-RSA2>3.3.CO;2-U.