We launched polymath10 a week ago and it is time for the second post. In this post I will remind the readers what the Erdos-Rado Conjecture and the Erdos-Rado theorem are, briefly mention some points made in the previous post and in the comments, make some remarks of administrative nature, and describe in detail a homological plan for attack, some of whose ingredients were mentioned in the first post.
Of course, there are various other avenues that can be explored: In a series of comments (e.g. this thread and that thread and this) Tim Gowers proposed a line of attack related to understanding quasirandom behavior of families of sets in terms of their pairwise intersections. (Update: Tim developed his ideas in further comments. A theme which is common to his approach as well as to the homological approach is to see if we can “improve” certain properties of the family after moving to an exponentially smaller subfamily. Second update: this post was written after 70 or so comments for post 1. There are many further interesting comments. ) Karim Adiprasito described a different topological combinatorics approach. Another clear direction is to try to extend the ideas of Spencer and Kostochka which led to the best known bounds today. Raising more ideas for attacking the conjecture is most welcome. For example, in Erdos Ko Rado theory, besides direct combinatorial arguments (mainly those based on “shifting,”) spectral methods are also quite important. Of course, the sunflower conjecture may be false as well and ideas on how to construct large families without sunflowers are also most welcome.
Terry Tao kindly set a Wiki page for the project and proposed to conduct computer experimentation for small values of and
. Of course, computer experimentation will be most welcome! Some of the suggestions described below can also be tested experimentally for small values.
Let me also mention some surprising connections between the sunflower conjecture and various issues arising in matrix multiplication. As pointed by Shachar Lovett (in this comment and the following one), a counterexample to a certain structural special case of the sunflower conjecture will imply an almost quadratic algorithm for matrix multiplication!
Dömötör and I hyperoptimistically conjectured that the Erdos-Rado example is optimal for Balanced families. But Hao gave a very simple counterexample.
The status of our project at this stage is described very nicely by Tim Gowers who wrote:
At the time of writing, Gil’s post has attracted 60 comments, but it is still at what one might call a warming-up stage, so if you are interested in the problem and understand what I have written above, it should still be easy to catch up with the discussion. I strongly recommend contributing — even small remarks can be very helpful for other people, sparking off ideas that they might not have had otherwise. And there’s nothing quite like thinking about a problem, writing regular bulletins of the little ideas you’ve had, and getting feedback on them from other Polymath participants. This problem has the same kind of notoriously hard feel about it that the Erdős discrepancy problem had — it would be wonderful if a Polymath collaboration could contribute to its finally getting solved.
Update to an earlier post. Karim Adiprasito, June Huh, and Eric Katz have now posted their paper “Hodge theory for combinatorial geometries” which contains, among other things, a proof of the Heron-Rota-Welsh conjecture on matroids.
Here is a reminder of the sunflower theorem and conjecture:
The Erdos-Rado sunflower Theorem
A sunflower (a.k.a. Delta-system) of size is a family of sets
such that every element that belongs to more than one of the sets belongs to all of them. We call the common element to all the sets the head of the sunflower (or the kernel of the sunflower), and the elements that belong to just one among the sets, the petals.
A basic and simple result of Erdos and Rado asserts that
Erdos-Rado sunflower theorem: There is a function so that every family
of
-sets with more than
members contains a sunflower of size
.
We denote by the smallest integer that suffices for the assertion of the theorem to be true.
The Erdos-Rado Sunflower Conjecture
The Erdos-Rado sunflower conjecture: .
Here, is a constant depending on
. It may be also the case that we can take
for some absolute constant C. The conjecture is already most interesting for
. I recommend to reading Kostochka’s survey paper and also, as we go, it will be useful to learn Spencer’s argument and Kostochka’s argument which made remarkable improvements over earlier upper bounds.
The main purpose of this post is to provide
A Homological attack on the sunflower Conjecture
Part 1: Combinatorial Extensions and Variations
A) The question as an Erdos-Ko-Rado type question
Let be the maximum size of a family
of
-subsets of [n]=
containing no sunflower of size
with head of size at most
. (Note: it should me
.)
Basic Question: Understand the function f(k,r,m;n). Is it true that , where
is a constant depending on r, perhaps even linear in r.
A family of -sets satisfies property P(k,r,m) if it contains no sunflower of size
with head of size at most
.
B) Stars and links: Given a family of sets and a set
, the star of
is the subfamily of those sets in
containing
, and the link of
is obtained from the star of
by deleting the elements of
from every set in the star. Another way to say that
has property P(k,r,m) is that the link of every set of size
at most less than contains no
pairwise disjoint sets.
C) The balanced case
A family of -sets is balanced (or
-colored, or multipartite) if it is possible to divide the ground set into
parts so that every set in the family contains one element from every part.
Let be the maximum size of a balanced family
of
-subsets of [n]=
containing no sunflower of size
with head of size at most
. By randomly dividing the ground set into colors we obtain that
.
D) What we aim for. Below we describe two variations of a homological attack on the sunflower conjecture. If successful (as they are) they will lead to the following bounds.
The first variation based on conjectured homological properties of balanced families would yield
(*)
The alternative version would give
(**)
Part 2: Collections of sets as geometric objects, homology and iterated homology.
E) Simplicial complexes and homology
Staring with a family we will consider the collection of sets obtained by adding all subsets of sets in
. This is a simplicial complex,
, and we can regard it as a geometric object if we replace every set of size
by a simplex of dimension
. (We call sets in
of cardinality
by the name i-faces.
The definition of homology groups only depends on the combinatorial data. For simplicity we assume that all sets in (and hence in the associated simplicial complex) are subsets of {1,2,…,n}. We choose a field A (we can agree that the field will be the field of real numbers). Next we define for i>0 the vector space of
-dimensional chains
as a vector space generated by i-faces of K. We also define a boundary map
for every
. The kernel of
is the space of i-cycles denoted by
; the image of
is the space of i-boundaries, denoted by
. The crucial property is that applying boundary twice gives you zero, and this allows to define homology groups
. The betti numbers are defined as
. We will give the definition of the boundary operator further below.
F) Acyclic families and intersecting families
A family of
-sets is acyclic if it contains no
-cycle, or equivalently if
. (For coefficients in
, a
-cycle
is a family of
-sets such that every set of size
is included in an even number of
-sets in
.)
Proposition: An acyclic family of k-subsets of [n], contains at most sets.
In the first post we asked: Are there some connections between the property “intersecting” and the property “acyclic?”
Unfortunately, but not surprisingly intersecting families are not always acyclic, and acyclic families are not always intersecting. (The condition from EKR theorem also disappeared.) As we mentioned in the previous post intersecting balanced families are acyclic! And as we will see for balanced families Erdos-Ko-Rado properties translate nicely into homological property.
G) Pushing the analogy further
We made an analogy between “intersecting” and “acyclic”. Building on this analogy
1) What could be the “homological” property analogous to “every two sets have at least m elements in common”?
2) What could be the “homological” property analogous to “not having r pairwise disjoints sets”?
I will propose answers below the fold. What is your answer?
H) Weighted homology
For a simplicial complex on the vertex set [n] the boundary operator
is defined by
. Where
.
Given a vector of nonzero weights
we can define a weighted boundary operator by
,
where . It is a simple matter of scaling a matrix that still the boundary of the boundary is zero and (over any field) the homology with respect to this weighted boundary operator does not depend on
.
I) Iterated homology
Being acyclic guarantees that
1) What is the global homological property that will give us ?
2) What is the global homological property that will give us ?
Answer for 1: There is no chain in which vanishes when you apply m (generic) weighted boundary operators successively.
Answer for 2: There is no chain in which vanishes when you apply each one out of
(generic) weighted boundary operators.
When both answers coincide with the top dimensional homology
. For larger value of
those are kind of homology-like spaces whch are called “iterated homology.”
J) m-fold acyclic families (first try)
Iterated homology gives us global properties of a family of sets that we want to relate to Erdos-Ko-Rado-like properties P(m,r). But in order to make such a connection we first need to study the connection between local and global properties. Here, by “local” I refer to properties described in terms of links. Let’s go back to ordinary homology and try to understand the situation when we impose (top-dimension-) acyclicity on the family as well as on links. We will start with the simplest case: what about families which are acyclic, and all links of vertices are acyclic? Let us choose the case k=3, m=2.
Is the number of triangles in such a 2-fold acyclic family at most linear in ? perhaps even at most
?
Here is an example with more than triangles.
But things can get much worse: Consider a Steiner triple system: namely a collection of triangles where every pair of elements is included in one triangle. It is obviously 2-acyclic and the link of every vertex is a matching and thus, it is an acyclic graph. Still, we have quadratic number of triangles.
K) m-fold acyclic families revisited.
Theorem 1: Let be a family of
-sets and let
be the associated
-dimensional simplicial complex. Suppose that
a)
b)
and
c)
Then .
So we need a new crucial assumption: it is not enough to require that the top homology for the family and its links vanish, we need also that the th homology will vanish.
[One thing to keep in mind: Condition c) is not preserved when we delete sets from the family. We can hope that we can replace this condition by a weaker condition which is a monotone property relating th homology of
with
th homology of links of vertices. For every vertex
there is a map from
to
. Perhaps the property is that this map is surjective for every vertex. update (Dec 13) I am less certain about what the property should be.]
This theorem extends also to every value of m.
Theorem 2: Let be a family of
-sets and let
be the associated
-dimensional simplicial complex. Suppose that
for every link of
(including
itself) whenever
, then
.
L) Collapsibility. An easier version of Theorem 2 is for the case that is “d-collapsible,” for
This is a combinatorial property which is stronger than the homology condition. Using a combinatorial strong form (like collapsibility) of the homological conditions may be relevant to our case as well.
M) A working conjecture that may assist an inductive argument.
The following working conjecture may be useful for some inductive arguments:
Working Conjecture: Suppose that is a family (or just a balanced family) of
-subsets of [n]. Suppose that for every element
the star of
contains a sunflower of size
with head of size
. Then
contains a sunflower of size
with head of size smaller than
.
Update: False as stated for general families: Fano plane fails it, as Dömötör pointed out. I dont have a cunterexample for balanced families.
Update: False also for balanced families, as Dömötör pointed out. I dont have a counterexample (general, or better balanced) for the case . (This case might be useful.)
PART III: Moving to the balanced case
N) Acyclicity and Erdos-Ko-Rado properties for balanced families.
Now we consider the various Erdos-Ko-Rado questions for balanced families and revisit the connection to homology. For example, note that for balanced families, if then one color class has just one element hence all sets in the family contains this element.
Proposition: For a balanced family of -sets
if every set of size
is included it at least
sets of size
, then
contains
pairwise disjoint sets.
Corollary: If is balanced and intersecting then it is acyclic. If
is balanced and has a
-cycle that vanished by applying each one of
generic boundary operations, then
contains
pairwise disjoint
-sets. [corrected]
O) The expected global consequences for balanced families without Delta systems
Conjecture 1 (special case of r=2): If is a balanced family of
-sets from [n] and every two sets in the family share at least
elements then there is no cycle in
which vanishes when you apply successively
different (generic) boundary operators.
Conjecture 1 (general case): If is a balanced family of
-sets from [n] without a sunflower of size
and head with less than
elements. (In other words, it has no
pairwise disjoint sets for every link of a set of size less than
.) Then there is no cycle in
which vanishes when you apply any combination of
boundary operators successively out of
different (generic) boundary operators.
This last conjecture would give
(*)
Part IV: An alternative ending to the program
P) Avoiding coloring
We had some difficulty to relating intersecting and acyclic families. One (conjectural) proposal was to move to balanced families. But another proposal is to relax the notion of acyclicity. (Essentially by adding additional boundary operators.)
Theorem 4: (1) Let be an intersecting family of
-subsets from [n]. Then there is no cycle in
which vanishes when you apply each one out of
(generic) boundary operators
(2) Let be a family of
-subsets from [n] without
pairwise disjoint sets, Then there is no cycle in
which vanishes when one applies every boundary operator out of
(generic) boundary operators.
(3) If F is a family of -sets from [n] and every two members of
share at least
elements then there is no cycle in
which vanishes when you apply any combination of m boundary operators successively out of
different (generic) boundary operators.
These follow directly from the fact that algebraic shifting preserves the property that is intersecting, the property that
has no
pairwise disjoint sets, and the property that every pairwise intersection has at least m elements.
Unfortunately, as we mentioned, the property of interest to us is not preserved under shifting. We can hope that the effect of the extra boundary operators, in an inductive argument will be as follows:
Q) The Conjecture for the alternative direction:
Conjecture 2: If is a family of
-sets from [n] and if it has no
pairwise disjoint sets for every link of a set of size less than
then there is no cycle in
which vanishes when you apply any combination of
boundary operators successively out of
different (generic) boundary operators.
This would give
(**)
Part V: Shifting
R) Shifting
We mentioned the shifting method in this post. A collection F of k-subsets from [n]={1,2,…,n} is shifted (or compressed) if whenever a set S is in the collection and R is obtained by S by lowering the value of an element, then R is also in the family.
A shifting process is a method to move from an arbitrary family to a shifted one with the same size. Erdos, Ko and Rado described a combinatorial method for shifting in their paper on the Erdos-Ko-Rado theorem. A very basic facts from Erdos-Ko-Rado theory is
(EKR) P(2,m) and P(r,1) are preserved under shifting.
But not having a sunflower is not preserved under shifting. It is still possible that not having a sunflower for the family is translated to a different statement for the family obtained from it by shifting and indeed we will formulate Conjectures 1 and 2 in these terms.
S) Algebraic shifting
Algebraic shifting was mentioned in this post. A good reference for it is this 2002 paper.
Here is a quick definition of algebraic shifting:
(1) Start with an by
generic matrix
.
(2) Next consider the th-compound
matrix whose entries correspond to the determinants all
by
minors of
. Order the rows and columns of
lexicographically.
(3) Given a family of
subsets of [n] consider the submatrix
of
whose columns are indexed by sets in
.
(4) Now, choose a basis to the rows of greedily, namely, go over the rows of
one by one and add a row to the basis if it does not depend on the earlier rows.
(5) The algebraic shifting of
is the family of indices for the rows in this basis.
Theorem: Property (EKR) continues to hold for algebraic shifting.
T) Algebraic shifting and homology
Algebraic shifting also preserves the Betti numbers as well as the dimension of various iterated homology groups.
For example, is acyclic, namely there is no
-chain that vanishes when a boundary operation is applied, if and only if all sets in
contains ‘1’.
There is no chain in which vanishes when you apply successively m weighted boundary operators if and only if all sets in
contains
.
There is no chain in which vanishes when you apply each one out of
(generic) weighted boundary operators, if and only every set in
contains an element
.
U) Our conjectures in terms of algebraic shifting
Conjecture 1 and 2 are equivalent to:
Conjecture 1′: Algebraic shifting of balanced families with property P(r,m) leads to a shifted family so that every set has at least m elements in the set {1,2,…,(r-1)k}.
Conjecture 2′: If is a family of k-subsets of {1,2,…,n} with property P(r,m) then for the algebraic shifting of
, every set has at least m elements in the set {1,2,…,m+(r-1)k}.
V) Balanced shifting
Even when dealing with balanced families we considered a shifting operation that does not preserve the balance structure.Variants for algebraic shifting for the balanced case were defined and may be useful. (EKR) is not known for balanced shifting.
Question: Does balanced shifting have property (EKR).
W) Methods from commutative algebra
Methods from commutative algebra are quite powerful for demonstrating (often in another language) results about algebraic shifting and iterated homology groups.
I think that in M) for your “working conjecture” a finite projective plane gives a counterexample.
Right, I overlooked that. In any case items L and M are calling to be on the alert for a “collapsibility-type” statement which may simplify proofs. But what I suggested is too strong.
Dömötör, I still wonder if the conjecture holds for the balanced case:
Working Conjecture (balanced case): Suppose that F is a balanced family of k-subsets of [n]. Suppose that for every element v, the star of v contains a sunflower of size r with head of size m. Then F contains a sunflower of size r with head of size smaller than m.
This is true for k=2, but fails for k=3. Let the set of vertices be
and the edges be the triples whose sum is even. Every v has r=2 sized sunflower, but there are no disjoint edges.
Hmm, right! very nice example! (BTW do you have a quick way to see that the hypergraph is intersecting?) I guess I care most about the case that m=k-1. So I wonder if we can construct a similar example of a family of k-sets (perhaps even a balanced family) so that every star of a vertex contains a sunflower with head k-1, but the family itself does not contain a sunflower with smaller head than k-1.
A quick way to see is that two disjoint triples would sum up to 3, so both cannot be even.
Even m=k-1 is false for r>2, even for balanced families, so we can construct a balanced family of k-sets so that every star of a vertex contains a sunflower with head k-1, but the family itself does not contain a sunflower with smaller head than k-1. Below I sketch this for r=3. Start with a digraph on k vertices where the outdegree of each vertex is 2, and the girth of the underlying multigraph is more than 3. The base set of our hypergraph is
and the support of each hyperedge has size at most 2. The hypergraph has
and every k-tuple with one non-zero element. The k-tuples with two non-zeros which are in the hypergraph are as follows. The k-tuple whose i-th element is 1 (resp. 2) and j-th element is 1 or 2 is in the hypergraph if there is a directed edge from the i-th vertex to the j-th vertex with label 1 (resp. 2). This guarantees that all stars have sunflowers with head k-1, and the large girth shows (with a simple case analysis) that there are no sunflowers with smaller heads.
Thanks Dömötör, it is useful to know it. I plan to describe further the notions of (b,c)-cycles and relevance to Erdos-Ko-Rado and sunflower statements in the 3rd thread.
It can be useful to think about the simplest cases for the conjectures. One simple case is the assertion that a balanced family of k-subsets from {1,2,…,k} so that every two sets have at least m elements in common contains at most
elements. The other case is to consider balanced families with no sunflower of size three with head of 0 or 1 elements.
The very very simplest case is the following: If
is a balanced family of
-subsets from [n] =
, and every pair of sets have at least two elements in common then
.
Maybe it is known and maybe some example a la Erdos-Ko-Rado (for the non balanced case) shows it false.
If it is correct it may have some simple combinatorial proof. There may be a proof using a combinatorial version of shifting for balanced families. And there may be a homological proof. We know that
and for every link of a vertex
we have
as well. We need some condition on the
-homology of the entire
.
The very very very simplest case is for
.
In the very very very simplest case above, you don’t need the condition that F is balanced. It would be interesting to see at which k the need for this condition kicks in. (I try to write out the k = 4 case, but my 4 year old keeps drawing faces at my piece of paper. I will come back to it (hopefully))
Ok, this is not entirely waterproofed but I feel that the very very simple conjecture above is true in the unbalanced case with possibly some exceptions at small n (small definable in terms of k.) It seems sensible to distinguish between the case where every two sets A, B from the family have the SAME pair of elements in common (i. e. F is a sun flower and attains the bound from the very very simple conjecture) or the case where there are family A, B, C that do not form a sunflower with head of size 2, in spite of every two of them having at least two elements of
in common.
If I’m not mistaken, in the latter case we have that when
the number of members in the family is at most
which, being a polynomial in $n$ of degree $k-3$, will for large enough n be less than the bound from the conjecture, which is a polynomial in n of degree
.
(For
we can have more than
members but I didn’t check if and when it beats
)
Dear Vincent, when
is large then many of the Erdos-Ko-Rado questions become easier as observed already by Erdos-Ko-Rado. So the answers for P(k,2,m) and P(k,r,1) are obtained when n is large for families containing
and one element from
respectively.
‘Family A, B, C’ should read ‘family members A, B, C’. Also, how do I make my Latex look Latexy?
After each opening dollar you write “latex” with no space. It’s hard to demonstrate without making it look latexy and thus hiding the demonstration, but if I use a pound sign to stand for the dollar sign, then to make n choose 2 you would for example write £latex \binom n2£.
This isn’t to do with the homological approach (which I plan to try to understand, but I have not got there yet). Instead it is a partial answer to a question I asked on the first post. The question was this: if you have a collection of
-sets, how many do you need in order to guarantee that either three of them are disjoint or
of them form an intersecting family?
The simple upper bound is around
. This one proves by taking a maximal disjoint subfamily, which contains at most two sets, and using the pigeonhole principle to find at least
sets that all contain the same element from the union of this subfamily. A simple lower bound is obtained by picking two disjoint intersecting families of size
. Then by the pigeonhole principle you don’t have three disjoint sets and you don’t have an intersecting family of size
. This family has size
.
The question I asked was whether there is a lower bound that tends to infinity with
for fixed
. The answer is yes: here’s a simple construction that gives a lower bound of around
.
Start by picking a graph with
vertices that has no independent set of size 3 and no clique of size
. This is known to exist from the best known bounds for
— in fact, we can improve it by a log factor. For each vertex
in this graph, let
be the set of edges incident to
. Finally, add separate points to each
to create sets
that have size
. (The
typically have size about
, so we don’t have to add too many points.)
Note that
is an edge of the graph if and only if
, and the points we have added do not affect whether the sets intersect, so the Ramsey property of the graph implies that no three of the sets
are pairwise disjoint and no
of them form an intersecting family. Also, there are
sets in the set system.
Now duplicate each set
times. Then no
of the sets form an intersecting family, no three are disjoint, and there are about
sets in the set system.
There was a (not very strong) hope that it might be possible to obtain an improved bound by showing that every
-intersecting family either contains a sunflower or a large
-intersecting family. The above construction shows that to pass to the
-intersecting family we would need to divide by at least
or something like that, and the product of those is
, which is not an interesting improvement on
.
I think that
or even
would be a spectacular progress. The best we have is
where
tends to infinity. And this is very ingenious.
Of course comments continuing the older thread are most welcome. The homological suggestions are sort of a last resort. There were some interesting further comments on the group question, in fact I will make one additional comment there but then we can safely move the discussion to here.
Ah — when I wrote that I stupidly didn’t check what the best known bound was.
In that case it seems worth thinking about whether the bound of
can be improved further, or matched by an upper bound. In the latter case, one wouldn’t immediately get an improvement to
because getting a pairwise intersecting family is not the same as getting a family of sets with a non-empty intersection, so it is far from obvious what the inductive step would be in general.
For that reason it might be interesting to consider the following question: how large an intersecting family of
-sets do you need in order to guarantee either three sets that form a sunflower with a head of size 1 or a subfamily of
sets with all pairwise intersections of size at least 2?
If
tends to infinity while
is fixed, then
would tend to zero, and you can’t duplicate a set less than once. Unless I misunderstood something in the construction.
The construction is meant to be for fixed
and
tending to infinity. The idea is that one wants to pass from a large set system that contains no three disjoint sets to a slightly smaller one that is intersecting. The construction shows that the intersecting subfamily may have to be smaller by a factor of
. The sizes of the set systems are much bigger than
.
Are there any best results for small
listed anywhere?
, is there better known?
I found
The first ten sets are
123 134 145 156 162
523 634 245 356 462
The other ten sets are the same combinations but with six different numbers
This is sharp, see more on http://mathoverflow.net/questions/163689/what-is-the-best-lower-bound-for-3-sunflowers.
Dear Gil,
I’m sorry but I’m rather confused about the definition of acyclic families. After some staring I understand the situation when working over Z/2Z. We then can naturally identify each family of k-sets with the k-chain that is the formal sum over its members and it is clear that this chain is a cycle iff it satifies the condition you describe. Also in that case I can make sense of the statement that a family is acyclic if it does not ‘contain’ a cycle, because I interpret it as the family not having a subfamily that is a cycle in the above sense. However there are a lot of things that I don’t see, notably:
1. What does it mean for a family to contain, or to be, a cycle (or even a chain, really) over the real numbers? Does it mean that no non-zero real linear combination of its members is a cylce?
not depend on the field A you work over?
2. Why do results like the bound
3. With the above notion of acylic (over Z/2Z) it is clear that if a family is acyclic, the associated chain complex K as in your post has Z_k(K) = 0 and hence H_k(K) = 0, but how do we know that it is the *only* way to get H_k(K) = 0?
I know this must all be standard material but I would be very happy if you could say something about it (or post a link to some introductory text).
Thanks in advance,
Vincent
Hi Vincent. Good questions. For every field of coefficients we sat that a family
of sets of size k is acyclic if it does not support a non-zero cycle w.r.t. the field.
, where
is the simplicial complex spanned by
. Yes, for the top dimension the only way to have vanishing homology is that the space of cycle vanishes.
This means that
The argument for question 2 goes like this and it is independent of the field of coefficients. Consider the family of all
-subsets from
and the
matrix that represent the boundary operator from
. Remember that (over every field) the boundary of a k-dimensional simplex is a (k-1)-cycle. This means that a column that correspond to a k-sets
not containing ‘1’ linearly depends on the k columns obtained by adding ‘1’ and deleting an element from S. This show that the rank of the matrix is at most
. However if you consider the rows corresponding to sets not containing ‘1’ and the columns corresponding to sets containing 1 you see a permutation submatrix of size
. This gives the result.
Thank you, this is most helpful!
I can also explain with a similar argument why a family
of
-sets which does not contain a chain that vanishes for each one of
(generic) boundary operators must satisfies
. This time you consider a
matrix which for every
sets describes the
different boundary operators. Now if you take a simplex of dimension
and apply successively the
boundary operators, then you get a
-dimensional chain which vanishes when you apply each one of the
boundary operators once more. This implies that in this matrix the columns which correspond to sets
not containing any elements from {1,2,…,r} depends on those that contains one or more element from {1,2,…,r}. This gives the inequality.
So in some sense an early case of the conjecture (for the balanced case) is this: you have a balanced collection of k sets without a sunflower of size 3 and head of size 0 or 1. You want to show that if you take four generic boundary operators, there will not be a chain that will vanish for every two of them. Perhaps the simplest way to go about it is to consider such a (4,2) cycle. and try to find in it a sunflower of the requested kind.
For the second approach we want to argue directly that a general family of k-sets without a sunflower of size 3 with head of size 0 or 1 cannot vanish for applying all pairs of boundary operators among 2k+2 generic boundary operators. Again the simplest way would be to look at such a (2k+2,2)-cycle and identify in it the required sunflower.
This is a non-comment, but I wanted to say that I am still thinking about the Ramsey-type problem of how many
-sets you need before three must be disjoint or
must be intersecting, but don’t have anything interesting to say about it.
If you insist on the stronger property that the
sets must have non-empty intersection (as opposed to being pairwise intersecting) then it’s easy to get a lower bound that’s roughly the same as the obvious upper bound of
. For example, let the
-sets be the sets of edges incident at the vertices of
. No two of these sets are disjoint (since any two vertices have an edge in common), there are
of them, and the number of sets containing any given edge is
. By duplicating
times with
we obtain a family of almost
sets that all intersect but that such that no element is contained in
of the sets.
So the question that interests me (even though it may not ultimately be of any help with the sunflower question) is whether the upper bound can be improved to
when we ask only for the weaker property that the family is pairwise intersecting.
It is perhaps worth noting that an obvious family of
-sets with no three disjoint is all
-subsets of a set of size
. Unfortunately, the proportion of these sets that contain the element 1 is about 1/3, so we don’t even get a dependence on
with this example.
Somehow it seems that to get a good example the
-sets need to be spread out in a set of size close to
. But this means that random sets have quite a high chance of being disjoint, so to avoid three disjoint sets you have to do a bit of work to force them to intersect. But then to increase the size of the set system it seems hard to do anything radically different from the duplication I have been using. So it looks as though the extremal examples for the Ramseyish problem will have huge sunflowers. However, I don’t have any serious ideas for converting this intuition into a rigorous argument.
A comment regarding the
case of the hyperoptimistic (former) conjecture — i.e. the maximum size of a balanced collection of 3-sets without an r-sunflower. Hao gave an example
(which together form a 3-colored bipartite multigraph*) between
and
. For instance
https://gilkalai.wordpress.com/2015/11/03/polymath10-the-erdos-rado-delta-system-conjecture/#comment-22294
of a balanced family of 9 3-sets without a 3-sunflower, which disproved the hyperoptimistic conjecture. In trying to understand his example I found it useful to think of the link graphs of the vertices 0, 1, and 2 from
000, 010, 100, corresponds to edges 00, 01, 10 having color 0
011, 001, 101, corresponds to edges 01, 00, 10 having color 1
112, 122, 212, corresponds to edges 11, 12, 21 having color 2
In this 3-colored bipartite multigraph, we are trying to avoid (as subgraphs)
, and
, and
i) monochromatic/rainbow*
ii) monochromatic/rainbow*
iii) an edge of multiplicity 3
as these correspond to different types of 3-sunflowers in the original set system.
* By
-colored multigraph I mean an edge colored multigraph having the property that the edges between a pair of vertices have distinct colors; this implies that the multiplicity of any edge is at most
.
, I mean one vertex of degree
which is adjacent to r vertices of degree 1.
, I mean a collection of
vertex disjoint edges (i.e. a matching of size
).
By
By
A graph is rainbow if all of its edges are different colors.
Using this formulation, it becomes easier to see that Hao’s example is maximal (as Sw asked https://gilkalai.wordpress.com/2015/11/03/polymath10-the-erdos-rado-delta-system-conjecture/#comment-22304). Although I have no elegant proof (it would be nice to have one), it seems possible to show (I started to), using some case analysis, that the maximum number of edges in a
-colored bipartite graph which avoids
, and
, and
i) monochromatic/rainbow
ii) monochromatic/rainbow
iii) an edge of multiplicity 3
is at most 9.
Note that there are no restrictions on
(which corresponds to the number of vertices in the “third” part whose link graphs we are considering; although
is probably a good test case), or on the number of vertices in the bipartite graph (which corresponds to the number of vertices in the other two parts). The same will be true in what follows.
My QUESTION as it relates to the
case of the balanced version of the problem:
-colored bipartite multigraph have which avoids
, and
, and
?
How many edges can a
i) monochromatic/rainbow
ii) monochromatic/rainbow
iii) an edge of multiplicity
If we could determine the maximum such value (over all
), then we would have an answer for the case of balanced collections of 3-sets containing no
-sunflower.
I got a bit lost above on how the elements of V1, V2, and V3 relate to you your bipartite multigraph.
For 000 are you imaging that the first 0 is a vertex representing an element from v1, the second 0 is a vertex representing an element from v2, and the third 0 (edge color) represents an element from v3?
That’s correct. The link graph of the third 0 is 00, 01, 10; the link graph of the third 1 is 01, 00, 10; and the link graph of the third 2 is 11, 12, 21. Since we are looking at all of these link graphs together, we give the link edges colors corresponding to which vertex they came from.
I am looking at cases where there are limits
for the number of petals in flowers with a head of size
starting with small number cases. This is very simplistic compared to other approaches discussed but perhaps I am not the only one who finds it too daunting to jump in at the deep end.
The simplest case is k-sets with
for
. This means no two sets can have an intersection. not even an empty one, so there can only be
set and
elements. This corresponds to
.
Second case is
. So up to two sets with an empty intersection are allowed and the maximal solution is 
The third case is a little more interesting.
. Every pair of sets must have a non-empty intersection because r_0=2. The intersections can’t be no larger than 1 because
No three sets can have a non-empty intersection because the intersection would have to be of size 1 but
. Each elements that appears in any set will therefore appear in exactly two sets. Take the first set in a collection of
k-sets. This set must have an intersection of size 1 with each of the other
, sets and these intersections must all be distinct. Since the set has
elements we conclude
. Furthermore this limit can be achieved by distributing
elements so that they each appear in a different pair of sets. The maximal solution is therefore
.
What about the k-set with
?
and all such intersections must be distinct. The first k-set has
subsets of size
so there is an upper bound on the size of the k-set of 
The intersection between any two of the sets must be of size
When can this limit be achieved? It can when
or
or
. In the case
the limit can be achieved when there is a biplane of order
( a biplane is a symmetric 3-design see https://en.wikipedia.org/wiki/Block_design ) Biplanes are known of order 0,1,2,3,4,7,9 and 11.
Apologies for the Latex errors. The above bound should be
Dear Philip, corrected now…(I did not guess correctly)
thanks
In the case above, one type of sunflower is allowed with a head that must be of a given size
and with two petals. The next step up is to allow two types of sunflower with heads of size
and
where
. In other words
and
for all other sizes of head.
It is more difficult to set a good limit for these cases except the not-intersecting case when
. I.e. the collection of k-sets is allowed to contain mutual pairs with no common elements. All other pairs of k-sets must have intersections of size
and no triples of sets can have a non-empty intersection.
We already know there is an upper limit to the number of k-sets in such a collection for given k, because it would be a special case of a delta-system with
. So let's assume that
is a collection of such k-sets of the maximum possible size 
Since
is maximal, there must be two sets
and
in
which do not intersect, because otherwise we could add a new set to
all of whose elements are different from those already used and that would give a bigger collection of k-sets with the required properties.
There can't be a third k-set which does not intersect with
or
since that would give a sunflower with an empty head and three petals. Furthermore any non-empty intersection between two sets is of size
. Therefore the collection
can be subdivided into four collections
, such that
all have
elements in common with
but none in common with
,
all have
elements in common with
but none in common with 
all have
elements in common with
and
elements in common with 
the k-sets in
the k-sets in
the k-sets in
All of these intersections must be distinct and there are
subsets of size
in each k-set, so


or
or when
and there is a biplane of order 
This limit can be achieved when
Instead of keeping the same chain groups and playing with boundary maps, I wonder whether it might make sense to associate objects other than simplices intersecting along m-faces with sets with m elements in common- to play with the chain groups.
Consider two sets with 3 elements. If they don’t intersect then H_0 will tell us that. Whether they intersect at 3 elements of at 2 or 1 elements will be distinguished by H_1 not of triangles, but of their 1-skeletons (so suppress 2-cycles). To distinguish between 1 and 2-element intersections, count elements in the union (that distinguishes all possibilities in this simple example but of course not in general).
Dear Daniel, it will certainly be very interesting to relate intersection properties to ordinary chain groups and consider more general objects, like skeleta as you suggested or even the full filtration of the simplicial complex by skeleta, or perhaps other objects.
Yes- my intuition is that this might be a good direction. I’m wondering what the logical first step of this direction might be…
Let me make a few comments on the homological approach.
Given b generic boundary operators, let us define a (b,c)-cycle as a (k-1)-chain that vanishes after every successive application of c boundary operators from the b. Both our approaches are based on a conjecture that certain (b,c) cycles must contain certain sunflowers. The first approach is for the balanced case and the second for the general case.
We also want to be on the look for a more general “combinatorial” notion of (b,c)-cycle which might already contain the required sunflower.
The very special case of a=1 and b=1. The claim is that for the balanced case a cycle (which is just a (1,1)-cycle) must contain two disjoint sets. All we need to get an induction to work is that
a) links of vertices in a (1,1)-cycle is a (1,1)-cycle
b) every set of size (k-1) which is included in one set of size k in the cycle is included in at least two.
This is true (over every field of coefficients) for a cycle. We can adopt b) as the notion of “combinatorial (1,1) cycle” and b) is enough for the inductive argument to go through.
To contain a “combinatorial (1,1)-cycle” just means that the comפlex does not collapse to its codimension-one skeleton.
Now everything I said extends to (a,1) cycles and I think also (a,a) cycles. But let me elaborate on it separately as this comment gets long.
The next case to consider is (b,1) cycles. A (b,1) cycle is a collection of sets so that some linear combination of them with non-zero coefficients is a chain which vanishes for applying each boundary operator among b generic ones. A (b,1) cycle satisfies
1) The link of a vertex of a (b,1) cycle is a (b,1)-cycle
2) every set of size k-1 is included in at least b+1 sets of size k.
In the balanced case a simple inductive argument shows that 1) and 2) imply that we must have b+1 pairwise disjoint sets. Again the weaker combinatorial property 2) suffices for that.
Here is the argument: By induction the link of a vertex contains b+1 pairwise disjoint sets. So we have something like this. (For b=2)
. B is included in an additional triangle
.
is colored red hence not in
. C is included in three triangles and one of them must have a red vertex different than both v and w.
Th elink of v contains three disjoint sets A,B and C . We can have three disjont triangles as follows.
Our more general aim is to show that in the balanced case (mb,m)-cycle must contain a sunflower of size b+1 with head of size at most m-1. Here are some thoughts, hopes, and concerns about it. Lets just worry about sunflowers of size 3.
A) A possible direction: The results about (2,1) cycles gives some information about links. With some extra results on vanishing of lower dimensional “homology” some techniques used for Theorem 2 may apply.
B) Hope: Using combinatorial notions of (b,c) cycles may simplify matters.
C) Concern: Maybe inductive arguments like the one describe here can be used to reduce the conjectures for “no sunflowers with small heads” to the original conjecture of “no sunflower”. Again a good place to check is for “no sunflowers of size 3 with head of size 0 or 1.”
D) (hopeful) The inductive argument actually allow to get a sunflower from weaker structure. We will return to it later. (Added later: Actually I don’t see it allows such a thing.)
The next case to consider is the case of (b,b)-cycles. Here the statement is this: if F is a balanced family of k-sets which form a (b,b)-cycle then there are two sets in the family whose intersection has size smaller than b. Again it looks to me that the inductive arguments work (and used basic properties of (b,b)-cycles which applies in greater generality).
Another challenge would be to prove the same conclusion (which we know is correct) using arguments of Theorems 1 and 2. Or to start consider the case b=2 and trying to guess/verify the additional homological property in addition to the property that the family and links of vertices have vanishing top dimensional homology.
Some of the insights regarding sunflowers may extend to many-families questions and such extensions may be useful for some inductive arguments. So for example we can ask, given k for which 3 numbers a,b,c whenever we have three families A, B, C of k-sets of cardinality a,b,c respectively, we can find a sunflower with one set from A one from B and one from C. of course we can also consider families of sets of different sizes.
I might misunderstand something, but if all sets of A and B contain some element x that is not in any set from C, then we will never have a colorful sunflower.
That’s right, we do need to make some extra assumptions. I specifically wondered about the following: If A B are cycles and balanced (all are families of k-sets). Do we necessarily have a pair of disjoint sets one from A and one from B? If A B and C are cycles for two boundary operators and balanced (all are families of k-sets). Do we necessarily have a colorful triple of pairwise disjoint sets?
Actually, I think that or basic argument for cycles indeed shows that.
I feel very ashamed, but the homological notions (like cycle) are still quite alien to me. But if you sketch a proof, I might be able to follow it, or maybe even understand cycles better!
Dear Dömötör, what about the following: we assume further that A B and C have a k-set in common. can we find a colorful sunflower then? Actually I care about k=2.
I think the same counterexample works with the addition of one element. Again, all sets of A and B contain some x, except for one set from each, which is the common set of A, B and C. If all sets from C avoid x and intersect this common set, we won’t have a rainbow triple.
Let me draw attention to GFP’s comment from the first thread. Fix k and n (and r that we can set to r=3). Consider the following sunflower process: we choose k sets from [n] at random until any new k-sets leads to a sunflower. The question is what is the expected size of the resulting sunflower-free family. It will be interesting to answer this question!
(We can also start from all the sets and remove sunflowers at random.)
I’ve just replied to that comment without noticing that it was on the first post. Let me briefly repeat here one thing that I said there, which is that I think it would be interesting to have a look at this question experimentally for some small values of
and
. How do the set systems produced compare with the best known examples? If I get time, and if nobody else has already done it, I’ll write a program to look into this.
I have some code that can do this already. I will post some results when I have them.
I’ll look forward to it!
I used
and gave up searching after 10 million attempts to find the next set. These were averaged over 100 trials
k=2: 4.52
k=3: 10.13
k=4: 24.11
k=5: 58.53
The last one may go a bit higher if I increase the number of attempts. For k=6 I would need a lot more attempts so it would take a long time. Some improvements in strategy may help. e.g. selecting elements randomly from all previous ones and k new ones could be faster.
Let me know if more info would be useful and I will run again.
Probably it will be useful to let both n run from k (or say 2k) and look at all pairs (k,n) trying to see a pattern to the behavior.
I’d be interested to know not just what the averages were but what the best examples were. It’s nice that these examples beat
, though I don’t know what the state of the art is.
I meant to say also that I agree with Gil that trying some smaller ground sets would be interesting.
Finally, I would like if possible to stare at some of the maximal examples — maybe there could be a page on the wiki for them. I’d like to know for example how spread out the sets are, whether the intersections tend to have roughly the same size, etc. etc.
Give me a little time and I will follow up these suggestions.
The maximum sizes I am seeing from this process are only a small percentage better than the averages and are a long way short of the best constructions known. For example you can get 20 k-sets for k=3 and 54 for k=4. There must be other random methods that would find better examples if that is one goal.
Here is a collection of 34 sets for k=4. I don’t see many bigger than this.
{ 9 1 13 0 } { 9 1 6 10} { 11 5 14 0 }
{ 3 1 0 11 } { 10 1 5 13 } { 3 1 11 12 }
{ 11 9 14 1 } { 10 2 13 9 } { 3 14 9 12 }
{ 9 13 2 0 } { 3 6 7 14 } { 3 4 14 12 }
{ 3 11 5 7 } { 4 9 10 0 } { 8 9 10 0 }
{ 2 3 7 14 } { 11 14 0 15 } { 10 1 9 13 }
{ 3 8 11 7 } { 9 13 2 10 } { 7 9 6 10 }
{ 9 1 13 12 } { 6 10 2 13 } { 3 8 11 5 }
{ 4 11 9 14 } { 7 9 1 10 } { 2 3 6 14 }
{ 11 5 14 15 } { 9 13 0 12 } { 6 10 13 9 }
{ 10 5 9 13 } { 3 4 14 9 } { 4 11 14 1 }
{ 4 8 9 10 }
All 16 numbers are in use so perhaps n needs to go higher
I may have a bug, let me check that before you do anything with these results
@Phillip Gibbs
I used my generic program for finding large examples in generic extremal problems. Some of my maximums are better than yours, some are not. It’s all very close. I will just upload my summary (I calculated a bunch of small values for
with
), but maybe it would make sense to unify the results somehow?
My program is still running and I still have to write a script to extract the results nicely. I only gave it 5 minutes for each set of parameters. For
my generic program needed ca. 10 hours for a complete search, so results will be far from optimal.
There was a bug that affected some of the earlier numbers a little but these ones pass sanity checks. Feel free to delete the others results to avoid confusion. I have done k=2 and k=3 with varying n. The best possible for k=3 is 20 but that never came up.
(k,n) mean max
(2,2) 1.00 1
(2,3) 3.00 3
(2,4) 3.75 4
(2,5) 4.64 5
(2,6) 5.23 6
(2,8) 5.38 6
(2,10) 5.48 6
(2,20) 5.75 6
(2,40) 5.90 6
(3,3) 1.00 1
(3,4) 4.00 4
(3,5) 5.82 6
(3,6) 8.06 10
(3,7) 10.15 12
(3,8) 10.92 12
(3,9) 11.57 14
(3,10) 11.49 14
(3,11) 11.45 14
(3,12) 11.67 17
(3,15) 11.88 17
(3,20) 11.92 16
(3,40) 12.26 16
(k,n) mean max
(4,4) 1.00 1
(4,5) 5.00 5
(4,6) 8.16 9
(4,7) 12.91 15
(4,8) 16.93 20
(4,9) 20.21 25
(4,10) 22.18 25
(4,11) 23.4 26
(4,12) 24.03 28
(4,13) 24.11 30
(4,14) 24.42 28
(4,15) 24.43 29
(4,16) 24.70 30
(4,20) 25.53 32
(4,30) 28.60 36
(4,40) 30.75 38
(4,60) 32.78 38
(4,100) 34.09 39
Many thanks, Philip. The outcomes seems monotone with n which surprised me. Is there a reason to think that this is always the case? And is there some guess we can make on what happens when n tends to infinity?
The maximum will be monotone but I don’t always find the maximum in these runs. The mean is less obvious. In the n tends to infinity limit it will select a k-set at each step so as to maximise the number of elements that have not been used before in previous k-sets.
I don’t know what is the most useful next step I can do but I am thinking about compiling a database of best solutions as a function of (k,n) and I will try to present them in an ordered way that allows us to see any symmetry
I have posted all the best examples of k-sets I could find at http://pastebin.com/XNkZwxzV
One other thing I wanted to say was that I had an idea for a generalization of the problem, but then realized that it was uninteresting. Nevertheless, perhaps it is worth mentioning, just in case someone can think of a way of making it interesting after all.
The generalization was to consider an analogous question for
-dimensional subspaces of a vector space, where a sunflower is defined exactly as before, though it is probably nicer to describe it in terms of dimensions of subspaces. This is a generalization because for the
-sets question we can think of the elements of the ground set as a linearly independent set of vectors and take the subspaces generated by the
-sets.
The reason the problem is uninteresting is that if you take two-dimensional subspaces of
in general position, then any two of them intersect in a one-dimensional subspace, but any three of them intersect in a zero-dimensional subspace. So it is easy to produce continuum-many sunflower-free systems of subspaces.
It’s tempting to use this fact about subspaces to build large sunflower-free sets, but the obvious things I’ve tried produce only very small ones. For example, in the vector space
we could take
-dimensional subspaces, but they have size
and there are at most
of them, so we get at best a bound like
with this construction, and my guess is that pretty well all similar constructions suffer from the same kind of problem.
This is an interesting direction. It is an interesting question what is the upper bound if we are asking about vector spaces over finite fields like
and consider them as sets systems.(So an r-dimensional space is regarded as a
-set. It is interesting what is the largest size of sunflower of this kind. Can we get above
?)
There is another way to go even over
which is to consider families of subspaces which, regarded as vectors in the corresponding exterior product, are linearly independent. (This follows also from a certain combinatorial property for pairs of spaces.) there the question is a genuine stengthening of the original question. For Erdos-Ko-Rado theory this more general setting reduces to the regular one since shifting is still available. But this does not apply to sunflower questions.
Since I read up on this PolyMath problem two days ago, I spend some time looking for a finite vector space version of the problem. (As a trained finite geometer that is the natural thing to do for me I suppose.) Finally, I found your comment, so maybe here my comment fits. I did not think about the same problem. I just thought a little bit about the following, where I replaced “of size x” with “of dimension x”:
A sunflower of size
is a family of subspaces
over a finite field with
elements such that every subspace that belongs to more than one of these subspaces belongs to all of them.
As in the set case you will have a function
such that every family of
-spaces with more than
elements contains a sunflower of size
. The proof for this is just the same.
Is there any good reason to look at this? Maybe not. At least
reminds one of the dual of a (partial) hyperoval (a family Y of 2-spaces in a 3-space such that no 1-space lies in more than two elements of Y). Then some things get much easier for large
(with the set case seen as
). Sometimes you can do a tradeoff between
and
(I know an example where you can replace
and
with
and
). Of course this will never help with the set case, but maybe it gives one new ideas or more confidence that the original Erdos-Rado conjecture is true.
As I have no useful ideas, I did not want to comment, but this looks like a good place to mention this canonical vector space analog.
Dear Ferdinand, I agree that the q-analog and other vector space analogs are potentially interesting. This applies also to Erdos-Ko-Rado theory of course.
Thanks. I don’t know why you mention EKR theorems, but there the q-analog of the standard EKR theorem is known for a long time (most of it due to Hsieh, 197?). In some sense the q-analog is easier. There’s a two line EKR proof for n >= k^3. The same two line q-analog argument shows the q-analog of the EKR theorem for n >= 3k (and n >= 2k+1 with some fine tuning).
I have implemented a small variation of the process, where I also require that the family is intersecting. One could obtain a usual sunflower-free family by ‘duplicating the family’. For each pair the process was run 100 times. Below is a list of the values I obtained (so again, we get twice as much for the usual sunflower-free problem)
For the pair (k,n)= (3, 4)
Average length is : 4.0
Max found is: 4
For the pair (k,n)= (3, 7)
Average length is : 8.61
Max found is: 10
For the pair (k,n)= (3, 10)
Average length is : 7.24
Max found is: 10
For the pair (k,n)= (3, 13)
Average length is : 6.97
Max found is: 10
For the pair (k,n)= (4, 5)
Average length is : 5.0
Max found is: 5
For the pair (k,n)= (4, 9)
Average length is : 18.06
Max found is: 21
For the pair (k,n)= (4, 13)
Average length is : 17.56
Max found is: 22
For the pair (k,n)= (4, 17)
Average length is : 17.67
Max found is: 24
For the pair (k,n)= (4, 21)
Average length is : 17.45
Max found is: 21
For the pair (k,n)= (5, 6)
Average length is : 6.0
Max found is: 6
For the pair (k,n)= (5, 11)
Average length is : 38.46
Max found is: 42
For the pair (k,n)= (5, 16)
Average length is : 37.43
Max found is: 46
For the pair (k,n)= (5, 21)
Average length is : 38.43
Max found is: 58
For the pair (k,n)= (5, 26)
Average length is : 38.86
Max found is: 49
For the pair (k,n)= (5, 31)
Average length is : 40.23
Max found is: 52
It seems to easily beat the 2^{k} construction, and even the 10^{n/2 -clog(n)} construction (for the small values of k I could manage at any rate), which I believe is the state of the art.
One particular context I was also thinking about was the “n=\infty case”. The advantage of this setting is that the randomness is much easier to control; for instance we know that the process would be initially driven by intersections of size 1, then when we run out of those by intersections of size 2 and so on…
If you can beat it for small values, you can also beat it for big ones, as
. So your example gives
and
, I think we need a little better to beat it with this simple product recursion, though other tricks might help further.
Yes, the aforementioned best known lower bound is obtained by making the observation that $g(mn)\geq g(m)g(n)^{m}$ and that $g(3)=10$ (where g is the extremal function for intersecting 3-sunflower free families). If we could find a $k$ for which $g(k)^{1/(k-1)}>10^{1/2}$ then using the same argument we’d obtain an improved lower bound.
Do you know what happens if you insist that the
-sets are
-coloured? Is it still possible to beat the
bound by quite a lot in this way?
Using random trials on the balanced case I found




