Bounds for the Sunflower conjecture

We say that a collection of finite sets $A_1,\ldots,A_\ell$ forms a $\ell$-sunflower if there exists some $B$ such that $A_i\cap A_j=B$ for all $i\neq j$ (or equivalently whenever some $x$ is in at least two of the sets it lies in all of them). Note that we allow $B=\emptyset$, and hence any collection of $\ell$ pairwise disjoint sets forms an $\ell$-sunflower -- indeed, the concept of sunflower is precisely what we get by including all disjoint collections and closing this under the operation of removing/adding an element to all sets in the collection.

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.\]

Sunflowers and spread families

We say that $\mathcal{F}$ is $R$-spread if for every set $X$ \[\#\{ A\in\mathcal{F} : X\subseteq A\}\leq R^{-\abs{X}}\abs{\mathcal{F}}.\] Note in particular that any $R$-spread family that contains a set of size $k$ has size at least $R^k$. Thus the $R$-spread hypothesis for a $k$-uniform family is stronger than the assumption $\mathcal{F}\geq R^k$. In fact, for the purposes of the sunflower conjecture, these assumptions are essentially identical.
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.
Therefore when studying the sunflower conjecture we lose nothing by imposing the stronger assumption that $\mathcal{F}$ is $R$-spread. Our goal is then to find some $R=R(k,\ell)$ such that any $R$-spread family contains an $\ell$-sunflower. In fact we will prove this in a strong form, showing that actually we can take $\ell$ disjoint sets. This is much more reasonable with the $R$-spread hypothesis, since now we know that any one particular set is not contained in too many sets, so disjointedness seems easier to establish.

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.\]
We remark that Lemma 1 is actually optimal - if we partition $[kR]$ into $k$ sets of size $\approx R$, and let $\mathcal{F}$ be the family of sets where we choose exactly one element from each partition, then it is easy, to check that $\mathcal{F}$ is $R$-spread, but the probability that a random set $\mathbf{W}$ with density $\delta$ contains some $A\in\mathcal{F}$ is bounded above by the probability that $\mathbf{W}$ contains at least one element from each part of the partition, which is \[\leq (1-(1-\delta)^R)^k\leq e^{-e^{-2\delta R}k}.\] In particular with $\delta \approx c\log k/R$ for some small constant $c$ this decays exponentially with $k$, and hence is much smaller than $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
  1. ($\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
  2. (either $W$ covers something in $\mathcal{F}$ or everything in $\mathcal{F}$ contains something in $\mathcal{G}$) for any $W$, either
    1. there exists some $A\in \mathcal{F}$ such that $A\subseteq W$, or
    2. for every $A\in\mathcal{F}$ there exists some $B\in\mathcal{G}$ such that $B\subseteq A$.
Given this statement, the deduction of Lemma 1 is straightforward: by property (2) if $\mathbf{W}$ does not contain any $A\in\mathcal{F}$ then for all $A\in\mathcal{F}$ we have $\#\{ B\in\mathcal{G} : B\subseteq A\}\geq 1$, and hence in particular $\sum_{A\in \mathcal{F}}\#\{ B\in\mathcal{G} : B\subseteq A\}\geq \abs{\mathcal{F}}$, whence \begin{align*} \mathbb{P}_{\mathbf{W}}(\mathbf{W}\textrm{ does not contain any }A\in\mathcal{F}) &\leq \bbe_{W,\mathcal{G}(W)} \frac{1}{\abs{\mathcal{F}}}\sum_{A\in\mathcal{F}}\#\{ B\in\mathcal{G} : B\subseteq A\}\\ &<1/2. \end{align*} Note that for the sunflower conjecture we applied this with $\mathcal{F}'=\mathcal{F}$, but for the threshold conjecture application we will apply this with $\mathcal{F}'$ being a uniform distribution independent from $\mathcal{F}$.

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

Kahn-Kalai threshold conjecture

The Kahn-Kalai threshold conjecture, now a theorem of Park and Pham, roughly says the following: given any monotonic property $P$ there is some threshold probability $p$ such that building a random set with that probability has the property with probability at least $1/2$. This is a natural and important quantity. Call this $p_T$.

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.

Note that it is trivial via the union bound that \[\mathbb{P}(\textrm{there exists }A\in \mathcal{F}\textrm{ such that }A\subseteq \mathbf{W})\leq \bbe \abs{\{ Y\in \mathcal{F} : Y\subseteq \mathbf{W}\}}.\] In particular if this probability is large, the expectation must be large. The point of the threshold theorem is that it gives a converse -- at the cost of replacing $\mathcal{F}$ by some $\mathcal{G}$ which contains it, and replacing uniformly random sets of size $m$ with random sets of size $m/\log n$, the probability being small forces the expected count to be small also.

Rao's construction of G

For any family $\mathcal{F}$ and set $X$ the $X$-shadow of $\mathcal{F}$ is defined to be \[\mathcal{F}_X = \{ A\in \mathcal{F} : A\subseteq X\}.\] Let $t,m\geq 1$ be some parameters to be chosen later. To prove Rao's Theorem we actually define a function on $t$-tuples of sets of size $m$ as $\mathcal{G}(W_1,\ldots,W_t)$, and then define $\mathcal{G}(W)$ on sets $W$ of size $mt$ by choosing first a random partition of $W$ into $t$ parts. (We will eventually choose $t\approx \log k$ for the result.)

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

  1. $\abs{A\backslash W^i} \geq 2^{t-i}$ and
  2. there is no $X\in \mathcal{G}_j$ for $j<i$ such that $X\subseteq A$, and
  3. 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$,
and let $\mathcal{G}(W_1,\ldots,W_t;\mathcal{F})=\cup_{1\leq i\leq t}\mathcal{G}_i$. We write $\mathcal{G}=\cup_{1\leq i\leq t}\mathcal{G}_i$.

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
  1. there exists some $A\in \mathcal{F}$ such that $A\subseteq W^t$, or
  2. 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.
The first property is much more subtle to prove, and we will need to make essential use of both the uniformity of $\mathcal{F}$ and the $R$-spread hypothesis on $\mathcal{F}'$.
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*}