Lecture notes on recent improvements for the sunflower lemma


Presented January 2022, revised May 2022

This document gives a self-contained presentation of the proof of the (improved) sunflower lemma.

Definition. A sunflower with r petals is a collection of sets S1,...,Sr where for all {i,j}⊆[r], Si∩Sj has the same value. Equivalently, for any three sets Si,Sj,Sk, and no element in the universe is contained in only 2 of the sets.

Lemma 1. Original sunflower lemma.[ ER60] Set system containing ≥k!(r−1)k sets of size ≤k, must contain sunflower with r petals.

Example 2. Application: Erdős + Sarkozy. Given T⊆[n], let sum(T)=x∈Tx. For all S⊆{1,...,n}, there are subsets T1,...,Tr for r≈|S|/(logn)2 where sum(T1),sum(T2),...,sum(Tr+1) is arithmetic progression. Proof: have |S|logn≈(wlogn)logn different subsets of size ≤logn with the same value, since there are only ≤n2 possible values. By sunflower lemma, have a sunflower in here, S1,...,Sr; let V=Si∩Sj be common area. Let subsets be T1=S1, T2=S1∪(S2\V), and T3=S1∪(S2\V)∪(S3\V), and so on.

Some history:

Theorem 3. There exists a universal constant C≤64 so that for any r≥1, k≥2, every set system containing ≥(Crlogk)k sets of size ≤k contains an r-petaled sunflower.

1 Entry material

Definition. Spread set; for R>1, random set A is R-spread if Pr[S⊆A]≤R−|S| for all S. Set family {Ai}i∈I is R spread if uniformly picking random set in family is R-spread.

For example, if the set system {Ai}i∈I has the property that every set contains one of a special set of 3 elements, then {Ai}i∈I can be no more than 3-spread.

Remark 4. Given a random R-spread set A, let B be a random set for which B⊆A almost surely. Then B is also R-spread.

Lemma 5. Locating a single petal. Assume {Ai}i∈I subset family on X is R-spread. Let V be a random subset of X drawn where each coordinate is independently included with probability 12r. Then with probability ≥12, V contains some Ai.

We now show that the sunflower lemma reduces to locating a single petal (Lemma 5).

Proof. Let A={Ai}i∈I be the given set system, with universe X, and all |Ai|≤k; we are given that |I|≥Rk. First, we show that it suffices to prove the sunflower lemma in the case where {Ai}i∈I is R-spread. Assume that A is not R-spread. For each set S⊆X, define

Q(S):=R|S||{i∈I:S⊆Ai}|

and let S0 be the set maximizing this. As Q(S)=0 if |S|>k, it must be |S0|≤k. Also, Q(∅)=|I|≥Rk. Let J={i∈I:S0⊆Ai}. Note that J must be nonempty. Consider now the family of sets A={Aj\S0}j∈J. Given a sunflower in A, we can form a sunflower in A by adding S0 to each petal. Also, A is R-spread on X, because for any S⊆X, and j∈J drawn u.a.r,

Pr[S⊆Aj\S0]=1S∩S0=∅|{i∈I:S0∪S⊆Ai}||{i∈I:S0⊆Ai}|≤1S∩S0=∅Q(S∪S0)/R|S0∪S|Q(S0)/R|S0|≤1S∩S0=∅R|S0|−|S0∪S|=R−|S|

(The inequality comes from the fact Q(S0)≥Q(S∪S0). The fact that |S0|−|S0∪S|=−|S| can be assumed because, if S and S0 intersect, then Pr[S⊆Aj\S0]=0.)

Thus, it suffices to prove the sunflower lemma if A is R-spread. Randomly partition X into 2r subsets V1,...,V2r, where for each index i∈X, we sample an independent uniform integer in [2r] and use it to determine which subset contains i. The distribution of each individual Vi will be the same as if each Vi were sampled from the product distribution where each coordinate is present with probability 12r. By Lemma 5, with probability ≥12, each Vi contains some Ai∈A. Since the expected number of Vi containing a set in A is ≥2r·12=r, there must be a specific partition of subsets ˆV1,...,ˆV2r where at least r of them contain an element of A. Let S1,...,Sr be these contained elements. They are all in A, and all disjoint, because the ˆVi are disjoint. __

