Back to TGINF

An Improved Sunflower Lemma

Speaker: Jiapeng
Title: An Improved Sunflower Lemma
Date: 16 Sep 2019 5:30pm-7:00pm
Location: Maxwell-Dworkin 123
Food: Thai

Abstract: The sunflower structure was introduced by Erdos-Rado. It has profound a lof of applications in combinatorics and theoretical computer science. Erdos-Rado proved any family of sets of size $w$, with at least about $w^w$ sets, must contain a sunflower. The sunflower conjecture speculates the upper bound can be improved to $c^w$ for some constant $c$. In this talk, we improve the bound to about $(\log w)^w$. Our proof is based on an encoding argument.