Sunflowers: from soil to oil

Rao, Anup

doi:10.1090/bull/1777

Sunflowers: from soil to oil
HTML articles powered by AMS MathViewer

by Anup Rao HTML | PDF

Bull. Amer. Math. Soc. 60 (2023), 29-38 Request permission

Abstract:

A sunflower is a collection of sets whose pairwise intersections are identical. In this article, we shall go sunflower-picking. We find sunflowers in several seemingly unrelated fields, before turning to discuss recent progress on the famous sunflower conjecture of Erdős and Rado, made by Alweiss, Lovett, Wu, and Zhang, as well as a related resolution of the threshold vs expectation threshold conjecture of Kahn and Kalai discovered by Park and Pham. We give short proofs for both of these results.

References

M. Ajtai and E. Szemerédi, Sets of lattice points that form no squares, Studia Sci. Math. Hungar. 9 (1974), 9–11 (1975). MR 369299
Ryan Alweiss, Shachar Lovett, Kewen Wu, and Jiapeng Zhang, Improved bounds for the sunflower lemma, STOC ’20—Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, ACM, New York, [2020] ©2020, pp. 624–630. MR 4141787, DOI 10.1145/3357713.3384234
Tolson Bell, Suchakree Chueluecha, and Lutz Warnke, Note on sunflowers, Discrete Math. 344 (2021), no. 7, Paper No. 112367, 3. MR 4240687, DOI 10.1016/j.disc.2021.112367
P. Erdős and R. Rado, Intersection theorems for systems of sets, J. London Math. Soc. 35 (1960), 85–90. MR 111692, DOI 10.1112/jlms/s1-35.1.85
P. Erdős and A. Sárközy, Arithmetic progressions in subset sums, Discrete Math. 102 (1992), no. 3, 249–264. MR 1169145, DOI 10.1016/0012-365X(92)90119-Z
Gudmund Skovbjerg Frandsen, Peter Bro Miltersen, and Sven Skyum, Dynamic word problems, J. ACM 44 (1997), no. 2, 257–271. MR 1470586, DOI 10.1145/256303.256309
Keith Frankston, Jeff Kahn, Bhargav Narayanan, and Jinyoung Park, Thresholds versus fractional expectation-thresholds, Ann. of Math. (2) 194 (2021), no. 2, 475–495. MR 4298747, DOI 10.4007/annals.2021.194.2.2
Anna Gál and Peter Bro Miltersen, The cell probe complexity of succinct data structures, Theoret. Comput. Sci. 379 (2007), no. 3, 405–417. MR 2329209, DOI 10.1016/j.tcs.2007.02.047
A. W. Hales and R. I. Jewett, Regularity and positional games, Trans. Amer. Math. Soc. 106 (1963), 222–229. MR 143712, DOI 10.1090/S0002-9947-1963-0143712-1
Jeff Kahn and Gil Kalai, Thresholds and expectation thresholds, Combin. Probab. Comput. 16 (2007), no. 3, 495–502. MR 2312440, DOI 10.1017/S0963548307008474
Jinyoung Park and Huy Tuan Pham, A proof of the Kahn–Kalai conjecture, arXiv:2203.17207, 2022.
Sivaramakrishnan Natarajan Ramamoorthy and Anup Rao, Lower bounds on non-adaptive data structures maintaining sets of numbers, from sunflowers, 33rd Computational Complexity Conference, LIPIcs. Leibniz Int. Proc. Inform., vol. 102, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2018, pp. Art. No. 27, 16. MR 3824478
Anup Rao, Coding for sunflowers, Discrete Anal. , posted on (2020), Paper No. 2, 8. MR 4072543, DOI 10.19086/da
A. A. Razborov, Lower bounds on the monotone complexity of some Boolean functions, Dokl. Akad. Nauk SSSR 281 (1985), no. 4, 798–801 (Russian). MR 785629
K. F. Roth, On certain sets of integers, J. London Math. Soc. 28 (1953), 104–109. MR 51853, DOI 10.1112/jlms/s1-28.1.104
Michel Talagrand, Are many small sets explicitly small?, STOC’10—Proceedings of the 2010 ACM International Symposium on Theory of Computing, ACM, New York, 2010, pp. 13–35. MR 2743011