Wiki
Wiki

Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated


Statement

Lemma 3.1 (p. 11): "There exists a ww-set system of size ((log⁡w)/8)w−w=(log⁡w)w(1−o(1))((\log w)/8)^{w-\sqrt w}=(\log w)^{w(1-o(1))} which does not contain a (1/2,1/2)(1/2,1/2)-robust sunflower."

Section 3 assumes, just before the lemma (p. 11), that ww is sufficiently large, and fixes α=β=1/2\alpha=\beta=1/2 for concreteness, saying that the construction can be easily modified for any other constant values of α,β\alpha,\beta. Robust sunflowers are defined on the page of Theorem 1.9, which the lemma shows to be tight up to the o(1)o(1) in the exponent for α=β=1/2\alpha=\beta=1/2. The lemma concerns robust sunflowers only; it says nothing about ordinary sunflowers.

Source. R. Alweiss, S. Lovett, K. Wu and J. Zhang, Improved bounds for the sunflower lemma, arXiv:1908.08483v3 (31 August 2021, 19 pages; the copy read), Lemma 3.1 on p. 11, proof on pp. 11--12; published in Ann. of Math. (2) 194 (2021), no. 3. The journal text was not compared.

Read depth. Claims checked: the statement and the standing assumption of Section 3 were read clause by clause on the page image of p. 11. The proof was read for structure only.

Proof pointer

Pages 11--12: take ww disjoint blocks of size log⁡(w/c)\log(w/c), with c=1/εc=1/\varepsilon, and the system of all transversals, which is not (1/2,1/2)(1/2,1/2)-satisfying (Claim 3.2); a greedy subsystem with pairwise intersections at most (1−ε)w(1-\varepsilon)w forces every robust sunflower to have a kernel too small for its link to be satisfying (Claim 3.3), and ε=1/w\varepsilon=1/\sqrt w gives the stated size.

Dependencies

None outside the paper's definitions.

Bears on

No Erdős problem directly: it limits the robust-sunflower method of Theorem 1.9 behind the paper's bound for Problem 20, not the sunflower function itself.