Sunflower Lemma – Improved Bounds Questions

additive-combinatoricsco.combinatorics

I have been reading 'Improved bounds for the sunflower lemma' by Alweiss, Lovett, Wu and Zhang (Ann. of Math., Vol. 194(3), 2021), and have some gaps in my understanding of the paper. They are as follows:

  1. In Lemma: 2.8 (pg. 802), the authors bound the number of bad pairs $(W,S_{i})$ by a product of four bounds obtained earlier- (i) the bound on the number of sets of the form $W \cup S_{i}$, (ii) the number of sets of the form $A = S_{i} \cap S_{j}$ (once $S_{j}$ is chosen and fixed in a certain manner), (iii) the number of sets in $\mathcal{F}^{'}$ that contain the set $A$, and (iv) the number of sets of the form $S_{i} \cap W$. Each of the bounds in i)-iv) are clear to me, but I am unable to understand how the product is indeed a bound for the number of bad pairs, both heuristically and in terms of constructing an injection from the set of bad pairs into the set encoded as above.
  2. In Lemma 2.10 (pg. 803), a new weighting $\sigma^{'}$ is defined on $\mathcal{F}^{'}$. Am I right in thinking that $\forall \, S \, \in F^{'}: \sigma^{'}(S) = 1$? In this case, the spreadness criteria seems to go through. If not, how is $\sigma^{'}$ defined explicitly?
  3. On pg. 804, the authors construct a recursively-defined, strictly-decreasing sequence of integers, $(w_{i})_{i =1}^{r}$, with $w_{i+1} = \lfloor (1 – \varepsilon)w_{i} \rfloor + 1$ for some small, fixed $\varepsilon$, uniformly bounded below by $w^{*}.$ It can be shown that $w^{*} \geq \frac{1}{\varepsilon}$. The authors claim that $\exists K > 0: r \leq \frac{K \, \log(w)}{\varepsilon}.$ I am unable to prove this remark, and would prefer, if possible, a constructive proof.
    My Attempt: Here are some observations, which don't seem to lead to a proof of what is required. We have that $w_{i} \geq (1 – \varepsilon)^{i}w.$ Moreover, we have that $w_{i} – w_{i+1} \geq \varepsilon w_{i} – 1,$ and hence, we also have that $$w_{i} – w_{i + 1} \geq \varepsilon w_{r} – 1 \geq \varepsilon w^{*} – 1.$$ Thus, the distance between each pair of successive terms is at least $\varepsilon w^{*} – 1$, and so, assuming that this is positive, the number of integers in the sequence, i.e., $r$ is bounded above by $$\frac{w – w^{*} + 1}{\varepsilon w^{*} – 1}.$$ We also observe that $$1 \leq w_{i} – w_{i + 1} \leq \varepsilon w_{i} \leq \varepsilon w_{0} = \varepsilon w,$$ and hence, a lower bound for $r$ is $$\frac{w – w^{*} + 1}{\varepsilon w}.$$
  4. On pg. 808, the proof of Theorem: 4.2 concludes by stating that $\mathcal{F}$ cannot be $C \, \log(w)$ spread for large enough $C$. This apparently follows from the improved version of Theorem 2.5 from Rao's paper (also proved independently by Tao). Below is my argument- I am not certain that it is correct.

Any help on any or all of these questions is appreciated.

Edit: I would especially appreciate any insights regarding the first question, even if you don't have the time to answer the others.

Best Answer

Let me try to answer your questions.

  1. We can recover the pair $(W, S_i)$ from the four quantities you mentioned. So the number of their combinations upper bounds the number of pairs $(W, S_{i})$, which is why we multiply the number of options for each one.

  2. Indeed, we switch from a set system with not necessarily uniform weights to a multi set system with uniform weights to simplify the proof.

  3. You are asking for a constructive proof. Assume that $w_{i} \geq \frac{2}{\varepsilon}$. Then $w_{i+1} \leq (1 - \varepsilon) w_{i} + 1 \leq (1-\frac{\varepsilon}{2}) w_{i}$. So you reach $w_{i} < \frac{2}{\varepsilon}$ after at most $O\left(\frac{\log w}{\varepsilon}\right)$ steps.

  4. I don't understand your question. If you replace our Theorem 2.5 with Rao's result it removes all the $\log\log$ terms we have, which is the point we are making.

Related Question