Polymath10-post 4: Back to the drawing board?

Posted on January 31, 2016 by Gil Kalai

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.

Polymath10:

We denoted by $f(k,r)$ the largest cardinality of a family of $k$ -sets without a sunflower of size $r$ , and $f(k,r,m,n)$ the largest cardinality in a family of $k$ -subsets of $[n]$ with the property $P(r,m)$ , namely without a sunflower of size $r$ with head of size at most $m$ . Adding the subscript $b$ for $f_b(k,r),f_b(k,r,m,n)$ refer to balanced families rather than to arbitrary family. The “Erdos-Ko-Rado regime” is when $r=2$ and $m$ is arbitrary or when $m=1$ and $r$ is arbitrary. (In this regime the property $P(r,m)$ is preserved under shifting.)

Results by Ferdinand Ihringer

Ferdinand gave interesting upper bounds and lower bounds for $f(k,r,m,n)$ in terms of $f(k,r)$ .

$f(m, r) \leq f(k, r, m, n) / \binom{n-m}{k-m} \leq 10 f(k, r)^3.$

For the upper bound see this writeup by Ferdinand. For more details see this comment and the following ones. It will be interesting to find sharp lower and upper bounds.

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 $R_3(k)$ ).

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 $k$ -uniform family without $r$ (different) sets whose pairwise intersection has the same size by $g(k,r)$ . As we have seen in the earlier discussion, trivially $g(k,r)\le f(k,r)$ and $g(k,r)\le R_r(k)$ (where in the last Ramsey notation we forbid $K_r$ in a $k$ -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 $f(k,r) \le g(ck,r)$ for some $c$ .”

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 $F$ of $k$ -sets contains a balanced subfamily of size $\frac {k!}{k^k}|F|$ . (BTW for graphs there is a sharper result by Noga Alon and it would be interesting to extend it to hypergraphs!) This gives that

$f(k,r) \le e^kf_b(k,r).$

Phillip Gibbs showed in this comment that if the sunflower conjecture is true then

$f_ (k,r) \le (1+o(1))^kf_b(k,r).$

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 $k$ -subsets without a sunflower of size 3 it is enough to consider families with elements colored by $100k$ colors such that every set is colored by consecutive colors and two sets sharing $k-1$ 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 $X=(x_ij)_{1 \le i \le n, 1 \le j \le n}$ be a generic matrix. The $k$ -th compound matrix $C_k(X)$ is the matrix of $k$ by $k$ minors. Namely, $C_k(X)=x_{ST}$ , $S,T \in {{[n]} \choose {k}}$ where $x_{ST}=det(x_{ij})_{i \in S,j\in T}$ .

Given two $k$ -unform hypergraphs $F,G$ we say that $F$ and $G$ are weakly isomorphic if the $m\times m$ minor $C_{F,G}(X)$ of $C_k(X)$ whose rows and columns correspond to sets in $F$ and $G$ respectively is non-singular. (It is fairly easy to see that if $F$ and $G$ are isomorphic then they are weakly isomorphic. This relies on the condition that $X$ is generic.) We will say that $F$ dominates $G$ if $|F|\ge |G|$ and $C_{F,G}(X)$ is full rank. Thus, $F$ and $G$ are weakly isomorphic if each dominates the other.

Let $D[b,c]$ be the set of $k$ -subsets $S$ of $[n]$ such that $|S \cap [b]|\ge c$ . The connection with our notions of acyclicity is as follows: $F$ is acyclic (i.e. $Z_{k-1}(K)=0$ ) iff $F$ is dominated by $D[1,1]$ . In greater generality, $K_{k-1}[b,c]=0$ iff $F$ is dominated by $D[b,c]$ . (In particular, $Z_{k-1} [r,1](K)=0$ iff $F$ is dominated by $D[r,1]$ , and $Z_{k-1}[m,m](K)=0$ iff $F$ is dominated by $D[m,m]$.) Remark: Here and later in the post $Z_*[b,c]$ with $H_*[b,c]$ since we deal only with cycles for the top dimension, so there are no “boundaries” to mod out.

Algebraic shifting

A family $F$ of $k$ -subsets of $[n]$ is shifted if whenever $S \in F$ and $R$ is obtained by replacing an element by a smaller element then $R \in F$ . 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 $F$ a shifted family $\Delta_T(F)$ . Suppose that $|F|=m$ . $\Delta (F)$ is the lexicographically smallest family of sets which is weakly isomorphic to $F$ . In more details: we first consider a total ordering $T$ on $k$ -subsets of $[n]$ . Then we greedily build a hypergraph which is dominated by $F$ . When we reach $m$ sets we obtain a hypergraph $\Delta_T(F)$ weakly isomorphic to $F$ .

Now, if the total ordering is the lexicographic order on ${{[n]} \choose {k}}$ then we denote $\Delta(F)=\Delta_T(F))$ and call $\Delta(F)$ the “algebraic shifting” of $F$ . In this case, it can be shown that the resulting family is shifted. Also of special importance is the case that $T=RL$ is the reverse lexicographic order.