Definition 6. Given a random variable X and deterministic function f, a conditionally independent copy X of a variable X subject to a condition f(X)=f(X) is a random variable identically distributed to X, where f(X)=f(X) always holds, and the variables X and X are conditionally independent given f(X).

Lemma 7. Refinement inequality. Let A be an R-spread random subset of X. Let W be a random subset of X in which each element is included with probability δ, which is independent of A. Let (A,W) be a conditionally independent copy of (A,W) subject to A∪W=A∪W. Then A is distributed identically to A and satisfies:

A⊆A∪WandE[A\W]≤1+Hb(δ)log(Rδ)E|A|.

We now reduce Lemma 5 to the preceding Lemma 7:

Proof. Let m be an integer chosen later, and let W1,W2,...,Wm be independent random subsets of X where each possible element of Wi is present with probability δ=1−1−12r1/m, so that V=⋃mi=1Wi contains each i∈X independently with probability 12r=1−(1−δ)m. For brevity, write Ui=⋃ij=1Wj, and CR,δ=1+Hb(δ)log(Rδ). Let A0 be uniformly randomly chosen from the set {Ai}i∈I – independent of the (Wi)i∈[m], and construct A1,...,Am iteratively as follows. Say we have constructed Ai, which is identically distributed to A0, may be correlated with (W1,W2,...,Wi), and satisfies Ai⊆A0∪Ui and E[Ai\Ui]≤CiR,δE|A0|. We construct a conditionally independent copy (Ai,Wi+1,Ui) of (Ai,Wi+1,Ui) subject to Ui=Ui and

(Ai\Ui)∪Wi+1=(Ai\Ui)∪Wi+1.

For each T⊆X, we note that the conditioned random variable Bi,T=(Ai\Ui|Ui=T) is R-spread, because for any S⊆X, we have:

Pr[S⊆Bi,T]=Pr[S⊆Ai\Ui|Ui=T]≤Pr[S⊆A0|Ui=T]=Pr[S⊆A0]≤R−|S|,

where we use the property that Ai⊆A0∪Ui, and that A0 is independent of Ui. Furthermore, with Bi,T=(Ai\Ui|Ui=T), we observe that Bi,T,Wi+1 is a conditionally independent copy of (Bi,T,Wi+1) subject to Bi,T∪Wi+1=Bi,T∪Wi+1. We apply Lemma 7 to (Bi,T,Wi+1), finding that Bi,T⊆Bi,T∪Wi+1, and

EBi,T\Wi+1≤CR,δE|Bi,T|.

Combining the results of the lemma over all T⊆X gives Ai\Ui⊆(Ai\Ui)∪Wi+1, since for each possible value T of Ui, we have Ai\T⊆(Ai\T)∪Wi+1. This implies Ai⊆Ai∪Ui+1. Similarly,

E[Ai\Ui+1]=T⊆XPr[Ui=T]E[(Ai\Ui)\Wi+1|Ui=T]=T⊆XPr[Ui=T]EBi,T\Wi+1≤CR,δT⊆XPr[Ui=T]E|Bi,T|=CR,δT⊆XPr[Ui=T]E[|Ai\Ui||Ui=T]=CR,δE|Ai\Ui|.

Finally, letting Ai+1=Ai, we observe that Ai+1 is identically distributed to A0, satisfies Ai+1⊆A0∪Ui+1, and has

E[Ai+1\Ui+1]≤CR,δE|Ai\Ui|≤Ci+1R,δE|A0|.

Since |Ai|≤k for all i∈[N], we have |A0|≤k and hence E|A0|≤k; then using the fact that V=⋃mi=1Wi=Ui, we have:

E|Am\V|≤CmR,δk

We want to prove that the right hand side is ≤12, because then E|Am\V|≤12; since |Am\V| is integral, this means that at least half the time, |Am\V|=0 and Am⊆V holds. (Since Am is distributed identically to A0, this means that we can couple a uniform random index n in I to V so that An⊆V with probability ≥12.) Setting m=log(2k), we observe that E|Am\V|≤12 if CR,δ≤2logRδ≤12 – or equivalently, R≥1δ22·2. Since

