Improved Bound on Sets Including No Sunflower with Three Petals

Abstract

A sunflower with $k$ petals, or $k$-sunflower, is a family of $k$ sets every two of which have a common intersection. Known since 1960, the sunflower conjecture states that a family $\mathcal{F}$ of sets each of cardinality $m$ includes a $k$-sunflower if $|\mathcal{F}|\ge c_k^m$ for some $c_k\in {\mathbb{R}}_{>0}$ depending only on $k$. The case $k=3$ of the conjecture was especially emphasized by Erdös, for which Kostochka's bound $cm!{\left(\frac{\log \log \log m}{\log \log m}\right)}^m$ on $|\mathcal{F}|$ without a 3-sunflower had been the best-known since 1997 until the recent development to update it to $c\log m$. This paper proves with an entirely different combinatorial approach that $\mathcal{F}$ includes three mutually disjoint sets if it satisfies the $\Gamma \left(c{m}^{\frac{1}{2}+\delta }\right)$-condition for any given $\delta \in (0,1/2)$. Here $c$ is a constant depending only on $\delta$, and the $\Gamma$-condition refers to \[ | \left\{ U~:~ U \in {\mathcal F} \textrm{~and~} S \subset U \right\}| < \left( c m^{\frac{1}{2}+ δ} \right)^{-|S|} |{\mathcal F}|, \] for every nonempty set $S$. This poses an alternative proof of the 3-sunflower bound ${\left(c{m}^{\frac{1}{2}+\delta }\right)}^m$.

25 pages. The 2nd version contained a flaw in the induction step of the main proof. The current one fixes it also proving a slightly stronger claim than the existence of the 3-sunflower: if the Γ-condition is met, the family F includes 3 mutually disjoint sets

Cited by in corpus (1)

• Improved bounds for the sunflower lemma