TAU Combinatorics Seminar

TAU Combinatorics Seminar 2020/21

When: Sunday, November 8, 10am Speaker: Matija Bucić, ETH Zurich Title: The intersection spectrum of 3-chromatic intersecting hypergraphs

Abstract:

For a hypergraph $H$, define its intersection spectrum $I(H)$ as the set of all intersection sizes $|E\cap F|$ of distinct edges $E,F\in 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. We prove the Erdős-Lovász conjecture in a strong form by showing that there are at least $k^{1/2-o(1)}$ intersection sizes.

This is joint work with Stefan Glock and Benny Sudakov.