While slowly writing Post 5 (now planned to be Post 6) of our polymath10 project on the Erdos-Rado sunflower conjecture, the very recent proof (see this post) that cap sets have exponentially small density has changed matters greatly! It implies a weaker version of the Erdos-Rado sunflower conjecture made by Erdos and Szemeredi. Let me remind the readers what these conjectures are:
The Erdos-Szemeredi Sunflower Conjecture: There is such that a family of subsets of [n] without a sunflower of size three have at most sets. (Erdos and Szemeredi have made a similar conjecture for larger sunflowers.)
The strong Cap Set Conjecture: There is such that a subset of without three distinct elements a, b, and c with a+b+c=0 contains at most elements.
Results by Erdos and Szemeredi give that the Erdos Rado sunflower conjecture implies the Erdos-Szemeredi sunflower conjecture. This implication is Theorem 2.3 in the paper On sunflowers and matrix multiplication by Noga Alon, Amir Shpilka, and Christopher Umans where many implications between various related conjectures are discussed (we discussed it in this post). One implication by Noga, Amir and Chris is that the strong cap set Conjecture implies the Erdos-Szemeredi sunflower conjecture!
In order that the post with the cap set startling news will remain prominent, I will put the rest of this post under the fold.
We also refer the readers again to Kostochka’s review paper Extremal problem on Δ-systems, and to the paper Group-theoretic algorithms for matrix multiplication, by Henry Cohn, Robert Kleinberg, Balasz Szegedy, and Christopher Umans.
A few days ago the cap set conjecture was proved (with the upper bound , see the previous post) and this implies also the Erdos-Szemeredi sunflower conjecture! (Eric Naslund computed (via a new argument that he had found) the derived upper bound to be .)
Thus, currently the most promising line of attack to the Erdos-Rado sunflower conjecture may well be through the result and methods involved in the Erdos-Szemeredi sunflower conjecture (now theorem) via the strong cap set conjecture (now theorem). Although I don’t have much to say about it myself, discussing this avenue is certainly welcome.
Some questions that come to mind are:
- Can the polynomial method apply also to the full Erdos-Rado sunflower conjecture (for three petals).
- Is there a direct proof (via the polynomial method) for the Erdos Szemeredi conjecture
- Do the new upper bounds for the Erdos-Szemeredi conjecture have some consequences for the Erdos-Rado conjecture?
- What about the Erdos-Szemeredi conjecture for avoiding sunflowers with r petals r>3.
In my next polymath10 post I do plan to return to the homological approach and related technology that I also like for other reasons/problems.
An off topic remark: In the previous post I expressed the (rather obvious) thought that the new cap set development may reflect also on bounds for Roth’s theorem, (little in the spirit of polymath6: “A is to B as C is to ???” ) with some naive thoughts about it. I still hope for some serious discussion about such a possibility.
For a presentation (with some nice modification – the three points on the affine line are treated symmetrically) of the Croot-Lev-Pach-Ellenberg-Gijswijt capset and further discussion see this post and comment thread on Terry Tao’s blog.
Update: Eric Naslund and Will Sawin gave a direct proof based on the polynomial method for the Erdos-Szemeredi sunflower conjecture (for three petals), and an even stronger result is given by Naslund here. I will try to give more updates on applications of the Croot-Lev-Pach-Ellenberg-Gijswijt breakthrough at the end of this post.