The homological balance conjecture would give
which is not in contradiction with these results.
With some more trials I have
and 
For
there is a balanced intersecting collection of 13 k-sets so
. Here is what the 13 k-sets it looks. Elements in different columns are coloured so that they are distinct
{ 0 0 0 0 }
{ 0 3 3 1 }
{ 0 3 3 2 }
{ 1 3 3 0 }
{ 2 3 3 0 }
{ 3 0 3 1 }
{ 3 0 3 2 }
{ 3 1 3 0 }
{ 3 2 3 0 }
{ 3 3 0 1 }
{ 3 3 0 2 }
{ 3 3 1 0 }
{ 3 3 2 0 }
The structure seen in the example of 13 balanced intersecting sets can be reused to show that
. Ignoring the extra row of zeros we can take the solution of size
and make three copies with two extra columns of identical numbers in each staggered over three columns as in the example. This gives an intersecting solution so it can be doubled up to give the overall factor of six with two extra columns.
For k=6 this construction gives a set of size 6×26=156 but using further random trials I now have
The generalisation of this construction gives
provided that
where
is the number of elements appearing in the union of the collection that gives the limit
. The extra condition is slightly better when we use connected sets. In particular
for
which gives
. This is for r=3.
This may be enough to show that the growth rate and the conjecture for balanced sets is the same as for general sets.
Why not
?
domotrop, because
the
elements from the unbalanced collection can each be given a different colour in the new balanced collection with sets of size
. These are then combined with the second set which is balanced so as to fill in the rest of the colours. That’s not very clear. I will try and find a way to write it out in more detail.
You can see how it works in the example of 13 k-sets with k=4 that I posted. This combines the unbalanced intersecting collection {2,3} {1,3} {1,2} with the balanced non-intersecting collection {0,1} (0,2} {1,0} (2,0} to give a balanced intersecting collection of 12 k-sets. In this case a 13th k-set can be added so the construction is not always optimal.
I see, nice construction. But I don’t think that this is enough to show that the growth rates are the same because of the condition
.
Suppose
and
then
implies 
For any
there is a maximal unbalanced collection of
sets which has some number
of elements in its union. Using the construction
times with this unbalanced collection and the maximal balanced collection for
to begin with we get,
which implies

