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]
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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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},
}
Full Article