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 
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 
A basic and simple result of Erdos and Rado asserts that
Erdos-Rado sunflower theorem: There is a function 
We denote by
The Erdos-Rado Sunflower Conjecture
The Erdos-Rado sunflower conjecture: 
Here, 
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 
Basic Question: Understand the function f(k,r,m;n). Is it true that 
A family of
B) Stars and links: Given a family 
at most less than 
C) The balanced case
A family of
Let 
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 
The definition of homology groups only depends on the combinatorial data. For simplicity we assume that all sets in 
F) Acyclic families and intersecting families
A family 
Proposition: An acyclic family of k-subsets of [n], contains at most 
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 
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 
Given a vector 
where
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 
Answer for 2: There is no chain in
When 
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 
Here is an example with more than
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
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 
[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 
This theorem extends also to every value of m.
Theorem 2: Let 
L) Collapsibility. An easier version of Theorem 2 is for the case that 
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
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 
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 
Proposition: For a balanced family of 
Corollary: If 
O) The expected global consequences for balanced families without Delta systems
Conjecture 1 (special case of r=2): If
Conjecture 1 (general case): If 
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
Theorem 4: (1) Let
(2) Let 
(3) If F is a family of
These follow directly from the fact that algebraic shifting preserves the property that
Unfortunately, as we mentioned, the property of interest to us is not preserved under shifting. We can hope that the effect of the extra
Q) The Conjecture for the alternative direction:
Conjecture 2: If 
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 
(2) Next consider the 
(3) Given a family 
(4) Now, choose a basis to the rows of
(5) The algebraic shifting 
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,
There is no chain in 
There is no chain in 
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
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![[n]](https://s0.wp.com/latex.php?latex=%5Bn%5D&bg=ffffff&fg=333333&s=0 "[n]")
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 ![[m]](https://s0.wp.com/latex.php?latex=%5Bm%5D&bg=ffffff&fg=333333&s=0 "[m]")
and one element from ![[r]](https://s0.wp.com/latex.php?latex=%5Br%5D&bg=ffffff&fg=333333&s=0 "[r]")
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 ![[n]](https://s0.wp.com/latex.php?latex=%5Bn%5D&bg=ffffff&fg=333333&s=0 "[n]")
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 ![\bigcup F_i=[n]](https://s0.wp.com/latex.php?latex=%5Cbigcup+F_i%3D%5Bn%5D&bg=ffffff&fg=333333&s=0 "\bigcup F_i=[n]")
.
form a sunflower iff
doesn’t appear in 
, 
represents a point
represents an intersection of whole 3 sets,
represents the backgrounds.
Then,
.![V=\{(a_1,a_2,\cdots,a_n)\in [0,1]^n:\sum a_i=s\}](https://s0.wp.com/latex.php?latex=V%3D%5C%7B%28a_1%2Ca_2%2C%5Ccdots%2Ca_n%29%5Cin+%5B0%2C1%5D%5En%3A%5Csum+a_i%3Ds%5C%7D&bg=ffffff&fg=333333&s=0 "V=\{(a_1,a_2,\cdots,a_n)\in [0,1]^n:\sum a_i=s\}")
,
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