Simons Collaboration on Algorithms and Geometry Monthly Meeting, February 2021

Shachar Lovett
The Sunflower Conjecture

The sunflower conjecture is a famous open problem in combinatorics, asked by Erdos and Rado in 1960. A sunflower is a collection of sets with the same pairwise intersection pattern. The conjecture asks if given a large enough family of sets, it must contain a sunflower. Erdos and Rado proved that this is indeed true, but they conjectured that the quantitative bounds that they showed can be improved. In the last 60 years, many applications of sunflowers were found (both in math and in CS), but the original bounds were not significantly improved. I will describe recent work that gives a significant improvement to the quantitative bounds, getting closer to the conjectured bound.

Surprisingly, the proof techniques turned out to have applications in other domains, such as random graph theory (proving the “fractional expectations conjecture” of Talagrand), and DNF compression in complexity theory. The talk will be composed of two parts:

• Part 1 – general background, general proof strategy, and connection to these other fields
• Part 2 – detailed proof

No background knowledge is assumed.

Based on joint work with Ryan Alweiss, Kewen Wu and Jiapeng Zhang.