Asymptotic Improvement of the Sunflower Bound

Abstract

A sunflower with a core $Y$ is a family $\mathcal{B}$ of sets such that $U\cap U^{\prime }=Y$ for each two different elements $U$ and $U^{\prime }$ in $\mathcal{B}$. The well-known sunflower lemma states that a given family $\mathcal{F}$ of sets, each of cardinality at most $s$, includes a sunflower of cardinality $k$ if $|\mathcal{F}|>(k-1{)}^{s}s!$. Since Erdös 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 $\mathcal{F}$ includes a sunflower of cardinality $k$ if \[ |{\cal F|} \ge \left( \sqrt{10} -2 \right)^2 \left[ k \cdot \min \left( \frac{1}{\sqrt{10}-2}, \frac{c}{\log \min(k, s)} \right) \right]^s s!, \] for a constant $c>0$, and any $k\ge 2$ and $s\ge 2$. 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 {\left[O\left(\frac{1}{\log s}\right)\right]}^s$, achieving the reduction ratio of ${\left[O\left(\frac{1}{\log s}\right)\right]}^s$. Also any $\mathcal{F}$ of cardinality at least ${\left(\sqrt{10}-2\right)}^2{\left(\frac{k}{\sqrt{10}-2}\right)}^{s}s!$ includes a sunflower of cardinality $k$, where $\frac{1}{\sqrt{10}-2}=0.8603796\dots$. 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.

arXiv comment13 pages, no figures