For sets of integers of size $k$ , 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

$\{1,2\} <_L \{1,3\} <_L \{1,4\}$ $\dots <_L$ $\{ 2,3\} <_L$ $\{2,4\} <_L \dots$

and from 21<31<32<41<42<43<51<52<… we get

$\{1,2\} <_{RL} \{1,3\}<_{RL}\{2,3\}<_{RL}\{1,4\}\dots$

We mention again some connection with acyclicity and homology: $F$ is acyclic if all sets in $\Delta (F)$ contains ‘1’. $F$ is $[r,1]$ -acyclic iff all sets in in $\Delta (F)$ intersect $[r]$ . $F$ is $[m,m]$ -acyclic iff all sets in $\Delta(F)$ contains $[r]$ . For general $b,c$ , $[b,c]$ -acyclicity is not expressed by those two versions of algebraic shifting, however, $F$ is $[s,k]$ -cyclic if $\Delta_{RL}(F) \subset {{[s]}\choose{k}}$ .

Algebraic shifting in the Erdos-Ko-Rado regime.

The following properties are preserved under algebraic shifting:

(1) Every two members of $F$ has at least $m$ elements in common.

(2) There are no $r$ pairwise disjoint sets in $F$ .

For balanced families we know even more:

(3) If $F$ is balanced and every two members of $F$ has at least $m$ elements in common then all sets in $\Delta(F)$ contains $[m]$ .

and

(4) If $F$ is balanced and there are no $r$ pairwise disjoint sets in $F$ , then every set in $\Delta(F)$ intersects $[r-1]$ .

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 $F$ has at least $m$ elements in common.

(6) There are no $r$ pairwise disjoint sets in $F$ .

(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 $F$ has no sunflower of size $r$ then it is $[xk,k]$ -acyclic. (I.e., $Z_{k-1}[(xk,k](K)=0.$ )

For balanced family we conjectured that $x=(r-1)$ and for the non-balance we had a larger value $x=r$ .

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 $F$ is $[xk,k]$ -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 $F$ is a family of $k$ -sets without a sunflower of size $r$ . Then

(*) For every family of $i$ -sets $F'$ which is the link of a set of size $k-i$ (including the case $F'=F)$ , Every set in $\Delta _{RL}(F')$ intersect $[(r-1)i]$ .

Conjecture B (greatly modified): For a family $F$ of $k$ -sets satisfying (*) we have

(**) $\Delta_{RL}(F) \subset {{[rk]}\choose{k}}$ .

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 $F$ is a family of $k$ -subsets of $[n]$ and $G$ is its complement, then the shifting of $F$ is related to the reverse lexicographic shifting of $G$ as follows: takes the complement of $\Delta (F)$ and apply the involution sending element $i$ to $n-i$ .)

If $K$ is the simplicial complex spanned by our family $F$ and $L$ is the simplicial complex spanned by the complement of $F$ we want to replace conditions of the form

(*) $Z_{k-1}[s,1] (K)=0$

by the stronger condition

(**) $Z_{k-1}[n-s-k,1] (L)\ne 0$

For example, for a graph $G$ with $n$ vertices and $n-1$ edges $\Delta (G)$ gives all edges containing ‘1’ (which is equivalent to (*) for $s=1$ ) if and only if $G$ is a tree. But requiring it for $\Delta_{RL}(G)$ implies (I think) that $G$ be a star and is equivalent (I think) to $Z_1[n-3,1](\bar G)\ne 0$ , where $\bar G$ is the complement of $G$ .

Planned experimentation.

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.)

This entry was posted in Combinatorics, Mathematics over the Internet, Polymath10. Bookmark the permalink.

12 Responses to Polymath10-post 4: Back to the drawing board?

Pingback: Polymath 11 is Now Open | The polymath blog
Eran Nevo says:

February 8, 2016 at 9:46 pm

Dear Gil, the new Conjecture B looks beautiful! Is it true for r=2?
Some small remarks:
> Conjecture B is true for F a shifted family. (Delta_RL acts as identity on shifted families, and just relabels vertices in their face links to make them shifted.)
> Can we replace [rk] by a shorter interval in (**)? At least [rk-1] looks “as safe as [rk]”. In other words, what is the smallest value x=x(r,k) for which (**) holds with [rk] replaced by [x]?
Of course, for concluding the sunflower conjecture we don’t need tightness in (**) and replacing [rk] in (**) by [f(r)k] will do for any function f(r).
> The relation between reverse-lexicographic and usual exterior algebraic shifting of the complementing family mentioned above, looks wrong:
for F consisting of 2 disjoint triangles, Delta_RL(F) consists of all edges in the initial segment 12,..,34 w.r.t. rev-lex order, while the recipe above tells us to replace 34 by 15.
In fact, Gil suspected this very counterexample.

