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 page, first 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.
snuzzo wuzzo
Pingback: Mohammad Ghomi and Joel Spruck settled the Cartan-Hadamard conjecture! | Combinatorics and more
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.
Pingback: Computer Science and its Impact on our Future | Combinatorics and more