It is time for a new polymath10 post on the Erdos-Rado Sunflower Conjecture. (Here are the links for post1, post2, post3.) Let me summarize the discussion from Post 3 and we can discuss together what directions to peruse. It is a pleasure to mention that in parallel Tim Gowers is running polymath11 aimed for resolving Frankl’s union closed conjecture. Both questions were offered along with the Erdos discrepancy problem and the Erdos-Hajnal conjecture in this 2009 post by Tim. In fact, some people participate both in polymath10 and polymath11. The acronym for polymath 11 is FUNC and I suppose we can choose between SUN or ERSC or some other options for polymath10.
Because of polymath10, I did not discuss over here other things. Let me mention two super major developments that I am sure you all know about. One is Laci Babai’s quasi-polynomial algorithm for Graph isomorphism. (This is a good time to mention that my wife’s mother’s maiden name is Babai.) You can read about it here (and the next three posts) and here. Another is the solution by Jean Bourgain, Ciprian Demeter, Larry Guth of Vinogradov’s main conjecture. You can read about it here and here.
We denoted by the largest cardinality of a family of -sets without a sunflower of size , and the largest cardinality in a family of -subsets of with the property , namely without a sunflower of size with head of size at most . Adding the subscript for refer to balanced families rather than to arbitrary family. The “Erdos-Ko-Rado regime” is when and is arbitrary or when and is arbitrary. (In this regime the property is preserved under shifting.)
Results by Ferdinand Ihringer
Ferdinand gave interesting upper bounds and lower bounds for in terms of .
Proposal by Domotor Palvolgyi
Domotor raised in this comment and the following ones some ideas for using algebraic methods for the sunflower conjecture. This have led to an interesting discussion (following these comments) between Domotor and Ferdinand on connection between Sunflowers and Ramsey numbers (mainly ).
So that this post will not interrupt this interesting discussion let me quote the beginning of Domotor’s comment posted minutes ago:
“So let us denote the size of the largest -uniform family without (different) sets whose pairwise intersection has the same size by . As we have seen in the earlier discussion, trivially and (where in the last Ramsey notation we forbid in a -coloring of the complete graph). Mysteriously, for all three functions we have similar lower and upper bounds. In this comment I propose to try proving for some .”
Proposal by Shachar Lovett.
Shachar Lovett proposed in this comment how to use the topological Tverberg theorem for attacking a certain important special case of the conjecture.
Reminder: Reduction to the balanced case, Phillip Gibbs’ construction, and more drastic reductions.
We started with the observation that every family of -sets contains a balanced subfamily of size . (BTW for graphs there is a sharper result by Noga Alon and it would be interesting to extend it to hypergraphs!) This gives that
Phillip Gibbs showed in this comment that if the sunflower conjecture is true then
It will be interesting to describe precisely what (1+o(1)) stands for, and improve it as much as possible. All left to be done for a counterexample to the sunflower conjecture is to complement Phillip construction by another one showing an exponential gap between the balanced and general case. This is certainly a tempting direction.
More drastic reductions then the very basic one are also possible, for example: for families of -subsets without a sunflower of size 3 it is enough to consider families with elements colored by colors such that every set is colored by consecutive colors and two sets sharing elements are not using the same color-intervals. (This implies “high girth” of some sort.) We can ask if this type of reductions is useful for proving the conjecture, if one can show (like Phillip) that assuming the conjecture, the gap between the bounds for this version is not too large compared to the general version, and hope that this can be part of a construction going in the negative direction.
The Homological/Algebraic Approach
In quite a few comments to post 3, I tried to further develop the homological ideas (and to mention some low hanging fruits and related questions). We did reach a major obstacle sending us back to the drawing board. I see some possible way around the difficulty and I will now describe it. For this purpose I will review the homological ideas in somewhat more general and very elementary context. (We only briefly mention the connection with cycles/homology but it is not needed).
Compound matrices, weak isomorphism and dominance.
Let be a generic matrix. The -th compound matrix is the matrix of by minors. Namely, , where .
Given two -unform hypergraphs we say that and are weakly isomorphic if the minor of whose rows and columns correspond to sets in and respectively is non-singular. (It is fairly easy to see that if and are isomorphic then they are weakly isomorphic. This relies on the condition that is generic.) We will say that dominates if and is full rank. Thus, and are weakly isomorphic if each dominates the other.
Let be the set of -subsets of such that . The connection with our notions of acyclicity is as follows: is acyclic (i.e. ) iff is dominated by . In greater generality, iff is dominated by . (In particular, iff is dominated by , and iff is dominated by $D[m,m]$.) Remark: Here and later in the post with since we deal only with cycles for the top dimension, so there are no “boundaries” to mod out.
A family of -subsets of is shifted if whenever and is obtained by replacing an element by a smaller element then . It can be shown that two shifted families of the same size are weakly isomorphic only if they are equal! We can use our compound matrix to describe an operation (in fact, several operations) called shifting which associated to a family a shifted family . Suppose that . is the lexicographically smallest family of sets which is weakly isomorphic to . In more details: we first consider a total ordering on -subsets of . Then we greedily build a hypergraph which is dominated by . When we reach sets we obtain a hypergraph weakly isomorphic to .
Now, if the total ordering is the lexicographic order on then we denote and call the “algebraic shifting” of . In this case, it can be shown that the resulting family is shifted. Also of special importance is the case that is the reverse lexicographic order.
For sets of integers of size , the lexicographic order refers to the lexicographic order when we ordered the elements of every set from increasingly, and the reverse lexicographic order is the lexicographic order when we order the elements decreasingly.
From 12<13<14<15<…<21<22<…<31<32<… we get
and from 21<31<32<41<42<43<51<52<… we get
We mention again some connection with acyclicity and homology: is acyclic if all sets in contains ‘1’. is -acyclic iff all sets in in intersect . is -acyclic iff all sets in contains . For general , -acyclicity is not expressed by those two versions of algebraic shifting, however, is -cyclic if .
Algebraic shifting in the Erdos-Ko-Rado regime.
The following properties are preserved under algebraic shifting:
(1) Every two members of has at least elements in common.
(2) There are no pairwise disjoint sets in .
For balanced families we know even more:
(3) If is balanced and every two members of has at least elements in common then all sets in contains .
(4) If is balanced and there are no pairwise disjoint sets in , then every set in intersects .
Reverse shifting in the Erdos-Ko-Rado regime.
As it turns out we have much stronger statements:
The following properties are preserved under reverse-lexicographic algebraic shifting:
(5) Every two members of has at least elements in common.
(6) There are no pairwise disjoint sets in .
(I dont know if (3) and (4) extends as well. It certainly worth the effort to check it.)
Modified plan for attack:
Our ultimate conjecture remains the same:
Main Conjecture: If has no sunflower of size then it is -acyclic. (I.e., )
For balanced family we conjectured that and for the non-balance we had a larger value .
Our homological approach mainly for the balanced case was to use the local homological condition from (2) (or(4)) (with some additional homological condition yet to be proved – this was Conjecture A) to conclude (This was Conjecture B) that is -acyclic. However, Conjecture B turned out to be false. Our new idea is to replace the local conditions on homology obtained from (2), (4) by those given by (6) which are apparently quite stronger.
We also tried to explore how to prove the main conjecture via an even stronger statement for “combinatorial cycles”. This works for the balanced case in the Erdos-Ko-Rado-regime (leading to some interesting consequences). But we did not manage to extend it beyond this regime. Domotor shoot down some half-baked attempts towards such a goal.
What we propose now is to use the following theorem instead of Conjecture A and to greatly modify Conjecture B accordingly. (For general families; being balanced is not used.)
Theorem: Let is a family of -sets without a sunflower of size . Then
(*) For every family of -sets which is the link of a set of size (including the case , Every set in intersect .
Conjecture B (greatly modified): For a family of -sets satisfying (*) we have
This is the new plan! Below are a couple of comments.
A new homological translation:
We can, I think, translate the condition on reverse lexicographic shifting also to some conditions on homology, given in this comment, but the connection is still a little dubious and need some further checking and explanation. (Specifically, it relies on a comment I make in my paper on algebraic shifting that if is a family of -subsets of and is its complement, then the shifting of is related to the reverse lexicographic shifting of as follows: takes the complement of and apply the involution sending element to .)
If is the simplicial complex spanned by our family and is the simplicial complex spanned by the complement of we want to replace conditions of the form
by the stronger condition
For example, for a graph with vertices and edges gives all edges containing ‘1’ (which is equivalent to (*) for ) if and only if is a tree. But requiring it for implies (I think) that be a star and is equivalent (I think) to , where is the complement of .
We plan to run computer experimentation to test some of these ideas on small cases.
A few words on symmetric shifting and related notions of homology.
Let me mention that there is a variant of compound matrix, weak equivalence and of algebraic shifting (and hence also of the various homology groups we considered,) when we use symmetric products instead of exterior products. The theories based on those variants are very similar, and the advantage of the notions based on symmetric powers is that they are closer to studied notions of commutative algebra. (But I think they will be harder to compute as determinants are replaced by permanents.)