Reply
Gil Kalai says:

February 8, 2016 at 11:00 pm

Thanks, Eran! How do we show that the RL-shifting of two disjoint triangles consist of 12,…,34?
(Namely there are no dependences for them)?

Reply
Eran Nevo says:

February 9, 2016 at 1:05 am

One checks that {12,13,23,14,24,34} is weakly isomorphic to {12,13,23,45,46,56}.
Specifically, in the determinant of the relevant 6X6 minor of the compound matrix, one observes that the sum of all monomials divisible by (x_11x_22x_33)^2 is nonzero. I did this “by inspection”, it will be good if someone can double-check it.

Reply
- Gil Kalai says:
  
  February 11, 2016 at 1:41 am
  
  Hmm, this is interesting. In some sense it is good news as it shows that $_{k-1}[2k,k](K)$ may hold for all families of $k$ -sets without a sunflower of size 3. (We don’t have even a “plan” for proving such a strong result, our plan is for weaker statements.) On the other hand, it leaves us without a clear homological interpretation of properties regarding reverse lexicographic algebraic shifting (and shows that some comments from some old paper of mine are incorrect.) I guess we will have to look carefully at that.
  
  Reply
Gil Kalai says:

February 18, 2016 at 7:10 am

Since we did not have comments for a while let me mention that I do plan to return to various topics from this post, and related ones. I also hear about various applications of the sunflower theorem where s
ometimes an improvement towards the conjecture is important and sometimes less so. So at some point I will report about it. I also plan to have some computer experimentation regarding quasi-isomorphism, shifting, and various homologies for balanced and non balanced sunflower free families.

Reply
- domotorp says:
  
  February 18, 2016 at 4:43 pm
  
  Great to know. I would be very interested in some computer programs, others also promised to have some, but no news from anyone yet.
  
  Reply
  - Ferdinand Ihringer says:
    
    February 18, 2016 at 8:18 pm
    
    I would be very interested as well. Some things:
    
    (1) I think that I have promised a computer program. I just used a MILP solver. For $f(k, r, m, n)$ I used the obvious approach and then I forgot to write up the results in a readable way. I have to do that as soon as I find some time for it … I just deprioritized it for the moment.
    
    (2) I still plan to improve my upper bound in a way such that the upper bound uses some polynomial in $f(m, r)$ instead of $f(k, r)$ . Otherwise it this feels unfinished. I have a vague idea on how this should work, but I would need a week to think about it.
    
    (3) I intend to bring (2) in particular and Polymath 10 in general to a small workshop in a few weeks. Maybe something will come from this and I will report here.
    
    After I failed or succeeded with (2), I will finally try to join the main approach using homologies.
  - Ferdinand Ihringer says:
    
    February 20, 2016 at 5:19 pm
    
    Now that I am going through my write-up yet another time, I noticed a tiny mistake in my calculations. My bound on $n$ is always $n \geq m(k-m) \binom{2k}{k} + m$ , not $n \geq m(k-m) \binom{2k-m}{m+1} + m$ . I will update my write-up in some time (I will just replace the existing file in some time). I suppose that the old condition is true as well, but there is no argument for this in my write-up.
Pingback: The Quantum Computer Puzzle @ Notices of the AMS | Combinatorics and more
domotorp says:

May 14, 2016 at 10:41 am

https://quomodocumque.wordpress.com/2016/05/13/bounds-for-cap-sets/

Reply
Pingback: Polymath10 conclusion | Combinatorics and more

	Questions and Concer… on Inaugural address at the Hunga…
	Questions and Concer… on The Argument Against Quantum C…
	Questions and Concer… on Physics Related News: Israel J…
	Questions and Concer… on The Google Supremacy Experimen…
	Questions and Concer… on Remarkable: “Limitations…
	Questions and Concer… on Ordinary computers can beat Go…
	Questions and Concer… on Amazing: Feng Pan and Pan Zhan…
	Gil Kalai on An Aperiodic Monotile
	Gil Kalai on Physics Related News: Israel J…
	Mostafa Touny on Physics Related News: Israel J…
	Gil Kalai on Stand Clear of The Closing Doo…
	Gil Kalai on Test your intuition 52: Can yo…

Polymath10-post 4: Back to the drawing board?