By a slight abuse of notation, we say that a family is $k$-uniform if every set in it has size $\leq k$. The fundamental question is: how large can a $k$-uniform collection of sets be without containing an $\ell$-sunflower? (One could also consider the situation where we bound, not the size of the sets, but the size of the universe; this is known as the weak sunflower problem, and recently a bound like $(2-c)^n$ was proved for $k=3$ via the Croot-Lev-Pach/Ellenberg-Gijswijt progress on the cap set problem; Alon, Shpilka, and Umans had already observed that an exponential upper bound for the cap set problem implies a solution, and Naslund-Sawin made this proof explicit.)

This was first considered by Erdős and Rado [ER], who proved the following.

Erdős-Rado 1960

If $\mathcal{F}$ is a $k$-uniform collection of finite sets nd $\abs{\mathcal{F}}> (\ell-1)^kk!$ then $\mathcal{F}$ contains a $\ell$-sunflower.
Proof

We argue by induction on $k$. The case $k=1$ is trivial. For the inductive step, suppose $\mathcal{F}$ contains no $\ell$-sunflower. If we consider any $\mathcal{F}_x=\{ A \in \mathcal{F} : x \in A\}$ then by induction $\abs{\mathcal{F}_x}\leq (\ell-1)^{k-1}(k-1)!$. On the other hand, taking the union of a maximal collection of $\leq \ell-1$ disjoint sets, we can find some set $X$ of size $\leq (\ell-1)k$ such that every set in $\mathcal{F}$ contains some element of $X$, and hence
\[\abs{\mathcal{F}}\leq \sum_{x\in X}\abs{\mathcal{F}_x}\leq (\ell-1)^kk!.\]
Let $F(\ell, k)$ denote the maximal size of a collection of sets of size $\leq \ell$ without an $\ell$-sunflower, so that the Erdős-Rado bound is that \[F(\ell,k) \leq (\ell-1)^kk!.\] In particular this bound grows like $\ell^k k^{(1+o(1))k}$. How large can it be? Here is a simple construction that shows $F(\ell,k)> (\ell-1)^k$: for every function $f:[k]\to [\ell-1]$, consider \[X(f)=\{ (x,f(x)) : x \in [k]\}.\] This is a $k$-uniform family containing $(\ell-1)^k$ sets. If $X_1,\ldots,X_{\ell}$ form an $\ell$-sunflower, then for any $x\in [k]$ there must exist some indicies $1\leq i<j<\ell$ such that $f_i(x)=f_j(x)$. It follows that $(x,f_i(x))$ is in both $X_i$ and $X_j$, so must be in every $X_i$, so the value of $f$ is fixed on any $x\in[k]$, whence there must be only one set.

In 1977 Spencer [Sp] proved $F(\ell,n)\ll_\ell (1+o(1))^kk!$. In 1997 Kostochka [K] obtained, with great effort, a very modest improvement over this bound: \[F(3,n)\ll \brac{\frac{\log\log\log k}{\log\log k}}^k k!.\] In particular, this is $o(k!)$, but is still of the shape $k^{(1-o(1))k}$.

Alweiss-Lovett-Wu-Zhang 2019

There is some constant $C>1$ such that
\[F(\ell,k) \leq (C\ell^3\log k\log\log k)^k\leq \ell^{O(k)} (\log k)^{(1+o(1))k}.\]
This was quickly improved about a month or two after it was posted, first by Frankston-Kahn-Narayanan-Park [FKNP], and then an alternative proof was given by Rao [Rao1]. An alternative interpretation of Rao's proof via entropy was given in a blog post of Tao.

Frankston-Kahn-Narayanan-Park, Rao, Tao

There is some constant $C>1$ such that
\[F(\ell,n)\leq (C\ell\log k)^k.\]
Incidentally, although our focus is on the regime where $\ell=O(1)$ is fixed and $k$ is large, we note that the opposite regime where $k$ is fixed and $\ell$ is large is basically solved.

Kostochka-Rödl-Talysheva 1998 [KRT]

