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 -