Taking the limit
with
and
fixed

we can now take the
limit to get
therefore 
Since this is true for all
The good news is we only need to consider balanced sets. The bad news is that balanced sets are no simpler than unbalanced sets.
Right, thx!
Maybe we can run the computations on balanced (k-colored) families as well. I met Avi today and he asked an very natural question: Can we reduce the delta-system conjecture to a specific case for k and n, say
. Avi also mentioned some applications of delta systems in TCS which I was not aware of and some other cool developments.
What is the status of the statement
? It would be quite surprising. Can we improve
?
Let
be a
delta set of size
with
elements in its union. Let
be a balanced
delta set of size
, Then if
we can construct a balanced
delta set of size
as follows.
Since
we can assign a unique colour from a palate of
colours to each element in the union of
. For each set
in
take the
colours assigned to its elements and recolour all the sets in
with the remaining
colours in the palette using a one to one mapping between the colours. Now form
coloured sets from the union of the coloured version of
with each recoloured set in
(We assume that the elements in
are distinct from the elements in
). Do this for each of the sets in
to form
sets.
To illustrate this with an example consider the (2,3) delta set {1,2}, (1,3}, (2,3} and the (4,3) balanced delta set {r4, g8}, {r4, g9}, {r5,g7}, {r6,g7} assign the 3 elements 1,2,3 to the colours r,g,b from a palate of four colours r,g,b,y. The 12 sets from the construction are
{r1, g2, b4, y8} (r1, g4, b2, y8 } {r4, g1, b2, y8}
{r1, g2, b4, y9} {r1, g4, b2, y9 } {r4, g1, b2, y9 }
{r1, g2, b5, y7} (r1, g5, b2, y7 } {r5, g1, b2, y7}
(r1, g2, b6, y7} {r1, g6, b2, y7 } {r6, g1, b3, y7}
Proof that the constructed delta set has no sunflower of size
:
. Consider three cases one of which must apply:

