Logo
All Random Solved Random Open
OPEN
Let $m=m(n,k)$ be minimal such that in any collection of sets $A_1,\ldots,A_m\subseteq \{1,\ldots,n\}$ there must exist a sunflower of size $k$ - that is, some collection of $k$ of the $A_i$ which pairwise have the same intersection.

Estimate $m(n,k)$, or even better, give an asymptotic formula.

Related to [536] and [856]. In [Er70] Erdős asks this in the equivalent formulation with intersection replaced by union.

This is sometimes known as the weak sunflower problem (see [20] for the strong sunflower problem).

When $k=3$ this is strongly connected to the cap set problem (finding the maximal size of subsets of $\mathbb{F}_3^n$ with no three-term arithmetic progressions), as observed by Alon, Shpilka, and Umans [ASU13]). Naslund and Sawin [NaSa17] have proved that \[m(n,3) \leq (3/2^{2/3})^{(1+o(1))n}.\]

Additional thanks to: Noga Alon