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

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

A class of matroids defined on hypergraphs

Let be the -uniform hypergraph which consists of all -subsets of [n] that intersect [r]. For a -uniform hypergraph on the vertex set [n] let . For the complete -uniform hypergraph on vertices () .

 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 is a Turan (4,3)-hypergraph with vertices then

This conjecture is a refinement of Turan’s conjecture. (The conjectured 1940 lower bound by Turan can be written as  .) It is known for (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 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 .

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

Our ultimate conjecture is:

Main Conjecture:  If has no sunflower of size then it is -acyclic. (I.e., )

An equivalent formulation in terms of reverse lexicographic shifting is:

(**) .

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

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

(**) .

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