If $k$ is fixed and $\ell$ is large then
\[F(\ell,k)=(1+O_k(\ell^{-1/2^k}))\ell^k.\]
If $\mathcal{F}$ is a $k$-uniform family of sets and $\abs{\mathcal{F}}\geq R^k$ then there exists $X$ with $\abs{X}\leq k$ such that $\mathcal{F}'=\{ A\backslash X : X\subseteq A\in \mathcal{F}\}$ is a non-empty $(k-\abs{X})$-uniform family which is $R$-spread.

Proof

We use induction on $k$. The case $k=0$ is trivial (the family $\{\emptyset\}$ is $R$-spread for every $R$). In general, if $\mathcal{F}$ is $R$-spread we are done, and if not by definition there exists some $X\neq\emptyset$ such that $\mathcal{F}'=\{ A\backslash X \in \mathcal{F} : X\subseteq A\}$ is a non-empty $(k-\abs{X})$-uniform family with $\abs{\mathcal{F}'}> R^{k-\abs{X}}$, and we are done by induction.
In particular, if we knew that every $k$-uniform family of sets which is $R$-spread contains $\ell$ disjoint sets then we could immediately deduce that $F(\ell,k)\leq R^k$. For example, we could argue as follows. Any element $x$ is contained in at most $\abs{\mathcal{F}}/R$ of the sets. If $R>(\ell-1)k$ then we could greedily just choose $A_1,\ldots,A_\ell$ disjoint and be done. This would yield $F(\ell,k)\leq (\ell-1)^kk^k$, and is basically the Erdős-Rado argument.

The core of the recent improvements is the following.

Lemma 1

If $\mathcal{F}\subseteq 2^{[n]}$ is an $\Omega(\delta^{-1}\log k)$-spread $k$-uniform family and $\mathbf{W}\subseteq [n]$ is a uniformly random set of density $\delta$ then
\[\mathbb{P}(\mathbf{W}\textrm{ contains some }A\in\mathcal{F})\geq 1/2.\]
Given Lemma 1, deduction of the sunflower bounds is now straightforward: partition the universe randomly into $2\ell$ sets $W_1\sqcup\cdots\sqcup W_{2\ell}$, so that each part behaves like a random set with density $1/2\ell$. Provided $1/\ell \gg \log k/R$ (so in particular we can choose $R=C\ell \log k$ for some large constant $C$) we know that each $W_i$ contains some $A\in\mathcal{F}$ with probability $\geq 1/2$. Therefore the expected number of $W_i$ that contain some $A\in\mathcal{F}$ is at least $\ell$ - obviously such $A$ must be disjoint, and we are done.

How to prove Lemma 1? A naive way would be to apply the union bound: if there is no $A\in\mathcal{F}$ contained in $\mathbf{W}$, then for every $A\in \mathcal{F}$, the collection $\mathcal{G}$ of all non-empty sets disjoint from $W$ would have $\#\{B\in\mathcal{G} : B\subseteq A\}\geq 1$, whence we have \[\mathbb{P}(\mathbf{W}\textrm{ contains no }A\in\mathcal{F})\leq \bbe_W \frac{1}{\abs{\mathcal{F}}}\sum_{A\in\mathcal{F}}\#\{B\in\mathcal{G} : B\subseteq A\}\leq \frac{1}{\abs{\mathcal{F}}}\sum_{A\in\mathcal{F}}\sum_{B}1_{B\subseteq A}\mathbb{P}(B\in \mathcal{G}).\] The probability here is $(1-\delta)^{\abs{B}}$, and the average over $A\in\mathcal{F}$ is at most $R^{-\abs{B}}$. So (subtracting the contribution from $B=\emptyset$) this is at most \[(1+(1/R-\delta/R))^n-1.\] With $\delta\approx 1/2$, this grows like $n/R$ - terrible, we don't know the size of the universe! We could be slightly more careful here, and limit $\mathcal{G}$ to be subsets of some $A\in\mathcal{F}$. Heuristically, the actual size of the relevant universe grows like $\ell k$, and so size of universe of $\mathcal{G}$ is actually like $O(k)$ - in particular with $\delta=1/2$ and $R\gg Ck$ for some large $C$ we get the probability at most $1/2$ as required. This is essentially the Erdős-Rado approach, which delivers $k^{k}$ type bounds.

