<p>the <a href="http://en.wikipedia.org/wiki/Sunflower_(mathematics)" rel="nofollow noreferrer">Erdos sunflower conjecture</a> seems to be very difficult after now over a half century(!) of being open. youve already listed some of the very best and most recent refs on the subj that would be very hard to beat (Alons recent paper, Juknas book on combinatorics). the Alon paper is highly notable for newly linking the conjecture to lower bounds on matrix multiplication, an area that has seen recent groundbreaking advance in the Williams results.[4]</p>

<p>you can find some further treatment, mainly applications to extremal circuit theory (circuit lower bounds 1st discovered by Razborov &amp; extended by others), in Jukna's outstanding book [1]. </p>

<p>one notable/related recent ref along these lines apparently not-so-widely-known-or-cited-so-far is [2] by Rossman with a new direction of application (Erdos-Renyi random graphs over monotone circuits) and who proves extended and/or stronger results on "quasi-" sunflowers. the paper is a result from his Phd thesis [3]. from the paper abstract</p>

<blockquote>
  <p>We introduce a new variant of sunflowers and prove an analogue of the sunflower lemma that may be of independent interest.</p>
</blockquote>

<p>[1] <a href="http://www.thi.informatik.uni-frankfurt.de/~jukna/boolean/index.html" rel="nofollow noreferrer">Boolean function complexity, advances and frontiers</a></p>

<p>[2] <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.156.5526" rel="nofollow noreferrer">The Monotone Complexity of k-Clique on Random Graphs (2009)</a> Rossman</p>

<p>[3] <a href="http://www.mit.edu/~brossman/mit-thesis.pdf" rel="nofollow noreferrer">Average-case complexity of detecting cliques</a> by Rossman</p>

<p>[4] <a href="http://rjlipton.wordpress.com/2011/11/29/a-breakthrough-on-matrix-product/" rel="nofollow noreferrer">Commentary on Williams breakthrough on matrix product lower bound</a> RJ Liptons Godels Lost Letter blog</p>

<p>[5] <a href="https://cstheory.stackexchange.com/questions/12641/detailed-materials-on-sunflowers">Detailed Materials on Sunflowers</a></p>

CC BY-SA 3.0
2012-12-02T17:36:30.013Z
2012-12-02T17:36:30.013Z
2017-04-13T12:32:28.167Z
vzn
<p>I am interesting in the sunflower system and its applications in computer science.</p>

<p>Given a Universe $U$ and a collection of $k$ sets $A_i$ is called a <strong>k-sunflower system</strong> 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.  </p>

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

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

<p>This result is called the sunflower lemma and has many important applications.</p>

<p>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)</p>

<p>Unfortunately, this conjecture is still open for $k=3$.</p>

<h2>Here is what I want to know.</h2>

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

<p>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|&gt;$ $c_i^s$ and $|U|=i$.</p>

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

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

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

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

<p>The paper above is one of its application(finite version)</p>

<p><a href="http://www.google.com/url?sa=t&amp;rct=j&amp;q=&amp;esrc=s&amp;source=web&amp;cd=1&amp;cad=rja&amp;ved=0CC4QFjAA&amp;url=http%3A%2F%2Fwww.cs.technion.ac.il%2F~shpilka%2Fpublications%2FASU11.pdf&amp;ei=u_y5UP6rKIWBiQei94DwDg&amp;usg=AFQjCNHnR0rNmULcyDTBGtvG3qsU5a9d2w&amp;sig2=BeclrG8vsTX_DJOAvrwSFg">On Sunflowers and Matrix Multiplication N Alon et.al </a></p>

