8
$\begingroup$

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

Improve this question
$\endgroup$
8
  • $\begingroup$ With a finite universe you can take $c_{|U|} > 2^{|U|}$, making the statement vacuous since no $F$ satisfy the condition. $\endgroup$
    – Ben Barber
    Commented Dec 1, 2012 at 17:10
  • $\begingroup$ 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}$. $\endgroup$
    – Andrés E. Caicedo
    Commented Dec 1, 2012 at 17:15
  • $\begingroup$ @Andres could you give a link? I have got some Kostochka's papers. ButI might not have this one. $\endgroup$
    – WangYao
    Commented Dec 1, 2012 at 18:06
  • $\begingroup$ @Ben. Yes.But since so $c_{|U|}>2^{|U|}$ is an trivial bound.We need something better. $\endgroup$
    – WangYao
    Commented Dec 1, 2012 at 18:14
  • 1
    $\begingroup$ 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. $\endgroup$
    – Andrés E. Caicedo
    Commented Dec 1, 2012 at 20:24

0

Reset to default

You must log in to answer this question.