To do better, we will still use the union bound, but make a more refined choice of $\mathcal{G}=\mathcal{G}(\mathbf{W},\mathcal{F})$, to try and be contained in every bad $A\in\mathcal{F}$ while not have too many elements.

This is the main technical result, formulated here by Rao. This approach by Rao unifies the sunflower bounds and the recent Park-Pham proof of the Kahn-Kalai threshold conjecture, as both are easy corollaries of this result.

Rao

Let $n,k\geq 1$ be integers. Let $\mathcal{F}\subseteq 2^{[n]}$ be a $k$-uniform family. For each $W\subseteq [n]$ of size $\gg \frac{\log k}{R}n$ there is a probability distribution $\mathcal{G}(W)$ on collections of subsets of $[n]$ such that
- ($\mathcal{G}$ contains few sets of $R$-spread families) if we choose a set $W$ uniformly at random and $\mathcal{F}'$ is $R$-spread then \[\bbe_{W,\mathcal{G}(W)} \sum_{A\in\mathcal{F}'}\#\{ B\in\mathcal{G} : B\subseteq A\} < \frac{1}{2}\abs{\mathcal{F}'},\] and
- (either $W$ covers something in $\mathcal{F}$ or everything in $\mathcal{F}$ contains something in $\mathcal{G}$) for any $W$, either
- there exists some $A\in \mathcal{F}$ such that $A\subseteq W$, or
- for every $A\in\mathcal{F}$ there exists some $B\in\mathcal{G}$ such that $B\subseteq A$.

We will discuss the connection to the Kahn-Kalai threshold conjecture below.

Another thing to measure is the expectation threshold: how large does $p$ have to be before the expected number of minimal witnesses of $P$ is at least $1/2$? Call this $p_E$. Now it is trivial that $p_E\leq p_T$, since by the union bound the probability that the property is satisfied is at most the expected number of minimal witnesses. The converse is not clear, however, but would be very useful - it is often quite trivial to calculate $p_E$, via linearity of expectation, but what we really want to know is $p_T$.

They are not always equal - the classic example is the property of containing a Hamiltonian cycle. If we build a random graph on $n$ vertices, then for this property $p_E\approx 1/n$ (easy, there are about $n!$ cycles, each is in the graph with probability $p^n$), but the threshold probability is $\approx \log n/n$.

This seemed to be the worst possible though, so Kahn-Kalai conjectured that when the universe has size $n$, we have $p_T\ll (\log n)p_E$. This would be very convenient, and very strong -- indeed Kahn and Kalai said ''It would probably be more sensible to conjecture that it is {\emph not} true''.

It is remarkable then that it has a relatively simple proof, discovered by Park and Pham, which grew out of these sunflower ideas, and the link has been made explicit by Rao. Here we show how it is implied by Rao's technical proposition above.

The following theorem is easily shown to be equivalent to the conjecture in terms of thresholds as it is normally stated. (Note that we use the trivial fact that any $\mathcal{F}\subseteq 2^{[n]}$ is $n$-uniform.)

Let $\mathcal{F}\subseteq 2^n$ be a family of sets. Let $\mathbf{W}$ be a uniformly random subset of $[n]$ of size $\delta n$, and suppose that
\[\mathbb{P}(\textrm{there exists }A\in \mathcal{F}\textrm{ such that }A\subseteq \mathbf{W})\leq 3/4.\]
Then there is some collection of sets $\mathcal{G}$ such that every $A\in\mathcal{F}$ is contained in some $X\in\mathcal{G}$ and if $\mathbf{U}$ is a uniformly random set of size $\approx \frac{\delta}{\log n}n$ then
\[\bbe \abs{\{ Y\in \mathcal{G} : Y\subseteq \mathbf{U}\}}\leq 1/2.\]

