Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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 et.al

share|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}$. –  Andres 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
1  
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. –  Andres Caicedo Dec 1 '12 at 20:24

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.