TY - CHAP

T1 - The Intersection Spectrum of 3-Chromatic Intersecting Hypergraphs

AU - Bucić, Matija

AU - Glock, Stefan

AU - Sudakov, Benny

N1 - Funding Information:
Research supported in part by Dr. Max Rössler, the Walter Haefner Foundation and the ETH Zürich Foundation. Research supported in part by SNSF grant 200021 196965.
Funding Information:
Research supported in part by Dr. Max R?ssler, the Walter Haefner Foundation and the ETH Z?rich Foundation. Research supported in part by SNSF grant 200021 196965.
Publisher Copyright:
© 2021, The Author(s), under exclusive license to Springer Nature Switzerland AG.

PY - 2021

Y1 - 2021

N2 - For a hypergraph H, define its intersection spectrum I(H) as the set of all intersection sizes | E∩ F| of distinct edges E, F∈ E(H). 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 k-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 k. 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 k1 / 2 - o ( 1 ) intersection sizes. In this extended abstract we sketch a simpler argument which gives slightly weaker bound of k1 / 3 - o ( 1 ). Our proof consists of a delicate interplay between Ramsey type arguments and a density increment approach.

AB - For a hypergraph H, define its intersection spectrum I(H) as the set of all intersection sizes | E∩ F| of distinct edges E, F∈ E(H). 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 k-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 k. 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 k1 / 2 - o ( 1 ) intersection sizes. In this extended abstract we sketch a simpler argument which gives slightly weaker bound of k1 / 3 - o ( 1 ). Our proof consists of a delicate interplay between Ramsey type arguments and a density increment approach.

KW - Intersecting hypergraphs

KW - Intersection spectrum

KW - Property B

UR - http://www.scopus.com/inward/record.url?scp=85114102478&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85114102478&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-83823-2_22

DO - 10.1007/978-3-030-83823-2_22

M3 - Chapter

AN - SCOPUS:85114102478

T3 - Trends in Mathematics

SP - 136

EP - 141

BT - Trends in Mathematics

PB - Springer Science and Business Media Deutschland GmbH

ER -