Computer Science/Discrete Mathematics Seminar I

An improved sunflower bound.

A sunflower with $r$ petals is a collection of $r$ sets so that the intersection of each pair is equal to the intersection of all. Erdos and Rado in 1960 proved the sunflower lemma: for any fixed $r$, any family of sets of size $w$, with at least about $w^w$ sets, must contain a sunflower. The famous sunflower conjecture is that the bound on the number of sets can be improved to $c^w$ for some constant $c$. Despite much research, the best bounds until recently were all of the order of $w^{cw}$ for some constant c. In this work, we improve the bounds to about $(log w)^w$. Joint work with Ryan Alweiss, Shachar Lovett and Kewen Wu.

Date & Time

October 07, 2019 | 11:00am – 12:00pm

Location

Simonyi Hall 101

Speakers

Jiapeng Zhang

Affiliation

Harvard University