Intersecting hypergraphs with large cover number
Combinatorial Theory · 2026
DOI: 10.5070/c6.69920 ↗Kurz gefasst
Fachartikel in der Zeitschrift Combinatorial Theory, 2026. Verfasst von Matija Bucić und 2 weiteren Autor:innen. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).
Abstract (Originalsprache)
In their famous 1974 paper introducing the local lemma, Erdős and Lovász posed a question—later referred to by Erdős as one of his three favorite open problems: What is the minimum number of edges in an \( r \)-uniform, intersecting hypergraph with cover number \( r \)? This question was solved up to a constant factor in Kahn's remarkable 1994 paper. More recently, motivated by applications to Bollobás' "power of many colours" problem, Alon, Bucić, Christoph, and Krivelevich introduced a natural generalization by imposing a space constraint that limits the hypergraph to use only \(n\) vertices. In this note, we settle this question asymptotically, up to a logarithmic factor in \(n/r\) in the exponent, for the entire range. Mathematics Subject Classifications: 05D05 Keywords: Hypergraphs, cover number, intersecting
Zitieren
APA
Bucić, M., Jain, V., & Sivashankar, V. (2026). Intersecting hypergraphs with large cover number. Combinatorial Theory. https://doi.org/10.5070/c6.69920
Vancouver
Bucić M, Jain V, Sivashankar V. Intersecting hypergraphs with large cover number. Combinatorial Theory. 2026. doi:10.5070/c6.69920
BibTeX
@article{Buci2026,
author = {Bucić, Matija and Jain, Vanshika and Sivashankar, Varun},
title = {Intersecting hypergraphs with large cover number},
journal = {Combinatorial Theory},
year = {2026},
doi = {10.5070/c6.69920}
}
EUVIMED