EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Intersecting hypergraphs with large cover number

Matija Bucić, Vanshika Jain, Varun Sivashankar

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).

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →