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.
Gil — in your statement of Turan’s (4,3) problem, should “maximum” be “minimum”?
GK: Oops. corrected, thanks!
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!
Thanks! regarding Jordan’s comment see also this riddle https://gilkalai.wordpress.com/2009/01/15/a-riddle/
Pingback: Why I want to be a Mathematician? | Gaurish4Math
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.
Pingback: Polymath10 conclusion | Combinatorics and more