Improved bounds for the sunflower lemma

Abstract

A sunflower with $r$ petals is a collection of $r$ sets so that the intersection of each pair is equal to the intersection of all of them. Erdős and Rado proved the sunflower lemma: for any fixed $r$, any family of sets of size $w$, with at least about $w^w$ sets, must contain a sunflower with $r$ petals. The famous sunflower conjecture states that the bound on the number of sets can be improved to $c^w$ for some constant $c$. In this paper, we improve the bound to about $(\log\, w)^w$. In fact, we prove the result for a robust notion of sunflowers, for which the bound we obtain is sharp up to lower order terms.

  • [alon2004probabilistic] N. Alon and J. H. Spencer, The Probabilistic Method, Fourth ed., John Wiley & Sons, Inc., Hoboken, NJ, 2016.
    @BOOK{alon2004probabilistic,
      author = {Alon, Noga and Spencer, Joel H.},
      title = {The Probabilistic Method},
      series = {Wiley Series in Discrete Mathematics and Optimization},
      edition = {Fourth},
      publisher = {John Wiley \& Sons, Inc., Hoboken, NJ},
      year = {2016},
      pages = {xiv+375},
      isbn = {978-1-119-06195-3},
      mrclass = {60-02 (05C80 05D40 60C05 60F10 60G42)},
      mrnumber = {3524748},
      zblnumber = {1333.05001},
      }
  • [alon1989nowhere] Go to document N. Alon and M. Tarsi, "A nowhere-zero point in linear mappings," Combinatorica, vol. 9, iss. 4, pp. 393-395, 1989.
    @ARTICLE{alon1989nowhere,
      author = {Alon, Noga and Tarsi, M.},
      title = {A nowhere-zero point in linear mappings},
      journal = {Combinatorica},
      fjournal = {Combinatorica. An International Journal on Combinatorics and the Theory of Computing},
      volume = {9},
      year = {1989},
      number = {4},
      pages = {393--395},
      issn = {0209-9683},
      mrclass = {11T30 (15A04 15A33)},
      mrnumber = {1054015},
      mrreviewer = {Rudolf Lidl},
      doi = {10.1007/BF02125351},
      url = {https://doi.org/10.1007/BF02125351},
      zblnumber = {0717.05021},
      }
  • [ALWZstoc] Go to document R. Alweiss, S. Lovett, K. Wu, and J. Zhang, "Improved bounds for the sunflower lemma," in STOC ’20—Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020, pp. 624-630.
    @INPROCEEDINGS{ALWZstoc,
      author = {Alweiss, Ryan and Lovett, Shachar and Wu, Kewen and Zhang, Jiapeng},
      title = {Improved bounds for the sunflower lemma},
      booktitle = {S{TOC} '20---{P}roceedings of the 52nd {A}nnual {ACM} {SIGACT} {S}ymposium on {T}heory of {C}omputing},
      pages = {624--630},
      publisher = {ACM, New York},
      year = {2020},
      mrclass = {05D05},
      mrnumber = {4141787},
      doi = {10.1145/3357713.3384234},
      url = {https://doi.org/10.1145/3357713.3384234},
      zblnumber = {07298275},
      }
  • [bell2021note] Go to document T. Bell, S. Chueluecha, and L. Warnke, "Note on sunflowers," Discrete Math., vol. 344, iss. 7, p. 112367, 2021.
    @ARTICLE{bell2021note,
      author = {Bell, Tolson and Chueluecha, Suchakree and Warnke, Lutz},
      title = {Note on sunflowers},
      journal = {Discrete Math.},
      fjournal = {Discrete Mathematics},
      volume = {344},
      year = {2021},
      number = {7},
      pages = {Paper No. 112367, 3},
      issn = {0012-365X},
      mrclass = {05D05},
      mrnumber = {4240687},
      doi = {10.1016/j.disc.2021.112367},
      url = {https://doi.org/10.1016/j.disc.2021.112367},
      zblnumber = {1466.05204},
      }
  • [cavalarmonotone] Go to document B. P. Cavalar, M. Kumar, and B. Rossman, "Monotone circuit lower bounds from robust sunflowers," in LATIN 2020: Theoretical Informatics, Springer, Cham, 2020, vol. 12118, pp. 311-322.
    @INCOLLECTION{cavalarmonotone,
      author = {Cavalar, Bruno Pasqualotto and Kumar, Mrinal and Rossman, Benjamin},
      title = {Monotone circuit lower bounds from robust sunflowers},
      booktitle = {L{ATIN} 2020: {T}heoretical Informatics},
      series = {Lecture Notes in Comput. Sci.},
      volume = {12118},
      pages = {311--322},
      publisher = {Springer, Cham},
      year = {2020},
      mrclass = {68Q06 (68Q17)},
      mrnumber = {4184972},
      doi = {10.1007/978-3-030-61792-9_25},
      url = {https://doi.org/10.1007/978-3-030-61792-9_25},
      zblnumber = {},
      }
  • [deza1981every] Go to document M. Deza and P. Frankl, "Every large set of equidistant $(0,\,+1,\,-1)$-vectors forms a sunflower," Combinatorica, vol. 1, iss. 3, pp. 225-231, 1981.
    @ARTICLE{deza1981every,
      author = {Deza, M. and Frankl, P.},
      title = {Every large set of equidistant {$(0,\,+1,\,-1)$}-vectors forms a sunflower},
      journal = {Combinatorica},
      fjournal = {Combinatorica. An International Journal of the J\'{a}nos Bolyai Mathematical Society},
      volume = {1},
      year = {1981},
      number = {3},
      pages = {225--231},
      issn = {0209-9683},
      mrclass = {05B99 (05C65)},
      mrnumber = {0637827},
      mrreviewer = {R. C. Mullin},
      doi = {10.1007/BF02579328},
      url = {https://doi.org/10.1007/BF02579328},
      zblnumber = {0491.05045},
      }
  • [ErdosR1960] Go to document P. ErdHos and R. Rado, "Intersection theorems for systems of sets," J. London Math. Soc., vol. 35, pp. 85-90, 1960.
    @ARTICLE{ErdosR1960,
      author = {Erdős, P. and Rado, R.},
      title = {Intersection theorems for systems of sets},
      journal = {J. London Math. Soc.},
      fjournal = {The Journal of the London Mathematical Society},
      volume = {35},
      year = {1960},
      pages = {85--90},
      issn = {0024-6107},
      mrclass = {04.00},
      mrnumber = {0111692},
      mrreviewer = {Djuro Kurepa},
      doi = {10.1112/jlms/s1-35.1.85},
      url = {https://doi.org/10.1112/jlms/s1-35.1.85},
      zblnumber = {0103.27901},
      }
  • [es] Go to document P. ErdHos and E. Szemerédi, "Combinatorial properties of systems of sets," J. Combinatorial Theory Ser. A, vol. 24, iss. 3, pp. 308-313, 1978.
    @ARTICLE{es,
      author = {Erdős, P. and Szemerédi, E.},
      title = {Combinatorial properties of systems of sets},
      journal = {J. Combinatorial Theory Ser. A},
      fjournal = {Journal of Combinatorial Theory. Series A},
      volume = {24},
      year = {1978},
      number = {3},
      pages = {308--313},
      issn = {0097-3165},
      mrclass = {05A05 (04A20 05C35)},
      mrnumber = {0491202},
      mrreviewer = {William T. Trotter, Jr.},
      doi = {10.1016/0097-3165(78)90060-2},
      url = {https://doi.org/10.1016/0097-3165(78)90060-2},
      zblnumber = {},
      }
  • [fox2021sunflowers] J. Fox, J. Pach, and A. Suk, Sunflowers in set systems of bounded dimension, 2021.
    @MISC{fox2021sunflowers,
      author = {Fox, J. and Pach, J. and Suk, A.},
      title = {Sunflowers in set systems of bounded dimension},
      arxiv = {2103.10497},
      year = {2021},
      zblnumber = {},
      }
  • [fknp] Go to document K. Frankston, J. Kahn, B. Narayanan, and J. Park, "Thresholds versus fractional expectation-thresholds," Ann. of Math. (2), vol. 194, iss. 2, pp. 475-495, 2021.
    @ARTICLE{fknp,
      author = {Frankston, Keith and Kahn, Jeff and Narayanan, Bhargav and Park, Jinyoung},
      title = {Thresholds versus fractional expectation-thresholds},
      journal = {Ann. of Math. (2)},
      fjournal = {Annals of Mathematics. Second Series},
      volume = {194},
      year = {2021},
      number = {2},
      pages = {475--495},
      issn = {0003-486X},
      mrclass = {05C80 (60C05 82B26)},
      mrnumber = {4298747},
      doi = {10.4007/annals.2021.194.2.2},
      url = {https://doi.org/10.4007/annals.2021.194.2.2},
      zblnumber = {7395716},
      }
  • [fukuyama2018improved] J. Fukuyama, Improved bound on sets including no sunflower with three petals, 2018.
    @MISC{fukuyama2018improved,
      author = {Fukuyama, J.},
      title = {Improved bound on sets including no sunflower with three petals},
      arxiv = {1809.10318},
      year = {2018},
      zblnumber = {},
      }
  • [Hastad87] J. T. Hastad, Computational Limitations of Small-Depth Circuits, ProQuest LLC, Ann Arbor, MI, 1986.
    @BOOK{Hastad87,
      author = {Hastad, Johan Torkel},
      title = {Computational Limitations of Small-Depth Circuits},
      note = {Thesis (Ph.D.)--Massachusetts Institute of Technology},
      publisher = {ProQuest LLC, Ann Arbor, MI},
      year = {1986},
      pages = {(no paging)},
      mrclass = {Thesis},
      mrnumber = {2941107},
      zblnumber = {},
      }
  • [hu-blog] Go to document L. Hu, Entropy estimation via two chains: Streamlining the proof of the sunflower lemma, 2021.
    @MISC{hu-blog,
      author = {Hu, L.},
      title = {Entropy estimation via two chains: {S}treamlining the proof of the sunflower lemma},
      url={http://theorydish.blog/2021/05/19/entropy-estimation-via-two-chains-streamlining-the-proof-of-the-sunflower-lemma},
      year = {2021},
      zblnumber = {},
      }
  • [kostochka1997bound] Go to document A. V. Kostochka, "A bound of the cardinality of families not containing $\Delta$-systems," in The Mathematics of Paul Erdős, II, Springer, Berlin, 1997, vol. 14, pp. 229-235.
    @INCOLLECTION{kostochka1997bound,
      author = {Kostochka, A. V.},
      title = {A bound of the cardinality of families not containing {$\Delta$}-systems},
      booktitle = {The Mathematics of {P}aul {E}rdős, {II}},
      series = {Algorithms Combin.},
      volume = {14},
      pages = {229--235},
      publisher = {Springer, Berlin},
      year = {1997},
      mrclass = {05D05 (04A20)},
      mrnumber = {1425216},
      mrreviewer = {Zolt\'{a}n Füredi},
      doi = {10.1007/978-3-642-60406-5\_19},
      url = {https://doi.org/10.1007/978-3-642-60406-5_19},
      zblnumber = {0864.05081},
      }
  • [li2018sunflowers] X. Li, S. Lovett, and J. Zhang, "Sunflowers and quasi-sunflowers from randomness extractors," in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2018, vol. 116, p. 51.
    @INCOLLECTION{li2018sunflowers,
      author = {Li, Xin and Lovett, Shachar and Zhang, Jiapeng},
      title = {Sunflowers and quasi-sunflowers from randomness extractors},
      booktitle = {Approximation, Randomization, and Combinatorial Optimization. {A}lgorithms and Techniques},
      series = {LIPIcs. Leibniz Int. Proc. Inform.},
      volume = {116},
      pages = {Art. No. 51, 13},
      publisher = {Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern},
      year = {2018},
      mrclass = {05C80 (68W20)},
      mrnumber = {3857289},
      zblnumber = {07378663},
      }
  • [lovett2019dnf] Go to document S. Lovett, N. Solomon, and J. Zhang, "From DNF compression to sunflower theorems via regularity," in 34th Computational Complexity Conference, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2019, vol. 137, p. 5:1-5:14.
    @INCOLLECTION{lovett2019dnf,
      author = {Lovett, Shachar and Solomon, Noam and Zhang, Jiapeng},
      title = {From {DNF} compression to sunflower theorems via regularity},
      booktitle = {34th {C}omputational {C}omplexity {C}onference},
      series = {LIPIcs. Leibniz Int. Proc. Inform.},
      volume = {137},
      pages = {5:1--5:14},
      publisher = {Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern},
      year = {2019},
      mrclass = {68R05 (05D05)},
      mrnumber = {3984610},
      doi = {10.4230/LIPIcs.CCC.2019.5},
      url = {https://doi.org/10.4230/LIPIcs.CCC.2019.5},
      zblnumber = {},
      }
  • [nagy2021alon] J. Nagy and P. P. Pach, The Alon-Jaeger-Tarsi conjecture via group ring identities, 2021.
    @MISC{nagy2021alon,
      author = {Nagy, J. and Pach, P. P.},
      title = {The {A}lon-{J}aeger-{T}arsi conjecture via group ring identities},
      arxiv = {2107.03956},
      year = {2021},
      zblnumber = {},
      }
  • [naslund2017upper] Go to document E. Naslund and W. Sawin, "Upper bounds for sunflower-free sets," Forum Math. Sigma, vol. 5, p. 15, 2017.
    @ARTICLE{naslund2017upper,
      author = {Naslund, Eric and Sawin, Will},
      title = {Upper bounds for sunflower-free sets},
      journal = {Forum Math. Sigma},
      fjournal = {Forum of Mathematics. Sigma},
      volume = {5},
      year = {2017},
      pages = {Paper No. e15, 10},
      mrclass = {05D05 (05B40 11B30)},
      mrnumber = {3668469},
      mrreviewer = {Simon R. Blackburn},
      doi = {10.1017/fms.2017.12},
      url = {https://doi.org/10.1017/fms.2017.12},
      zblnumber = {1366.05113},
      }
  • [rao2019coding] Go to document A. Rao, "Coding for sunflowers," Discrete Anal., p. 2, 2020.
    @ARTICLE{rao2019coding,
      author = {Rao, Anup},
      title = {Coding for sunflowers},
      journal = {Discrete Anal.},
      fjournal = {Discrete Analysis},
      year = {2020},
      pages = {Paper No. 2, 8},
      mrclass = {05D05},
      mrnumber = {4072543},
      doi = {10.19086/da},
      url = {https://doi.org/10.19086/da},
      zblnumber = {1450.05092},
      }
  • [razborov1995bounded] Go to document A. A. Razborov, "Bounded arithmetic and lower bounds in Boolean complexity," in Feasible Mathematics, II, Birkhäuser Boston, Boston, MA, 1995, vol. 13, pp. 344-386.
    @INCOLLECTION{razborov1995bounded,
      author = {Razborov, Alexander A.},
      title = {Bounded arithmetic and lower bounds in {B}oolean complexity},
      booktitle = {Feasible Mathematics, {II}},
      venue = {{I}thaca, {NY},
      1992},
      series = {Progr. Comput. Sci. Appl. Logic},
      volume = {13},
      pages = {344--386},
      publisher = {Birkhäuser Boston, Boston, MA},
      year = {1995},
      mrclass = {03D15 (03F30 06E30 68Q15)},
      mrnumber = {1322282},
      mrreviewer = {Shih Ping Tung},
      doi = {10.1007/978-1-4612-2566-9_12},
      url = {https://doi.org/10.1007/978-1-4612-2566-9_12},
      zblnumber = {0838.03044},
      }
  • [Rossman14] Go to document B. Rossman, "The monotone complexity of $k$-clique on random graphs," SIAM J. Comput., vol. 43, iss. 1, pp. 256-279, 2014.
    @ARTICLE{Rossman14,
      author = {Rossman, Benjamin},
      title = {The monotone complexity of {$k$}-clique on random graphs},
      journal = {SIAM J. Comput.},
      fjournal = {SIAM Journal on Computing},
      volume = {43},
      year = {2014},
      number = {1},
      pages = {256--279},
      issn = {0097-5397},
      mrclass = {68Q17 (68Q87)},
      mrnumber = {3166976},
      mrreviewer = {Peter Damaschke},
      doi = {10.1137/110839059},
      url = {https://doi.org/10.1137/110839059},
      zblnumber = {1304.68081},
      }
  • [tao-blog] Go to document T. Tao, The sunflower lemma via Shannon entropy, 2020.
    @MISC{tao-blog,
      author = {Tao, T.},
      title = {The sunflower lemma via {S}hannon entropy},
      url = {http://terrytao.wordpress.com/2020/07/20/the-sunflower-lemma-via-shannon-entropy},
      year = {2020},
      zblnumber = {},
      }
  • [yu1999permanent] Go to document Y. Yu, "The permanent rank of a matrix," J. Combin. Theory Ser. A, vol. 85, iss. 2, pp. 237-242, 1999.
    @ARTICLE{yu1999permanent,
      author = {Yu, Yang},
      title = {The permanent rank of a matrix},
      journal = {J. Combin. Theory Ser. A},
      fjournal = {Journal of Combinatorial Theory. Series A},
      volume = {85},
      year = {1999},
      number = {2},
      pages = {237--242},
      issn = {0097-3165},
      mrclass = {15A15},
      mrnumber = {1673948},
      doi = {10.1006/jcta.1998.2904},
      url = {https://doi.org/10.1006/jcta.1998.2904},
      zblnumber = {0923.15011},
      }

Authors

Ryan Alweiss

Department of Mathematics, Princeton University, Princeton, NJ

Shachar Lovett

Department of Computer Science & Engineering, University of California, San Diego, La Jolla, CA

Kewen Wu

Department of Electrical Engineering and Computer Science, University of California, Berkeley, Berkeley, CA

Jiapeng Zhang

Department of Computer Science, University of Southern California, Los Angeles, CA