δ=1−1−12r1/m=1−1−12r1/log(2k)≤1log(2k)2r

it follows setting

R=24log(2k)·2r

is sufficient. (As we have assumed k≥2, log(2k)≤2logk, so we have R≤64log(k)r.) __

2 Interlude: Entropy lemmas

Definition 8. Given a random variable X with values in S, its Shannon entropy is

H(X):=x∈SPr[X=x]log1Pr[X=x].

The conditional Shannon entropy on event E is

H(X|E):=x∈SPr[X=x|E]log1Pr[X=x|E]

and conditioning on random variable Y with range T gives

H(X|Y):=y∈TPr[Y=y]H(X|Y=y)

Fact 9. Entropy refresher

  1. Monotonicity; if X=f(Y) for a fixed function f, then 0≤H(X)≤H(Y) . If X=f(Y,Z), then 0≤H(X|Z)≤H(Y|Z). If Y=h(Z), then H(X|Z)≤H(X|Y).

  2. Subadditivity: H(X,Y)≤H(X)+H(Y) with equality if independent.

  3. Chain rule: H(X,Y)=H(X)+H(Y|X)=H(Y)+H(X|Y). Also have: 0≤H(X|Y)≤H(X).

  4. Jensen’s inequality: for convex ψ, ψ(EX)≤Eψ(X). For entropy, means that if X is supported on S, then H(X)≤log|S|. Similarly, if X supported on SY, then H(X|Y)≤Elog|SY|.

  5. Binary entropy: Hb(p)=plog1p+(1−p)log11−p, and ddpHb(p)=log1−pp. Also, Hb is concave, so d2dp2Hb(p)≤0.

Lemma 10. Subsets of small sets have small conditional entropy. Let A,B be random finite sets. If A⊆B almost surely, have H(A|B)≤E|B|.

Proof. This follows from Jensen’s inequality: H(A|B)≤Elog⏐⏐2B⏐⏐=E|B| since A∈2B. __

Lemma 11. Let A be an R-spread random set in X. Then for any random set S for which S⊆A almost surely, H(A|S)≤H(A)−(logR)E|S|.

Proof. We want to prove that the mutual information I(A:S)=H(A)−H(A|S)≥(logR)E|S|. Write p(A)=Pr[A=A], p(S)=Pr[S=S], and p(A,S)=Pr[A=A∧S=S], and p(A|S)=p(A,S)/p(S). Then:

H(A)−H(A|S)=A⊆Xp(A)log1p(A)−S⊆Xp(S)A⊆Xp(A,S)p(S)logp(S)p(A,S)=S⊆XA⊆Xp(A,S)logp(A,S)p(A)p(S)=S⊆Xp(S)A⊆Xp(A|S)logp(A|S)p(A)=S⊆Xp(S)S⊆A⊆Xp(A|S)logp(A|S)p(A)becauseS⊆A

Because A is R-spread, for any S, we have

Pr[S⊆A]=S⊆A⊆Xp(A)≤R−|S|;

Note also that S⊆A⊆Xp(A|S)=1, because S⊆A almost surely. Then because f(s)=−log(s) is convex, by Jensen’s inequality,

S⊆Xp(S)S⊆A⊆Xp(A|S)·−logp(A)p(A|S)≥S⊆Xp(S)·−logS⊆A⊆Xp(A|S)p(A)p(A|S)=S⊆Xp(S)log1S⊆A⊆Xp(A)≥S⊆Xp(S)logR|S|=logRS⊆X|S|p(S)=(logR)E|S|.

This completes the proof. __

Corollary 12. Let W be a random subset of X with each coordinate included independently with probability δ. Let S be a random subset of X for which S⊆W almost surely. Then H(W|S)≤H(W)−log1δE|S|.

Proof. W is 1δ-spread, because for any T⊆X, Pr[T⊆W]=Pr[∀i∈T:Wi=1]=1δ|T|. Then apply Lemma 11. __

Lemma 13. Info properties of uniformly random sets. Let X be finite set, and W a set with each coordinate included independently with probability δ. Let S be a random subset of X. Then H(W∪S)≤H(W)+log1δE|S|.

