2026-08-05T21:43:29Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14158 2024-03-06T10:53:37Z ddc:004 open_access

Improving Gebauer’s Construction of 3-Chromatic Hypergraphs with Few Edges Kozik, Jakub Property B Hypergraph Coloring Deterministic Constructions 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})}. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jakub Kozik 2021 Is Part Of LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2021.89 urn:nbn:de:0030-drops-141587 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.89 eng https://creativecommons.org/licenses/by/4.0/legalcode