Problem 20

Erdős Problem #20: declared status 'open'. Formalized: yes. Let $f(n,k)$ be minimal such that every family $\mathcal{F}$ of $n$-uniform sets with $\lvert \mathcal{F}\rvert \geq f(n,k)$ contains a $k$-sunflower. Is it true that$$f(n,k) < c_k^n$$for some constant $c_k>0$? Current best: Kostochka [Ko97] improved this slightly (in particular establishing an upper bound of $o(n!)$, for which Erd\H{o}s awarded him the consolation prize of \$100), but the bound stood at$n^{(1+o(1))n} for a long time until Alweiss, Lovett, Wu, and Zhang \cite{ALWZ20} proved\[f(n,k) < (Ck\log n\log\log n)^n\]for some constant C>1. This was refined slightly, independently by Rao \cite{Ra20}, Frankston, Kahn, Narayanan, and Park \cite{FKNP19}, and Bell, Chueluecha, and Warnke \cite{BCW21}, leading to the current record of\[f(n,k) < (Ck\log n)^n\]for some constant C>1$. Prize:$1000. OEIS: A332077. Tags: combinatorics.