Asymptotic Improvement of the Sunflower Bound

Junichiro Fukuyama

Published 2014-08-15, updated 2014-08-19Version 2

A sunflower with a core $Y$ is a family ${\cal B}$ of sets such that $U \cap U' = Y$ for each two distinct elements $U$ and $U'$ in ${\cal B}$. The well-known sunflower lemma states that a given family ${\cal F}$ of sets, each of cardinality at most $s$, includes a sunflower of cardinality $k$ if $|{\cal F}|> (k-1)^s s!$. Since Erdos and Rado proved it in 1960, it has not been known for more than half a century whether the sunflower bound $(k-1)^s s!$ can be improved asymptotically for any $k$ and $s$. It is conjectured that it can be reduced to $c_k^s$ for some real number $c_k>0$ depending only on $k$, which is called the sunflower conjecture. This paper shows that the general sunflower bound can be indeed reduced by an exponential factor: We prove that ${\cal F}$ includes a sunflower of cardinality $k$ if \[ |{\cal F|} \ge \left( \frac{8}{7} \right)^2 \left[ k \cdot \min \left( \frac{7}{8}, \frac{c}{\log \min(k, s)} \right) \right]^s s!, \] for a constant $c>0$. For instance, whenever $k \ge s^\epsilon$ for a given constant $\epsilon \in (0,1)$, the sunflower bound is reduced from $(k-1)^s s!$ to $(k-1)^s s! \cdot O (1 / \log s )^s$, achieving the reduction ratio of $O ( 1 / \log s )^s$. Also any ${\cal F}$ of cardinality at least $(8/7)^2 (7k/8)^s s!$ includes a sunflower of cardinality $k$. Our result demonstrates that the sunflower bound can be improved by a factor of less than a small constant to the power $s$, giving hope for further update.