Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. 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
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 on his blog –  vzn Dec 1 '12 at 21:42
    
@vzn Thanks very much for the link. –  Yao Wang Dec 2 '12 at 7:54
    
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 Dec 2 '12 at 20:23
    
@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 Dec 3 '12 at 17:10
    
briefly, I am asking if we can improve the lower bound. –  Yao Wang Dec 3 '12 at 17:10

1 Answer 1

the Erdos sunflower conjecture 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

[2] The Monotone Complexity of k-Clique on Random Graphs (2009) Rossman

[3] Average-case complexity of detecting cliques by Rossman

[4] Commentary on Williams breakthrough on matrix product lower bound RJ Liptons Godels Lost Letter blog

[5] Detailed Materials on Sunflowers

share|improve this answer

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.