The intersection spectrum of 3-chromatic intersecting hypergraphs
OPEN ACCESS
Loading...
Author / Producer
Date
2022-05
Publication Type
Journal Article
ETH Bibliography
yes
Citations
Altmetric
OPEN ACCESS
Data
Abstract
For a hypergraph H$H$, define its intersection spectrum I(H)$I(H)$ as the set of all intersection sizes |E boolean AND F|$|E\cap F|$ of distinct edges E,F is an element of E(H)$E,F\in E(H)$. In their seminal paper from 1973 which introduced the local lemma, Erdos and Lovasz asked: how large must the intersection spectrum of a k$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$k$. Despite the problem being reiterated several times over the years by Erdos and other researchers, the lower bound of three intersection sizes has remarkably withstood any improvement until now. In this paper, we prove the Erdos-Lovasz conjecture in a strong form by showing that there are at least k1/2-o(1)$k<^>{1/2-o(1)}$ intersection sizes. Our proof consists of a delicate interplay between Ramsey-type arguments and a density increment approach.
Permanent link
Publication status
published
External links
Editor
Book title
Journal / series
Volume
124 (5)
Pages / Article No.
680 - 690
Publisher
Wiley
Event
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Organisational unit
03993 - Sudakov, Benjamin / Sudakov, Benjamin
02889 - ETH Institut für Theoretische Studien / ETH Institute for Theoretical Studies
Notes
Funding
196965 - Problems in Extremal and Probabilistic Combinatorics (SNF)