CC BY-SA 3.0
2012-12-01T21:42:28.233Z
there does not seem to be much direct work on it other than new applications & alons recent paper you cite, which might increase interest & is prob best place to start for refs (& juknas book is also unbeatable). here is a nice summary of the interconnections by [kalai](http://gilkalai.wordpress.com/2011/12/09/cup-sets-sunflowers-and-matrix-multiplication/) on his blog
vzn
CC BY-SA 3.0
2012-12-02T20:23:12.857Z
i think having a $c_i$ that depends on $i = |U|$ makes the problem trivial, as you can set $c_i = 2^i$. also my impression is that having no dependence on $|U|$ is the interesting thing about the lemma
Sasho Nikolov
CC BY-SA 3.0
2012-12-03T17:10:16.613Z
@SashoNikolov. Thanks for reply Yes, what we want is having no dependence on $|U|$.   but if we have $|U|$, then we can explicitly build the maximal family $F$. What I wonder is that if this explicit building  could show something interesting for the problem. For example can we find  a family with $2^{i-\epsilon}$ that still does not contain a sunflower system. I tried to build such  maximal family, but it seems so hard. I cannot make some larger maximal family other that the example on Junka's Book(Cha7).
Yao Wang
CC BY-SA 3.0
2012-12-03T17:10:55.900Z
briefly, I am asking if we can improve the lower bound.
Yao Wang
<co.combinatorics><set-theory>
The state of art for sunflower system
Yao Wang
# The state of art for sunflower system

(Asked by: username_0 on 2012-12-01)

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](http://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&cad=rja&ved=0CC4QFjAA&url=http%3A%2F%2Fwww.cs.technion.ac.il%2F~shpilka%2Fpublications%2FASU11.pdf&ei=u_y5UP6rKIWBiQei94DwDg&usg=AFQjCNHnR0rNmULcyDTBGtvG3qsU5a9d2w&sig2=BeclrG8vsTX_DJOAvrwSFg)

**Tags:** co.combinatorics, set-theory
> **Comments:**
> **username_1**: there does not seem to be much direct work on it other than new applications & alons recent paper you cite, which might increase interest & is prob best place to start for refs (& juknas book is also unbeatable). here is a nice summary of the interconnections by [kalai](http://gilkalai.wordpress.com/2011/12/09/cup-sets-sunflowers-and-matrix-multiplication/) on his blog  
> **username_2**: i think having a $c_i$ that depends on $i = |U|$ makes the problem trivial, as you can set $c_i = 2^i$. also my impression is that having no dependence on $|U|$ is the interesting thing about the lemma  
> **username_0**: @SashoNikolov. Thanks for reply Yes, what we want is having no dependence on $|U|$.   but if we have $|U|$, then we can explicitly build the maximal family $F$. What I wonder is that if this explicit building  could show something interesting for the problem. For example can we find  a family with $2^{i-\epsilon}$ that still does not contain a sunflower system. I tried to build such  maximal family, but it seems so hard. I cannot make some larger maximal family other that the example on Junka's Book(Cha7).  
> **username_0**: briefly, I am asking if we can improve the lower bound.  

---

## 1 answers

### Answer by username_1 on 2012-12-02. Score: 7

the [Erdos sunflower conjecture](http://en.wikipedia.org/wiki/Sunflower_(mathematics)) seems to be very difficult after now over a half century(!) of being open. youve already listed some of the very best and most recent refs on the subj that would be very hard to beat (Alons recent paper, Juknas book on combinatorics). the Alon paper is highly notable for newly linking the conjecture to lower bounds on matrix multiplication, an area that has seen recent groundbreaking advance in the Williams results.[4]

you can find some further treatment, mainly applications to extremal circuit theory (circuit lower bounds 1st discovered by Razborov & extended by others), in Jukna's outstanding book [1].

one notable/related recent ref along these lines apparently not-so-widely-known-or-cited-so-far is [2] by Rossman with a new direction of application (Erdos-Renyi random graphs over monotone circuits) and who proves extended and/or stronger results on "quasi-" sunflowers. the paper is a result from his Phd thesis [3]. from the paper abstract

> We introduce a new variant of sunflowers and prove an analogue of the sunflower lemma that may be of independent interest.

[1] [Boolean function complexity, advances and frontiers](http://www.thi.informatik.uni-frankfurt.de/~jukna/boolean/index.html)

[2] [The Monotone Complexity of k-Clique on Random Graphs (2009)](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.156.5526) Rossman

[3] [Average-case complexity of detecting cliques](http://www.mit.edu/~brossman/mit-thesis.pdf) by Rossman

[4] [Commentary on Williams breakthrough on matrix product lower bound](http://rjlipton.wordpress.com/2011/11/29/a-breakthrough-on-matrix-product/) RJ Liptons Godels Lost Letter blog

[5] [Detailed Materials on Sunflowers](https://cstheory.stackexchange.com/questions/12641/detailed-materials-on-sunflowers)


---