and some other using a different set from
.
in
, case (2) would imply a sunflower in
, and in case (3) the intersections of the three described sets in pairs cannot be the same. This completes the proof.
Suppose we can find a sunflower of size
(1) All the sets in the sunflower are constructed using distinct sets from
(2) All the sets in the sunflower are constructed using the same set from
(3) The sets in the sunflower contain some pair using the same set from
All three cases can be ruled out. Case (1) would imply a sunflower of size
From this construction we can conclude that

where
is the (smallest) total number of elements in a maximal
delta set
provided
Suppose that
and
where
and
may depend on
. (The following argument also works if these can be infinity)
For any
let
be the number of elements in a maximal
delta set. Then using the inequality
times we get


with all else fixed.

we can take the
limit so
. Since
we also know that
therefore 
Taking the limit
Since this is true for all
Beautiful! and looks perfectly ok. (But other participants, please do check it too, maybe I missed something). Now if we could only always enlarge a balanced system for (k,r) to a general system of size larger by a factor
we would have a counter example to the conjecture. (We have
times available sets.) Unfortunately, it looks that we cannot enlarge at all the basic
example.
Given this equality, the homological balanced conjecture will give a bound of
, and the homological unbalanced conjecture would yield a weaker result.
The example can be extended with {r4, g4, b4, y7} and still be intersecting, and the construction has some flexibility in the recolouring. It is also possible to renumber the sets from
differently for each set from
. So there is hope that enlargement could work.
As Philip said, there may other ways to alternate between balanced and non balanced example so that we may gain something, maybe even break the exponential barrier. This certainly deserve thinking.
Another idea we can explore which may be relevant to both positive and negative direction is a more drastic reduction of the kind we did when we originally moved from general families to balanced families. (This was suggested both by Tim and by me and perhaps others.)
Suppose we start want to color with 5k colors rather than k colors with the following additional conditions
(1) every set is colored by k consequtive colors modulo 5k.
(2) Two sets that share k-1 elements must involve at least k+1 colors.
Perhaps by taking random coloring and excluding violators of (1) and (2) we can start from an arbitrary family and end with an exponentially smaller (but only exponential smaller) subfamily satisfying these conditions.
If there are k-1 fixed elements that are contained in every set, then I don’t think you can have both (1) and (2) for more than two sets.
About breaking the exponential barrier, here is a paper that shows how to “break it” for many problems (though I don’t see how it could be applied to sunflowers): http://www.sciencedirect.com/science/article/pii/S0097316597927801
But we cannot have
fixed elements in
or more sets.
Not if you want to use that we don’t have a sunflower, but I thought that you wanted to make a general construction, like we had earlier.
That’s a good point. the earlier construction and also if you only worry about (1) are general.In particular they apply for the questions about no sunflower with small heads. If you want to achieve (2) you need to exclude sunflowers. There may be various other “exponential” reductions.
I’ve also wondered if the following, Kneser-type coloring question can be useful:
How many colors to we need to color all k-tuples of an n element set avoiding monochromatic 3-sunflowers?
Let me try to work out the obvious bounds here, just to get a feel for the problem. Of course, we need at least
colours, where
is the size of the largest 3-sunflower-free family. Obviously one interesting problem is whether this second bound is likely to be a good one. That is, if we define
to be
divided by the smallest number of colours needed to avoid a monochromatic sunflower — which is the average size of each colour class — we know that
, but must it in fact be much less?
For very large
I would guess no, given that there are some powerful results around that tell us that complete hypergraphs can be almost partitioned into copies of small fixed hypergraphs — or even exactly partitioned when certain divisibility conditions are satisfied. But the range that interests us is more like
I think, and here it is not at all clear that extremal sunflower-free examples would fit together nicely.
Hello I’m a highschool student in Korea. I recently read over a book on extremal combinatorics,
,
and
.
form a sunflower iff
doesn’t appear in
,
represents a point
represents an intersection of whole 3 sets,
represents the backgrounds.
Then,
.
,
wanted to find some problems to think about, and fortunately got to this website.
I really like this environment of discussing about a problem. It’s so cool.
And I admire intelligent people here such as Tao and Gowers.
I have some approaches and (probably)related problems. It might be meaningless but
please leave some comments on it.
1. This approach is only meaningful in the case of 3 petals.
Let there’s a family
Regard the set as 0 1 vectors. A simple observation is that
three different vectors
component of
occupied by a single set,
and
And another possible representation of this is here,
Define
three different vector in the family form a sunflower iff
From this, we can generalize this problem to the case of real vectors.
(Think about a finite set of vectors in
such that each pair of vectors satisfy some distance condition. (like ||u-v||>=1 in some p-norm?)
And what number of vectors guarentee that there’re three different u,v,w such that I(u,v,w)<1?)
But this might be unsucessful since normally I(u,v,w) would be too large.
I'll continue this a few hours later
Dear daeseoklee, thanks for participating! What is the definition of
?
I meant ++-3 when is the ordinary inner product and is sum of all coordinatewise products of u,v,w.
Ah I got why this type error happened. Maybe it omits inner product notation (sharp parenthesis). I meant u•v+v•w+w•u-3u•v•w where u•v•w is sum of coordinatewise products
While I was away for a few days I thought about how to construct
delta systems. With a few observations I was able to reduce it to a problem of constructing polytopes. I don’t know if this is already understood but it is new to me so I will try to explain it. My goal is to work through the case
by hand and then try to understand the
case well enough to use a computational search. The
case reduces to looking at ordinary polytopes in three dimensions where the faces are made with triangles, squares and pentagons and all vertices are trivalent. For
you have to move up to 4-dimensional polytopes built from the 3-dimensional ones and they may be embedded in spaces of different topologies so this will be a lot more difficult. These polytopes are the duals of the simplical complex used in the homological approach so there may be some cross-over that will help.
(1)
(sorry I was using the term delta system incorrectly. I meant families of k-sets with no sunflowers of size 3)
The first goal is to construct all
families of k-sets with no sunflowers of size
. It suffices to construct all complete families, where “complete” means that no further k-sets can be added without forming a sunflower with
petals. If incomplete families are needed they can be derived from complete ones by removing some k-sets.
The first useful observation is as follows: Given is a complete
family
, select any element
that appears in at least one k-set of
and form the family
of (k-1)-sets from the subsets of
which contained
, with
.
is then a complete
family. This is because if you could add a new k-set to
without forming a sunflower then you could add the element
to that set and add the set to
without forming a sunflower.
From this observation the task of constructing complete
families reduces to first constructing complete
families, and then working out how to combine them,
Thanks, I am sure this construction must have been done before. Let me know if you are aware of a reference.
For a reference, see the top of this post…
I see the definition of link. I was wondering if anyone had gone through this whole classification based on polytopes. I may not be able to access all the literature because I don’t have journal subscriptions.
Unfortunately, I don’t believe your “first useful observation.” Take k=2 and r=4, and let F be the graph formed by three disjoint triangles. This is maximal but no
is.
Thank you for pointing this out. There are also counterexamples for the r=3, k=3 case, e.g. a solution based on two tetrahedra. However, it should not be difficult to find these possibilities as special cases.
(2)
There are three complete (2,3) families as follows
square: {1,2} {2,3} {3,4} {4,1}
pentagon: {1,2} {2,3} {3,4} {4,5} {5,1}
tow triangles: {1,2} {2,3} {1,3} {4,5} {5,6} {6,4}
The only complete (1,3) family is {1} {2} so (2,3) families must be formed by linking pairs into collections of polygonal structures. It remains to check that any bigger polygons or collections of polygons than these three would have more than two mutually distinct subsets which would therefore form a sunflower with an empty head.
(3)
.
Now we need to see how to combine these (2,3) families to build a complete (3,3) family
Any k-set with 3 elements
in
can be associated with three complete (2,3) families
and these can be any combination of the three possibilities, the square, the pentagon or the two triangles. This can be pictured by placing the k-set
on a vertex of a graph where three edges and three faces meet. The faces can be squares, pentagons or triangles and can be labelled with the symbols
,
and
accordingly (usually these elements are represented by numbers)
The process of making vertexes in this way can be repeated to form a graph for the (3,3) family.
When triples of complete (2,3) families are brought together in this way, some of the elements in the families need to match for consistency at the vertex, however there are other elements from the smaller families that could be made to match but they don’t have to. We have the choice. This has to be done in such a way that no
sunflowers are created. Potentially this generates a large number of cases to check until all consistent families are found. Luckily there is an observation that simplifies this task.
The procedure is to build the graph structure vertex by vertex and face by face choosing from squares, pentagons and triangles and always using trivalent vertices, but whenever two elements don’t have to be the same, always make them different, provisionally. Continue this until the graph forms a complete polytope. Since no polygons with more than 5 edges are used and all vertices are trivalent, we know that this process will eventually end. There are only a finite number of trivalent polytopes made with triangles, squares and pentagons (note that the polyopes don’t have to be formed with flat faces. It is only the topology that matters). Listing them all is the first step towards finding all complete (3,3) families. However, our family
can be constructed from more than one such polytope.
Each square face and each pentagon face is the polytopes will be labelled with a unique element. The triangular faces will come in pairs Labelled with the same element because they form the two-triangle (2,3) family. The two triangles in each pair can be different faces in the same polytope but they must not touch at an edge of vertex. They can also be two faces in two different polytopes in which case the labelling element would form a connection between them
The remaining question is how do you form the cases where some of the elements that could be different are chosen to be the same? The only way this can be done consistently is when the collection of polytopes has a symmetry. Faces that map to each other under some subset of the symmetry transformations can be made the same consistently, provided the transformations never maps a vertex to another vertex in the same face.
To conclude, all complete (3,3) families can be constructed by considering all collections of trivalent polytopes made with faces of up to 5 edges and considering reductions modulo some subset of their symmetries.
(4)
using this polytope construction we only accept the results if no sunflowers of size
are formed. The next useful observation is that the only such sunflowers that can form before any symmetry reduction are those made of
mutually disjoint sets. This is because if any sunflowers of size
with an element
in its head were included in
then it would also form a sunflower in
, but we have only used the three complete (2,3) families which have no sunflowers of size 3.
When forming families
To make the construction more concrete consider some special cases. If the only faces used are squares the only trivalent polytope that can be formed is a cube with the faces numbered from 1 to 6. The family this forms with one set for each of the eight vertices incorporating the elements on faces that meet at the vertex is
{1,2,3} {4,2,3} {1,5,3} {4,5,3} {1,2,6} {4,2,6} {1,5,6} {4,5,6}
This includes pairs of mutually disjoint sets but no triples, so it is a valid (3,3) family. Only one cube can be included in the family because two cubes would have four mutually disjoint sets.
For a second example consider the case where only pentagons are used as faces. The polytope formed is a dodecahedron labelled with 12 elements. There are 20 sets in the family corresponding to the vertices. In this case it is possible to find four mutually disjoint sets by choosing vertices that form a tetrahedron inside the dodecahedron. However the family can be reduced modulo a reflection which sends each vertex, face and edge to its antipodal point on the dodecahedron. This reduces the number of elements to 6 and the number of sets to 10. In the resulting family there are no mutually disjoint sets, so in this case two copies on the reduced dodecahedron can be included in a family. This gives the maximal (3,3) family of 20 sets.
What about families built from pairs of triangles? The trivalent polytopes formed from triangles are tetrahedrons, but the faces must be paired across different tetrahedrons otherwise the pairs would touch. Every tetrahedron in the family must be connected to each other one by either one or two pairs to avoid disjoint sunflowers. There are valid ways to do this using 3,4 or 5 tetrahedrons. Since there are four vertices on each tetrahedron this gives families of 12, 16 and 20 sets. (I was not aware of this second maximal solution until I constructed it in this way)
(5)
What are the possible symmetries that can be used to reduce the collections of polytopes? The polytopes themselves can have many symmetries and if the collection has more than one polytope of the same form there will be permutation symmetries of those. However, the permutation symmetries would just reduce the number of polytopes by making them equivalent.
The symmetries must not map any vertex to another vertex in the same polygon. Since rotation symmetries in 3D always have a fixed point any rotation symmetry of a polytope will be invalid. I conjecture that the only valid transformation is the reflection that maps each point to its antipodal point. This can easily be verified in individual cases.
(6)
triangles,
squares and
pentagons, then using Euler’s formula
. Fortunately wikipedia provides a shortcut to finding all cases that work with a list of the dual polytopes made from triangles at https://en.wikipedia.org/wiki/Deltahedron If I have not missed anything there are eleven cases with the following values for 
To be able to complete the classification of (3,3) families a list of all trivalent polytopes with faces having at most 5 edges is needed. If a trivalent polytope has
(0,0,12) (0,2,8) (0,3,6) (0,4,4) (0,5,2) (0,6,0) (1,3,3) (2,0,6) (2,2,2) (2,3,0) (4,0,0)
From here it is a straightforward exercise to construct all the solutions.
(7)
As Dömötör pointed out this construction does not give all complete/maximal families, and I don’t think I can fix that. However it is still a good way of constructing large families so it could help with the search for possible counterexamples.
To illustrate the point I have a new best family for r=3, k=4. It was found by combining the new family of 20 sets for r=3. k=3, but there is an easier way to describe the construction which starts with the following 11 sets
{ 0 1 2 3 4 } { 0 1 5 6 7 } { 0 2 7 8 9 }
{ 0 3 6 9 10 } { 0 4 5 8 10 } { 1 2 6 8 10 }
{ 1 3 5 8 9 } { 1 4 7 9 10 } { 2 3 5 7 10 }
{ 2 4 5 6 9 } { 3 4 6 7 8 }
These form the Paley biplane with the property that there is a one-to-one correspondence between pairs of elements and pairs of sets which contain them both. To get the r=3, k=4 family just take all subsets of size four from each set to form a family of 55 sets. According to the wiki the best known solution has 54 sets so this is a new record. It is not a huge advance but at least it shows we are in new territory.
Hold on, {0 2 3 4}, {0 1 5 6} and {0 7 8 9} form a sunflower, don’t they? But I also have high hopes that this approach will give a better construction for r=3, k=4.
Yes you are right. I will keep looking.
Dömötör wrote: “…the homological notions (like cycle) are still quite alien to me. But if you sketch a proof, I might be able to follow it, or maybe even understand cycles better!”
Let me try to explain the notions a little better, and later sketch some proofs using them.
A (k-1)-dimensional chain is a linear combination of k-sets with real coefficients. Such a chain is a (b,c)-cycle if it vanishes whenever we apply c successive boundary operations from b generic such boundary operations. A family of k-sets is a (b,c)-cycle if we can assign nonzero weights to its members as to get a (k-1)-chain which is a (b,c)-cycle. Our conjecture is that for
a balanced (non-empty) family of k-sets which is a (2m,m)-cycle must contain a sunflower of size three with head of size smaller than m. If true this will say that for r=3,
(and hence by Philip result
.)
This is fairly cryptic but I think it is useful to replace (or “approximate”) the notion of a (b,c) cycle by a stronger combinatorial notion as follows:
When c < k, a family of k-sets is a combinatorial (b,c)-cycle if every link of a vertex is a combinatorial (b,c) cycle. When c=k, a family of k-sets is a (b,c) cycle if its cardinality is larger than
.
Combinatorial (b,c)-cycles are good approximations for (b,c)-cycles (that we can call topological or algebraic (b,c)-cycles.) It is easier to understand them and sometimes to get results you need to juggle between the two notions.
Pingback: Polymath 10 Post 3: How are we doing? | Combinatorics and more
Pingback: attack on/ of the sunflowers! | Turing Machine
Pingback: Polymath10-post 4: Back to the drawing board? | Combinatorics and more
Pingback: Polymath10 conclusion | Combinatorics and more