Gil Kalai starts Polymath10

I’ve already mentioned this on Google Plus, but my readership there is different from my readership here, so it seems a good idea to write a similar post here, to give what publicity I can to the fact that Gil Kalai has started a new Polymath project. The problem he would like solved (and I would very much like to see it solved too) is the famous delta-systems or sunflower conjecture of Erdős and Rado.

The problem, as with many problems in combinatorics, is easy to state, but fascinatingly hard to solve. It is a classic extremal problem, in that it asks how big some combinatorial object needs to be before it is guaranteed to contain a subobject of some particular kind. In this case, the object is a $k$uniform hypergraph, which just means a collection of sets of size $k$. The subobject one would like to find is a sunflower of size $r$, which means a collection of sets $A_1,\dots,A_r$ such that we can find disjoint sets $H, P_1,\dots,P_r$ with the $P_i$ disjoint and with $A_i=H\cup P_i$ for each $i$. I have used the letters $H$ and $P$ to stand for “head” and “petal” — $H$ is the head of the sunflower and $P_1,\dots,P_r$ are the petals.

How many sets of size $k$ do you need to guarantee a sunflower of size $r$? A simple argument gives not too bad an upper bound of $k!(r-1)^k$. We argue as follows. Let $\mathcal{A}$ be a collection of $n=k!(r-1)^{k-1}r$ sets, each of size $k$. If we can find $r$ disjoint sets in $\mathcal{A}$ then we are done (with an empty head and the petals being the sets themselves). Otherwise, let $X$ be the union of a maximal disjoint collection of sets in $\mathcal{A}$, and note that $X$ has cardinality at most $(r-1)k$, and that every set in $\mathcal{A}$ has a non-empty intersection with $X$.

By the pigeonhole principle, we can find $x\in X$ and a subcollection $\mathcal{A}'$ of $\mathcal{A}$ containing at least $n/(r-1)k=(k-1)!(r-1)^{k-2}r$ sets, such that every set $A\in\mathcal{A}'$ contains $x$.

Now remove $x$ from all the sets in $\mathcal{A}'$ to create a collection $\mathcal{A}_1$ of sets of size $k-1$. By induction, this collection contains a sunflower of size $r$, and putting back the element $x$ then gives us a sunflower in $\mathcal{A}$. (The base case, when $k=1$, states that $r$ sets are enough to guarantee a sunflower of size $r$.)

How about a lower bound? An easy one is obtained as follows. Let $X_1,\dots,X_k$ be disjoint sets of size $r-1$ and let $\mathcal{A}$ consist of all sets that intersect each $X_i$ in exactly one place. There are $(r-1)^k$ such sets, and there cannot be a sunflower, since there is not enough room in each $X_i$ to make it possible to have $r$ disjoint petals.

The main question of interest is the dependence on $k$: for fixed $r$, does the correct bound grow exponentially (like the lower bound just given), or more like $k!$, or like something in between? Even when $r=3$, the first non-trivial case, the answer is not known (though there are bounds known that improve on the simple ones I’ve just given).

For more information, as well as a discussion about how a homological approach might be useful, see Gil’s post.

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.

If you have comments specific to what I’ve written above, such as to point out typos or inaccuracies, then by all means write them here, but if you have mathematical thoughts about the problem, please write them on Gil’s blog.

5 Responses to “Gil Kalai starts Polymath10”

1. Bruce Smith Says:

You said “disjoint sets H, P_1,\dots,P_r with the P_i disjoint”. Does H also need to be disjoint from the P_i?

• gowers Says:

Yes it does. So an example would be the sets $\{1,2,3,4\}, \{1,2,5,6\}$ and $\{1,2,7,8\}$. Those form a sunflower with head $\{1,2\}$ and petals $\{3,4\}, \{5,6\}$ and $\{7,8\}$.

2. Stan Dolan Says:

Even small values for k and r seem difficult to deal with! Apologies if the following is well-known but at least with k=2 one can see what is happening in terms of “playing-off” the effects of having no large sunflowers of either head size.

Suppose that the maximum size of a sunflower with no head in a family of 2-sets is r. Then the idea of the matching augmentation algorithm can be used to show that there are integers p and qi and disjoint sets Y and Xi such that:-
• r = p + Σqi
• Y has p elements
• Each Xi has 2qi +1 elements
• The given family consists only of sets with both elements in an Xi and sets with one or both elements in Y.

The maximum size of a sunflower with head of size 1 then limits the sizes of the p and qi. [Each i is supposed to be a suffix.]

3. Stan Dolan Says:

P.S. Thinking about how to write out a formal proof I realise that each Xi has a specific element which could be the same as the specific element of other Xi s – so they are almost disjoint!

4. attack on/ of the sunflowers! | Turing Machine Says:

[…] 10. Gil Kalai starts Polymath10 | Gowers’s Weblog […]