Proof

Let $\mathcal{G}(\mathbf{W})$ be as in the corollary. By the second conclusion, and the fact that (a) occurs with probability at most $3/4$, we have that
\[\mathbb{P}(\textrm{for all }A\in\mathcal{F}\textrm{ there exists }X\in\mathcal{G}(\mathbf{W})\textrm{ such that }X\subseteq A)\geq 1/4.\]
We now consider the random distribution $\mathbf{U}$, which it is easy to check is $R$-spread for some $R\gg \delta^{-1}\log n$.
It follows from property (1) and Markov's inequality there is some $\mathcal{G}$ such that $\bbe_{\mathbf{U}}\abs{\mathcal{G}_{\mathbf{U}}}\leq 1/2$ and also for all $A\in\mathcal{F}$ there exists some $X\in \mathcal{G}$ with $X\subseteq A$, as required.

Fix some family of sets $\mathcal{F}$. For any $W_1,\ldots,W_t\subseteq [n]$ we let $W^i=\cup_{j\leq i}W_j$ and define $\mathcal{G}_i=\mathcal{G}(W_1,\ldots,W_t)_i$ for $1\leq i\leq t$ inductively. The idea is the following: at stage $i$ we look at the universe after discarding $W^i$, and include all large minimal sets from what remains of $\mathcal{F}$ which do not contain any set constructed so far.

More formally, we define $\mathcal{G}_i$ as the collection of sets of the form $A\backslash W^i$ for all $A\in\mathcal{F}$ such that

- $\abs{A\backslash W^i} \geq 2^{t-i}$ and
- there is no $X\in \mathcal{G}_j$ for $j<i$ such that $X\subseteq A$, and
- if $B\in\mathcal{F}$ is such that $B\backslash W^i\subsetneq A\backslash W^i$ then there is some $X\in\mathcal{G}_j$ for $j<i$ such that $X\subseteq B$,

There are two properties we need to check for Rao's Theorem. The second property is the most straightforward, and requires very few assumptions (in particular we don't care about uniformity or spreadness here).

Let $n,t\geq 1$ be integers and $\mathcal{F}\subseteq 2^{[n]}$ be a family of sets. Then, for any $W_1,\ldots,W_t\subseteq [n]$, either

- there exists some $A\in \mathcal{F}$ such that $A\subseteq W^t$, or
- for every $A\in\mathcal{F}$ there exists some $X\in\mathcal{G}(W_1,\ldots,W_t)$ such that $X\subseteq A$.

Proof

Suppose that (1) fails, and let $A\in\mathcal{F}$. We wish to find some $X\in\mathcal{G}$ such that $X\subseteq A$ -- suppose that no such $X$ exists. It follows that the family
\[\{ B\in\mathcal{F} : B\backslash W^t \subseteq A\backslash W^t\textrm{ and there is no }X\in\mathcal{G}_j\textrm{ for }j<i\textrm{ such that }X\subseteq B\}\]
contains $A$, and in particular is not empty. Let $B$ be a member of this family such that $B\backslash W^t$ is minimal. We claim that $B\backslash W^t\in\mathcal{G}_t$, and thus we are done. The first condition is just asking for $B\backslash W^t\neq\emptyset$, which holds since else $B\subseteq W^t$ and (1) holds. The second is trivially true by definition of the family, and the third is true by minimality.
Let $n,m,t\geq 1$ be integers and $R\geq 64n/m$. Let $\mathcal{F}\subseteq 2^{[n]}$ be a $2^t$-uniform family of sets. If $W_1,\ldots,W_t$ are uniformly chosen from all disjoint $t$-tuples of sets of size $m$ and $\mathcal{F}'$ is $R$-spread then
\[\bbe_{W_1,\ldots,W_t} \sum_{A\in\mathcal{F}'}\lvert \mathcal{G}_{A}\rvert < \frac{1}{8}\abs{\mathcal{F}'},\]

