Polymath 10 post 6: The Erdos-Rado sunflower conjecture, and the Turan (4,3) problem: homological approaches.

Posted on May 27, 2016 by Gil Kalai

In earlier posts I proposed a homological approach to the Erdos-Rado sunflower conjecture. I will describe again this approach in the second part of this post. Of course, discussion of other avenues for the study of the conjecture are welcome. The purpose of this post is to discuss another well known problem for which a related homological approach, might be relevant. The problem is the Turan (4,3) problem from 1940.

We will not regard attacks on the sunflower conjecture based on the recent solution of the cap set problem and the Erdos Szemeredi sunflower conjecture (which is a weaker version of the Erdos-Rado conjecture that we considered in post 5) as part of the present polymath10 project, but, of course, I will be happy to hear also reports on progress or comments on these directions. Some updates on this story: Eric Naslund and Will Sawin gave a direct proof based on the polynomial method for the Erdos-Szemeredi sunflower conjecture, and an even stronger result is given by Naslund here. (Eric also has stronger quantitative bounds for Erdos-Szemeredi based on bounds for cap sets.) More cap set updates are added to this post, and can be found in the comment threads here and here.

Turan’s (4,3) problem

Turan’s 1940 problem is very easy to state.

What is the minimum of edges in a 3-uniform hypergraph on n vertices with the property that every four vertices span at least one triangle?

We talked about the problem (and a little about the homological approach to it) in this post and this post.

Four things that the Erdos-Rado sunflower problem and the Turan (4,3) problem have in common.

4. 1000 dollars or so Erdos prize

If I remember correctly, the Turan’s problem is the only question not asked by Erdos himself for which he offered a monetary award.

3. The homological approach might be relevant.

This is what this post is going to be about. But while this connection is still tentative and speculative, the next connections between the two problems are solid.

2. Sasha Razborov

Sasha used the Erdos-Rado sunflower theorem in his famous theorem on superpolynomial lower bounds for monotone circuits, and his flag-algebra theory have led to remarkable progress and the best known upper bound for the Turan (4,3) problem. (See here and here .)

1. Sasha Kostochka

Sasha holds the best known upper bound for the sunflower conjecture and he found a large class of examples for the equality cases for the Turan (4,3) conjecture.

Quasi-isomorphism of hypergraphs

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.

A class of matroids defined on hypergraphs

Let $G(k,r,n)$ be the $k$ -uniform hypergraph which consists of all $k$ -subsets of [n] that intersect [r]. For a $k$ -uniform hypergraph $F$ on the vertex set [n] let $rank_r(F) = rank C_{F,G(k,r,n)}$ . For the complete $k$ -uniform hypergraph $K$ on $n$ vertices ( $n \ge r$ ) $rank_r(K)={{n}\choose {k}} - {{n-r} \choose {k}}$ .

Homological approach to Turan’s (4,3) problem.

We refer to a 3-uniform hypergraph with the property that every four vertices span at least one triangle as a Turan (4,3)-hypergraph.

Conjecture: If $F$ is a Turan (4,3)-hypergraph with $n$ vertices then

$rank_r(F) \ge r {{n-r-1}\choose {2}}.$

This conjecture is a refinement of Turan’s conjecture. (The conjectured 1940 lower bound by Turan can be written as $\max (r{{n-r-1} \choose {2}}: r\ge 1)$ .) It is known for $r=1$ (see this post) and an analogous statement is known for Turan (3,2)-graphs.

We would like to find even stronger algebraic statements which amounts not only to upper bounds on certain homology-like groups but to stronger statements about vanishing of certain homology-like groups.

I am also curious about

Question: Are all extremal examples with n vertices for the Turan (4,3) problem quasi-isomorphic? If this is the case we can also conjecture that every Turan (4,3) hypergraph dominates Turan’s example on the same number of vertices.

I hope to be able to present some experimental data on these problems.

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}}$ .

The (current) homological approach to the Sunflower problem: a reminder.

Our ultimate conjecture is:

Main Conjecture: If $F$ has no sunflower of size $r$ then it is $[rk,k]$ -acyclic. (I.e., $Z_{k-1}[(rk,k](K)=0.$ )

An equivalent formulation in terms of reverse lexicographic shifting is:

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

Our current proposal is to use the following theorem and (a greatly modify) Conjecture B. (For general families.)

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 (from post 4, greatly modified from the one discussed in posts 2,3): For a family $F$ of $k$ -sets satisfying (*) we have

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

Also here, I hope to be able to present some experimental data soon.

6 Responses to Polymath 10 post 6: The Erdos-Rado sunflower conjecture, and the Turan (4,3) problem: homological approaches.

JSE says:

May 27, 2016 at 6:32 pm

Gil — in your statement of Turan’s (4,3) problem, should “maximum” be “minimum”?

GK: Oops. corrected, thanks!

Reply
domotorp says:

May 27, 2016 at 10:09 pm

Or maybe it should be that every four vertices miss a triple. Two more typos from the beginning: monitory should be monetary and x_ij should be x_{ij}.

GK: thanks! corrected!

Reply
Gil Kalai says:

May 27, 2016 at 11:06 pm

Thanks! regarding Jordan’s comment see also this riddle https://gilkalai.wordpress.com/2009/01/15/a-riddle/

Reply
Pingback: Why I want to be a Mathematician? | Gaurish4Math
Gil Kalai says:

June 8, 2016 at 5:13 pm

It is worth noting that “weak-isomorphism” is not transitive. The reason is that two shifted hypergraph of the same cardinality are weakly isomorphic iff they are the same. Every hypergraph is weakly isomorphic to its rev-lex shifting and to its lex shifting but in many cases these two shiftings give different outcomes.

Reply
Pingback: Polymath10 conclusion | Combinatorics and more

	Gil Kalai on Gérard Cornuéjols’s bake…
	Abstractness on Amazing: Karim Adiprasito prov…
	Gil Kalai on The story of Poincaré and his…
	Peter Shor on The story of Poincaré and his…
	Gil Kalai on What do Firms Want?
	Gil Kalai on Noisy quantum circuits: how do…
	World News OK, WTF I… on Quantum computers: amazing pro…
	Quantum computers: a… on The story of Poincaré and his…
	Craig on The story of Poincaré and his…
	Gil Kalai on The story of Poincaré and his…
	Craig on The story of Poincaré and his…
	Rao on The story of Poincaré and his…