MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am interesting in the sunflower system and its applications in computer science.

Given a Universe $U$ and a collection of $k$ sets $A_i$ is called a k-sunflower system if $A_i \cap A_j = Y $ for all $i \neq j$. And $Y$ is called as the core and $A_i - Y$ is called petals.

A family of sets $F$ is called $s$-uniform is all the sets it contained possess $s$ elements.

Erdos and Rado proved that for a $s$ uniform family of sets $F$ , $F$ must contain a $k$-sunflower system petals if $|F| > s!(k-1)^s $.

This result is called the sunflower lemma and has many important applications.

Erdos conjectured that for every $k$ there exist a constant $c_k$ such that the upper bound should be $c_k^s$ every $s$-uniform family $F$. (The sunflower conjecture)

Unfortunately, this conjecture is still open for $k=3$.

Here is what I want to know.

If we limit the number of elements in the universe $U$.Suppose $|U|$= $u$. Then the problem turns out be:

Given a universe with $u$ elements, and $s$-uniform family $F$ of sets containing the elements in $U$, we supposed can find sequence of constants $c_1$, $c_2$, $c_3$ ,... such that every $s$-uniform family $F$ contains a $3$-sunflower system if $|F|>$ $c_i^s$ and $|U|=i$.

Moreover, if we could prove that the sequence $c_i$ converges to a constant $c$, then it seems we can prove the sunflower conjecture.

But I cannot find such result.It might be that this approach is too stupid or too hard.

Could any one provide the state of art of sunflower lemma and the conjecture(finite version is also OK).

Here is some I can provide. There is a chapter in Junka's book The Extremal Combinatorics.

The paper above is one of its application(finite version)

On Sunflowers and Matrix Multiplication N Alon

share|cite|improve this question
With a finite universe you can take $c_{|U|} > 2^{|U|}$, making the statement vacuous since no $F$ satisfy the condition. – Ben Barber Dec 1 '12 at 17:10
Nice question. The best result I know is due to Kostochka: For all $m>1$ there is a $c_m$ such that for any $n$, an $n$-uniform family $F$ not admitting a $3$-sunflower system and of largest possible cardinality satisfies $|F|\le c_m n! m^{-n}$. – Andrés E. Caicedo Dec 1 '12 at 17:15
@Andres could you give a link? I have got some Kostochka's papers. ButI might not have this one. – WangYao Dec 1 '12 at 18:06
@Ben. Yes.But since so $c_{|U|}>2^{|U|}$ is an trivial bound.We need something better. – WangYao Dec 1 '12 at 18:14
Wang, This is a few years old, so better results may be known. The reference I have is: MR1425216 (98d:05145) Alexandr V. Kostochka. A bound of the cardinality of families not containing $\Delta$-systems, in The mathematics of Paul Erdős, II, 229–235, Algorithms Combin., 14, Springer, Berlin, 1997. – Andrés E. Caicedo Dec 1 '12 at 20:24

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.