### 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.