Three problems on 3-chromatic intersecting hypergraphs

Abstract: 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

combinatoricsprobability

Audience: researchers in the topic

Extremal and probabilistic combinatorics webinar

Series comments: We've added a password: concatenate the 6 first prime numbers (hence obtaining an 8-digit password).