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.

Advertisements
This entry was posted in Combinatorics, Uncategorized. Bookmark the permalink.

4 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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s