The intersection spectrum of 3-chromatic intersecting hypergraphs

Matija Bucić, Stefan Glock, Benny Sudakov

Research output: Contribution to journalArticlepeer-review


For a hypergraph (Formula presented.), define its intersection spectrum (Formula presented.) as the set of all intersection sizes (Formula presented.) of distinct edges (Formula presented.). In their seminal paper from 1973 which introduced the local lemma, Erdős and Lovász asked: how large must the intersection spectrum of a (Formula presented.) -uniform 3-chromatic intersecting hypergraph be? They showed that such a hypergraph must have at least three intersection sizes, and conjectured that the size of the intersection spectrum tends to infinity with (Formula presented.). Despite the problem being reiterated several times over the years by Erdős and other researchers, the lower bound of three intersection sizes has remarkably withstood any improvement until now. In this paper, we prove the Erdős–Lovász conjecture in a strong form by showing that there are at least (Formula presented.) intersection sizes. Our proof consists of a delicate interplay between Ramsey-type arguments and a density increment approach.

Original languageEnglish (US)
Pages (from-to)680-690
Number of pages11
JournalProceedings of the London Mathematical Society
Issue number5
StatePublished - May 2022

All Science Journal Classification (ASJC) codes

  • General Mathematics


Dive into the research topics of 'The intersection spectrum of 3-chromatic intersecting hypergraphs'. Together they form a unique fingerprint.

Cite this