Proof. We will show that for any coordinate i∈X,

H(Wi∪Si)≤Hb(δ)+log1δE|Si|
(1)

Summing this over all i∈X and using subadditivity gives:

H(W∪S)≤i∈XH((W∪S)i)≤|X|Hb(δ)+log1δi∈XE|S∩{i}|=H(W)+log1δE|S|

To prove Eq. 1, we first note that Hb is concave, for all γ s.t. δ+γ∈[0,1]

Hb(δ+γ)≤Hb(δ)+γ·ddpHb(δ)

By monotonicity and the union bound, δ=Pr[Wi]≤Pr[Wi∪Si]≤δ+Pr[Si]. This and the previous statement imply:

Hb(Wi∪Si)≤maxγ∈[0,Pr[Si]]Hb(δ+γ)≤Hb(δ)+maxγ∈[0,Pr[Si]]γ·log1−δδ

We have two cases. If δ≤12, then log1−δδ≥0, and the maximum of this last upper bound happens at γ=Pr[Si]; if δ≥12, then the maximum happens at γ=0. In both cases, log1δPr[Si] is an upper bound, so:

Hb(Wi∪Si)≤Hb(δ)+⎧⎨⎩0δ≥12Pr[Si]log1−δδδ≤12≤Hb(δ)+log1δPr[Si]

which completes the proof, as Pr[Si]=E|Si|. __

Lemma 14. Let X be finite set, and W a set with each coordinate included independently with probability δ. Let S be a random subset of X, independent of W. Then H(S\W|S)=Hb(δ)E|S|.

Proof. H(S\W|S)=ESH(S\W|S=S)=ES|Hb(δ)|S||=Hb(δ)E|S| since for any set T⊆X, we have H(T\W)=|T|Hb(1−δ)=|T|Hb(δ). __

Lemma 15. Properties of “Conditionally independent copy.” Given X and deterministic f, we can construct a conditionally independent copy X with the exact same distribution as X, but linked so that f(X)=f(X) , and X, X are independent when conditioned on f(X)=f(X).

  1. H(X|X)=H(X|f(X))=H(X)−H(f(X))

  2. H(X,X)=2H(X)−H(f(X))

Proof. The joint distribution for (X,X) has

Pr[(X,X)=(X,X)]=1f(X)=f(X)Pr[f(X)=f(X)]·Pr[X=X|f(X)=f(X)]Pr[X=X|f(X)=f(X)]

Then since X,X are conditionally independent given f(X)=f(X),

H(X|X)=H(X|f(X))=H(X,f(X))−H(f(X))=H(X)−H(f(X))

Adding H(X) to both sides and using the chain rule gives H(X,X)=2H(X)−H(f(X)), since H(X)=H(X). __

3 Conclusion: proving Lemma 7

Proof. We are given a conditionally independent copy (A,W) of (A,W) subject to A∪W=A∪W; equivalently, this ensures

A⊆A∪W=⇒A\W⊆A∩A

We now prove E|A∩A|≤1+Hb(δ)logRδE|A|.1 We will estimate H(A,W,A,W) in two different ways, and prove lower and upper bounds for it; some light algebra afterwards reveals the result.

For the lower bound:

H(A,W,A,W)=H(A,W)+H(A,W|A,W)=H(A)+H(W)+H(A,W|A,W)

Now,

H(A,W|A,W)=H(A,W|A,W,A∪W)becauseA∪W←A,W=H(A,W|A∪W)cond.indep.ofA,WgivenA∪W=H(A,W|A∪W)identdistrib.ofA,WgivenA∪W=H(A,W)−H(A∪W)defn.condentropy,andA∪W←A,W=H(A)+H(W)−H(A∪W)independence≥H(A)−log1δE|A|byLemma13

Thus

H(A,W,A,W)≥2H(A)+H(W)−log1δE|A|

The upper bound uses a more complicated decomposition:

H(A,W,A,W)=H(A,A∩A,W,A,W)=H(A)+H(A∩A|A)+H(A|A,A∩A)+H(W|A,A∩A,A)+H(W|A,A∩A,A,W)

