$$

Adapted from Anup Rao’s talk at the UW Theory Seminar.

Theorem (Alweiss–Lovett–Wu–Zhang).¹ Any family of $w$-sets that doesn’t have a $k$-sunflower must have at most $(k\log w{)}^{O(w)}$ sets.

The bound has been slightly improved to $O(k\log w{)}^w$.²

Strategy

Let $\mathcal{F}=\{S_1,\dots ,S_l\}\subseteq (\genfrac{}{}{0ex}{}{[n]}{w})$ be the family of sets, and let’s call $w$ the “width”.

The original sunflower lemma of Erdős and Rado uses the fact that $\mathcal{F}$ must either have

• $k$ disjoint sets (which is a $k$-sunflower),
• or one element $i$ that’s contained in a $\ge \frac{1}{kw}$ fraction ${\mathcal{F}}^{\prime }\subseteq \mathcal{F}$ of the sets (in which case you recurse on ${\mathcal{F}}^{\prime }$, with $i$ removed).

The recursion decreases the width by one, and when the width falls to $0$ you can only have one set remaining. So if you start out with $|\mathcal{F}|>(kw{)}^w$ sets, you must find a $k$-sunflower before the width falls to $1$.

The improved sunflower lemma generalizes the “one element” part: instead of trying to find a single element $i\in [n]$ that’s in a $\ge \frac{1}{r}$ fraction of the sets for some $r$, more generally try to find a set $I\subseteq [n]$ that is included in a $\ge \frac{1}{r^{|I|}}$ fraction of the sets. In either case, the point is that decreasing the width by one “costs a factor $r$”, so if you start out with $l>r^w$ sets, you must find a $k$-sunflower before the width falls to $1$.

To still get a result, we need to show that if there is no such $I$, then $\mathcal{F}$ must have $k$ disjoint sets. That is, let’s say $\mathcal{F}$ is $r$-spread in the sense that no set $I\subseteq [n]$ of elements is included in a $\frac{1}{r^{|I|}}$ fraction of the sets. Then we need to show:

Lemma. There is some $r\le \mathrm{poly}(k,\log w)$ such that any $r$-spread $\mathcal{F}$ contains $k$ disjoint sets.

Encoding argument

TODO:

• outline Rao’s “coding for sunflowers” proof
• does this result give an improvement on SBI’s Small restrictions switching lemma?
• think again about remark that “Tribes is not pseudorandom enough” (it’s not spread), and see if this inspires you about better structural results for w-DNFs with small n

1. Ryan Alweiss, Shachar Lovett, Kewen Wu, Jiapeng Zhang, “Improved bounds on the sunflower lemma”. ↩

2. Tolson Bell, Suchakree Chueluecha, Lutz Warnke, “Note on sunflowers”. ↩