Benny Sudakov

Three problems on 3-chromatic intersecting hypergraphs

The study of non-2-colorable hypergraphs has a long history going back almost 60 years to the famous problem
of Erdos and Hajnal, who asked for the minimum number of edges in such a k-uniform hypergraph. In 1973 Erdos
and Lovasz further asked what happens if in addition to non-2-colorability one requires the hypergraph to be
intersecting. Their seminal paper, which introduced the local lemma, contains three intriguing problems on
the properties of 3-chromatic intersecting hypergraphs. Despite these problems being reiterated several times
over the years by Erdos and other researchers, remarkably they withstood any progress up until now. In
this talk, we prove that in any 3-chromatic intersecting k-uniform hypergraph there are at least k^(1/2-o(1))
different intersection sizes among pairs of edges. This proves a conjecture of Erdos and Lovasz in a strong
form and substantially improves their previously best bound of at least 3 different intersection sizes. Joint work with M. Bucic and S. Glock.