Note that this immediately implies property (1) of Rao's Theorem, since choosing a random partition of a random set of size $mt$ into $t$ parts is identical to uniformly choosing a disjoint $t$-tuple of sets of size $m$.
Proof

We first show that, if we fix $W_1,\ldots,W_{i-1}$, and $Z$ is a fixed subset of $[n]$, then there exists some $S=S(W_1,\ldots,W_{i-1},V)$ of size at most $2^{t-i+1}$ such that whenever $W_i,Z'$ are such that $Z'\in\mathcal{G}_i$ and $Z=Z'\cup W_i$ then $Z'\subseteq S$.
Indeed, we may assume that there exists at least one $W_i\subseteq Z$ such that $Z\backslash W_i\in \mathcal{G}_i$, or else we are trivially done. Let $Z\backslash W_i=A\backslash W^i$ for some $A\in\mathcal{F}$, and note that this forces $A\backslash W^{i-1}\subseteq Z$. Furthermore, there is no $X\in \mathcal{G}_j$ for $j<i$ such that $X\subseteq A$. Therefore, the collection of sets
\[\{ A\in\mathcal{F} : A\backslash W^{i-1}\subseteq Z\textrm{ and there is no }X\in\mathcal{G}_j\textrm{ for }j<i\textrm{ such that }X\subseteq A\}\]
is not empty. (Note that the definition of this family depends only on $W_1,\ldots,W_{i-1}$, and hence this family is fixed.) Let $B$ be a member of this family such that $B\backslash W^{i-1}$ is minimal, and let $S=B\backslash W^{i-1}$. We note that $\abs{B\backslash W^{i-1}}< 2^{t-(i-1)}$, or else $B\backslash W^{i-1}\in\mathcal{G}_{i-1}$ and there would exist some $Y\in \mathcal{G}_{i-1}$ such that $Y\subseteq B$, which is a contradiction. (For $i=1$ we use the assumption that $\abs{B}\leq 2^t$ since $B\in\mathcal{F}$.)
To prove the claim it therefore suffices to show that if $W_i\subseteq Z$ is such that $Z\backslash W_i\in \mathcal{G}_i$ then $Z\backslash W_i\subseteq B\backslash W^{i-1}$. Suppose otherwise, and note that since $B\backslash W^{i-1}\subseteq Z$,
\[B\backslash W^i = (B\backslash W^{i-1})\backslash W_i\subseteq Z\backslash W_i.\]
Property (3) of the definition of $\mathcal{G}_i$ means that we cannot have $B\backslash W^i\subsetneq Z\backslash W^i\in\mathcal{G}_i$, and hence $B\backslash W^i=Z\backslash W^i$, and so $Z\backslash W_i\subseteq B\backslash W^{i-1}$ as required.
In particular, we have now shown that with $W_1,\ldots,W_{i-1}$ fixed, and $Z$ any fixed subset of $[n]$, there are only $2^{2^{t-i+1}}$ many sets $Z'$ such that $Z=Z'\cup W_i$ and $Z'\in \mathcal{G}_i$.
We now note that, by linearity of expectation, and the $R$-spread hypothesis of $\mathcal{F}'$, since every set in $\mathcal{G}_i$ has size at least $2^{t-i}$,
\begin{align*}
\bbe_{W_1,\ldots,W_t}\frac{1}{\abs{\mathcal{F}'}}\sum_{A\in\mathcal{F}'}\#\{ Y\in\mathcal{G} : Y\subseteq A\}
&\leq \sum_{1\leq i\leq t}\sum_{\substack{Y\subseteq [n]\\ \abs{Y}\geq 2^{t-i}}}\frac{1}{\abs{\mathcal{F}'}}\sum_{A\in\mathcal{F}'}1_{Y\subseteq A}\mathbb{P}_{W_1,\ldots,W_t}(Y\in\mathcal{G}_i)\\
&\leq \sum_{1\leq i\leq t}\sum_{a \geq 2^{t-i}}R^{-a}\sum_{\substack{Y\subseteq[n]\\ \abs{Y}=a}}\mathbb{P}_{W_1,\ldots,W_t}(Y\in\mathcal{G}_i).
\end{align*}
We now bound the inner summation, for which we may assume that $W_1,\ldots,W_{i-1}$ have been fixed (so all probabilities below are conditional on that choice).
\begin{align*}
\sum_{\substack{Y\subseteq[n]\\ \abs{Y}=a}}\mathbb{P}(Y\in\mathcal{G}_i)
&\leq
\sum_{\substack{Y\subseteq[n]\\ \abs{Y}=a}}\sum_{\substack{Z\subseteq [n]\\ \abs{Z}=m+a}}\mathbb{P}'(Z=Y\cup W_i\textrm{ and }Y\in \mathcal{G}_i)\\
&\leq \sum_{\substack{Z\subseteq [n]\\ \abs{Z}=m+a\\ Z\cap W^{i-1}=\emptyset}}\sum_{\substack{Y\subseteq Z\\ \abs{Y}=a}}1_{Z=Y\cup W_i\textrm{ for some }W_i}\mathbb{P}(W_i=Z\backslash Y).
\end{align*}
Note here that, crucially, we have limited our attention to those $Z$ disjoint from $W^{i-1}$, or else the probability is zero, since both $Y\in\mathcal{G}_i$ and $W_i$ are disjoint from $W^{i-1}$ by construction, so certainly $Z=Y\cup W_i$ must be also.
Since $W_i$ is chosen uniformly from all $m$-subsets of $[n]\backslash W^{i-1}$, and $\abs{Z\backslash Y}=m$, the inner probability is \[\binom{n-(i-1)m}{m}^{-1}\leq \binom{n-(i-1)m}{m+a}(n/m)^a.\] Furthermore by the above argument (for fixed $Z$ and $W_1,\ldots,W_{i-1}$) the number of $Y$ such that $Z=Y\cup W_i$ for some $W_i$ is at most $2^{2^{t-i+1}}$. Therefore the above is \[\leq \binom{n-(i-1)m}{m+a}2^{2^{t-i+1}}\binom{n-(i-1)m}{m}^{-1}\leq 2^{2^{t-i+1}}(n/m)^a\leq 2^{2^{t-i+1}}(R/64)^{a}.\] It follows that \begin{align*} \bbe_{W_1,\ldots,W_t}\frac{1}{\abs{\mathcal{F}'}}\sum_{A\in\mathcal{F}'}\#\{ Y\in\mathcal{G} : Y\subseteq A\} &\leq \sum_{1\leq i\leq t}2^{2^{t-i+1}}\sum_{a\geq 2^{t-i}}64^{-a}\\ &\leq 2\sum_{1\leq i\leq t}2^{-4\cdot 2^{t-i}}\\ &\leq 1/8. \end{align*}

**[ER]**P. Erdős and R. Rado,*Intersection theorems for systems of sets*, J. London Math. Soc. 35 (1960) 85-90.**[ALWZ]**R. Alweiss, S. Lovett, K. Wu, and J. Zhang,*Improved bounds for the sunflower lemma*, arXiv: 1908.08483.**[FKNP]**K. Frankston, J. Kahn, B. Narayanan, and J. Park,*Thresholds versus fractional expectation-thresholds*, arXiv 1910.13433.**[K]**A. V. Kostochka,*A bound of the cardinality of families not containing $\Delta$-systems*, The mathematics of Paul Erdős, II, 229–235, Algorithms Combin., 14, Springer, Berlin, 1997.**[KRT]**A. V. Kostochka, V. Rödl, and L. A. Talysheva,*On Systems of Small Sets with No Large $\Delta$-Subsystems*, Combinatorics, Probability and Computing , Volume 8 , Issue 3 , May 1999 , pp. 265 - 268**[Rao1]**A. Rao,*Coding for Sunflowers*, Discrete Analysis: 11887.**[Sp]**J. Spencer,*Intersection theorems for systems of sets*, Canad. Math. Bull. 20 (1977), no. 2, 249–254.