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