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) 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 maximum number of edges in a 3-uniform hypergraph on n vertices with the property that every four vertices span at least one triangle?
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 monitory 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.
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.