Since A∩A⊆A, Lemma 10 implies

H(A∩A|A)≤E|A|.

By monotonicity and Lemma 11,

H(A|A,A∩A)≤H(A|A∩A)≤H(A)−(logR)E|A∩A|.

By monotonicity, and applying Lemma 12 since A\A⊆W,

H(W|A,A∩A,A)≤H(W|A\A)≤H(W)−log1δE|A\A|.

Finally, as we can write W=(A∪W)\(A\W), (i.e, as a function of A, W, and (A\W)), by applying monotonicity twice, and then Lemma 14:

H(W|A,A∩A,A,W)≤H(A\W|A,A∩A,A,W)≤H(A\W|A)=Hb(δ)E|A|.

Combining these upper bounds gives:

H(A,W,A,W)≤H(A)+E|A|+H(A)−(logR)E|A∩A|+H(W)−log1δE|A\A|+Hb(δ)E|A|=2H(A)+H(W)−log1δE|A|+(1+Hb(δ))E|A|−(logRδ)E|A∩A|

Combining this with the lower bound on H(A,W,A,W) gives, after canceling identical terms:

0≤(1+Hb(δ))E|A|−(logRδ)E|A∩A|

hence E|A∩A|≤1+Hb(δ)logRδE|A|. __

4 Misc

Remark 16. A remark of [ BCW21] implies that the idea of an R-spread construction, combined with a random selection of a subset, cannot be further improved. They show the example of a set family F on V1∪...∪Vk,where each set Vi has size R and is disjoint from the others. The set family F contains all sets Fi of size k which |Fi∩Vj|=1 for all j∈[k]. This is R-spread, but the probability that a random set of density δ=Θ1r contains any set of F is

≤(1−(1−δ)r)k≤e−(1−δ)rk

which is ≤12 if (1−δ)rk≥ln2, i.e, if rlnkδ. Would need r≈1δ for the multiple disjoint random sampling trick to work.

References

[ALW+20]

Ryan Alweiss, Shachar Lovett, Kewen Wu, and Jiapeng Zhang. Improved bounds for the sunflower lemma. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, pages 624–630, Chicago, IL, USA. Association for Computing Machinery, 2020. isbn: 9781450369794. doi: 10 . 1145 / 3357713 . 3384234. url: https://doi.org/10.1145/3357713.3384234.

[BCW21]

Tolson Bell, Suchakree Chueluecha, and Lutz Warnke. Note on sunflowers. Discrete Mathematics, 344(7):112367, 2021. issn: 0012-365X. doi: https://doi.org/10.1016/j.disc.2021.112367. url: https://www.sciencedirect.com/science/article/pii/S0012365X21000807.

[ER60]

P. Erdös and R. Rado. Intersection theorems for systems of sets. Journal of the London Mathematical Society, s1-35(1):85–90, 1960. doi: https://doi.org/10.1112/jlms/s1-35.1.85. eprint: https://londmathsoc.onlinelibrary.wiley.com/doi/pdf/10.1112/jlms/s1-35.1.85. url: https://londmathsoc.onlinelibrary.wiley.com/doi/abs/10.1112/jlms/s1-35.1.85.

[Hu21]

Lunjia Hu. Entropy Estimation via Two Chains: Streamlining the Proof of the Sunflower Lemma. 2021. url: https://web.archive.org/web/20220502190641/https://theorydish.blog/2021/05/19/entropy-estimation-via-two-chains-streamlining-the-proof-of-the-sunflower-lemma/. Accessed: 2022-05-02.

[Rao20]

Anup Rao. Coding for sunflowers, 2020. arXiv: 1909.04774 [math.CO].

[Tao20]

Terence Tao. The sunflower lemma via Shannon entropy. 2020. url: https://web.archive.org/web/20220502185424/https://terrytao.wordpress.com/2020/07/20/the-sunflower-lemma-via-shannon-entropy/. Accessed: 2022-05-02.

1In fact, not only do we have E|A\W|≤E|A∩A|, but it is possible to prove E|A\W|=(1−δ)E|A∩A|.

Return to main page | as PDF