Amazing: Ryan Alweiss, Shachar Lovett, Kewen Wu, Jiapeng Zhang made dramatic progress on the Sunflower Conjecture

WOW! The new paper https://arxiv.org/abs/1908.08483 improved bounds for the sunflower lemma gives the most dramatic progress on the sunflower conjecture since it was asked. Congratulations to Ryan Alweiss, Shachar Lovett, Kewen Wu, Jiapeng Zhang.

(Written on my smartphone will expand it when reconnected to my laptop.)  (Reconnected) Rather, I will write about it again in a few weeks. Let me mention now that while the old difficult and ingenious improvements stayed in the neighborhood of Erdos and Rado initial upper bound the new result is in the neighborhood of the conjecture! (And is tight for a certain robust version of the problem!)

Let me also mention that we discussed the sunflower conjecture here many times and polymath10 (wiki pagefirst post, last post) was devoted to the problem.)

Update: Let me mention an important progress on the sunflower conjecture from 2018 by Junichiro Fukuyama in his paper Improved Bound on Sets Including No Sunflower with Three Petals. I missed Fukuyama’s paper at the time and I thank Sasha Kostochka and Andrew Thomason for telling me about it now. Further update: It seems that Junichiro’s argument (while insightful) has a gap.

Updates: (from comments below) Anup Rao presents a simplification of the original Alweiss, Lovett, Wu, and Zhang argument. https://arxiv.org/abs/1909.04774; An excellent Quanta Magazine article by Kevin Hartnett https://www.quantamagazine.org/mathematicians-begin-to-tame-wild-sunflower-problem-20191021/ . Terry Tao posted a version of Rao’s proof
https://terrytao.wordpress.com/2020/07/20/the-sunflower-lemma-via-shannon-entropy/.

This entry was posted in Combinatorics, Computer Science and Optimization and tagged , , , , , . Bookmark the permalink.

11 Responses to Amazing: Ryan Alweiss, Shachar Lovett, Kewen Wu, Jiapeng Zhang made dramatic progress on the Sunflower Conjecture

  1. that kitty says:

    snuzzo wuzzo

  2. Pingback: Mohammad Ghomi and Joel Spruck settled the Cartan-Hadamard conjecture! | Combinatorics and more

  3. Gil Kalai says:

    Let me mention that the robust notion of the problem arose in the connection to problems in the theory of computing and in earlier works [3,2] and the proof strategy continues the works in [1,2].

    [1] X. Li, S. Lovett, and J. Zhang. Sunflowers and quasi-sunflowers from randomness extractors. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018.

    [2] S. Lovett, N. Solomon, and J. Zhang. From DNF compression to sunflower theorems via regularity. In 34th Computational Complexity Conference, CCC 2019, July 18-20, 2019, New Brunswick, NJ, USA., pages 5:1–5:14, 2019.

    [3] B. Rossman. The monotone complexity of k-clique on random graphs. SIAM J. Comput., 43(1):256–279, 2014.

  4. Pingback: Computer Science and its Impact on our Future | Combinatorics and more

  5. Gil Kalai says:

    Anup Rao presents a simplification of the original Alweiss, Lovett, Wu, and Zhang argument. https://arxiv.org/abs/1909.04774

  6. Pingback: Noisy quantum circuits: how do we know that we have robust experimental outcomes at all? (And do we care?) | Combinatorics and more

  7. Gil Kalai says:

    An excellent Quanta Magazine article by Kevin Hartnett https://www.quantamagazine.org/mathematicians-begin-to-tame-wild-sunflower-problem-20191021/ . I was interviewed by Kevin and truly enjoyed to tell about the sunflower conjecture and I remember that when I prepared to the interview I thought about 3 major aspects of this achievement that makes me happy and during the interview I thought about one more. (And these aspects have several sub-aspects). The 4 aspects were 1) that it is a famous and difficult problem in extremal combinatorics that stood as a major challenge for many decades, 2) that it has various applications and connections to other problems in extremal combinatorics and Ramsey theory, 3) the manifestation of the structure vs randomness idea which is central in combinatorics and other areas 4) the old and new two-ways connections with the theory of computation – matrix multiplication, monotone lower bounds, improvement of the switching lemma fir pseudorandom circuits, and more.

    Of course it is a natural question if the methods can be used to prove the full conjecture, but for me the notion of robust sunflowers and the theorem for them which is sharp is very appealing.

  8. Pingback: Amazing! Keith Frankston, Jeff Kahn, Bhargav Narayanan, Jinyoung Park: Thresholds versus fractional expectation-thresholds | Combinatorics and more

  9. Pingback: Two talks at HUJI: on the “infamous lower tail” and TOMORROW on recent advances in combinatorics | Combinatorics and more

  10. Gil Kalai says:

    Terry Tao posted a version of Rao’s proof

    The sunflower lemma via Shannon entropy

  11. Pingback: Greatest Hits 2015-2022, Part II | Combinatorics and more

Leave a comment