Benny Sudakov


Three problems on 3-chromatic intersecting hypergraphs

Combinatorics Seminar

30th March 2021, 11:00 am – 12:00 pm
Virtual (online) Zoom seminar; a link will be sent to the Bristol Combinatorics Seminar mailing list, the week before the seminar.

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.

Comments are closed.