Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

$\newcommand{\ms}{\mathscr}$Please give me only a small hint, or give me an easier problem to solve that would help me do this.

A sunflower is a family of sets (petals) for which ever pairwise intersection is the same.

I want to prove

Sunflower Lemma: Let $\ms{A}$ be a family of sets such that $|A|\le\ell$ for each $A\in\ms{A}$. If $|\ms{A}|>(p-1)^\ell\ell!$, then $\ms{A}$ contains a sunflower with $p$ petals.

(Thanks to Brian M Scott for the correct statement of the lemma)


I though about this a lot but I didn't get much. First I realized that a family of sets like {1,2,3,4,5}, {1,2,3,4}, {1,2,3}, {1,2}, {1} is never a sunflower.

I also found that if there is no sunflower with empty core (I named the pairwise intersection the core) then our sets are made out of at most $lp$ symbols.

It's also impossible for our sunflower to have full core (equal to the whole set) because there would only be one set in our family of sets.

I tried to think a bit about the probability of two sets having an intersection, but it didn't seem fruitful because it's so complex to try to generalize this to more sets.

I was thinking for a while about the largest possible set containing no sunflower. If it didn't have any empty set in it's pairwise intersection then out of every $p$ sets at least one pair must have a nonempty intersection. I tried to use pigeonhole principle to get 3 petals but this gave a too weak bound.


I am thinking about some way of doing the induction step for $\ell$ like for sets of size $\ell$ then $|\ms{A}|>N=(p-1)^\ell\ell!$ has n $p$-sunflower $\implies |\ms{A}|>N \cdot (p-1)(\ell+1)$ for sets of size $\ell+1$ has a $p$-sunflower. The is that if you allow the sets to be bigger, they're much more capable of avoiding being sunflowers. The reason for that might be related to my first observation. If I have $N \cdot (p-1)(\ell+1)$ then I was first thinking each of the $(p-1)(\ell+1)$ blocks of size $N$ have a sunflower in them but I don't actually have that so I need a new idea.


From Andres Caicedo hints I have the following:

The proof should work by induction on $\ell$, so suppose than any family of sets of size $\ell$ will contain a $p$-petalled sunflower if $|\ms{A}| > N$, we would like to find a bound on the cardinality of a family of sets of size $\ell+1$ needed for it to contain a $p$-petalled sunflower.

Suppose there are not $p$ pairwise disjoint sets, since if there were we would be done.

Let $\ms{F}$ be a maximal disjoint subfamily of $\ms{A}$, then every set from $\ms{A}$ has nonempty intersection with exactly one set of $\ms{F}$ (otherwise it should have been included in $\ms{F}$ since it's disjoint to everything in there). This allows us to partition $\ms{A}$ into families $\ms{A}_F$ for each $F \in \ms{F}$ and any sunflower must be completely contained in one of the families.

Since there are at most $p-1$ of the $\ms{A}_F$, we we would be able to get a bound for $\ms{A}$ and be done by pigeonholing if we could just figure out how large an $\ms{A}_F$ needs to be for there to be a $p$-petalled sunflower in it. This plan seems promising but I don't quite see how we could go from the idea of induction on $\ell$ to the idea of taking a maximal disjoint subfamily.

If any element was in more than $N$ of sets then we would have a sunflower by the induction hypothesis (just remove the element and we have a family of $N$ $\ell$ sets). So I asked: How many sets would we need to meet $F$ in order for an element to be contained in $N$ of them? The answer is $N|F|$ which is at most $N (\ell+1)$.

The pigeonholing argument gives us that we need $N \cdot (p-1)(\ell+1)$ sets in $\ms A$.

share|improve this question
1  
What's the constraint on $l$? There must be one, because otherwise $l=1$ is a trivial counterexample. –  Peter Taylor Dec 1 '12 at 20:48
    
@PeterTaylor, I think it's not a counterexample because a single set is a 1-petal sunflower. Please correct me if I'm wrong. –  user51427 Dec 1 '12 at 21:07
1  
$l$, not $p$. If there are $(p-1)$ sets there can't be $p$ of them which form a sunflower. (Although $p=1$ is also a counterexample, because if there are $0$ sets you can't choose that single set to be a $1$-petal sunflower). –  Peter Taylor Dec 1 '12 at 21:13
1  
I think you have to have an assumption for the size of the total set of all symbols for this statement to be non-trivial. Clearly you can define arbitrarily many subsets of $\mathbb{N}$, all pairwise disjoint, all of a fixed size. –  Hans Engler Dec 1 '12 at 22:23
1  
@sunflower: your accounts have been merged. (Hopefully I merged them in the correct direction.) –  Qiaochu Yuan Dec 2 '12 at 1:53

2 Answers 2

up vote 4 down vote accepted

[The original formulation of the question had $|\mathcal A|\ge(p-1)^l l!$ rather than $|\mathcal A|>(p-1)^l l!$. The result is true in this case, but a somewhat more delicate argument in needed, which made me suspect the intended question had the strict inequality, as in the current version. Some of the comments below refer to this original formulation.]

Pretty sure there is a mistake in your statement, and what you want is to show that a family $\mathcal A$ with more than $(p-1)^l l!$ many sets of size at most $l$ contains $p$ that form a sunflower. (Sunflowers are also called $\Delta$-systems, by the way.)

A reasonable approach is by induction on $l$. The result is clear if $l=1$, since then we have at least $p$ distinct singleton sets in $\mathcal A$, which therefore are pairwise disjoint.

We may assume that we do not have $p$ disjoint sets, and also that no element $x_0$ belongs to too many sets in $\mathcal A$: If $x_0$ is in more than $(p-1)^{k-1}(k-1)!$ many sets, we can restrict to them, remove $x_0$ from each, and apply induction.

The key idea is to combine these two observations. Pick a maximal pairwise disjoint subfamily $\mathcal F$. Maximality buys us that any other set in $\mathcal A$ meets one of the sets in this subfamily. This gives you a way of bounding $|\mathcal A|$: There are at most $l-1$ sets in the disjoint subfamily, and any other set, must meet something in $\mathcal F$. But we have a bound on the number of times we can have any element. I'll leave the details to you.

Let me add that the original proof, in

Paul Erdős, and Richard Rado. Intersection theorems for systems of sets, Journal of the London Mathematical Society, 2nd. series 35 (1), (1960), 85–90. MR0111692 (22 #2554)

starts the same way, and obtains a somewhat better bound, by an inclusion-exclusion argument: It is enough to assume $$ |\mathcal A|> l!(p-1)^{l+1}\left(1-\frac1{2!(p-1)}-\frac2{3!(p-1)^2}-\dots-\frac{l-1}{l!(p-1)^{l-1}}\right). $$

share|improve this answer
    
I see that while I was hunting for the exact reference, Brian posted an (excellent, as usual) answer that explains the idea behind the improvement I mention in the last line. (And addresses your question, as stated, with $\ge$ rather than $>$.) –  Andres Caicedo Dec 1 '12 at 23:15
    
Essentially the same idea is behind the key combinatorial argument that lead to the following paper: "Defining non-empty small sets from families of finite sets", with John Clemens, Clinton Conley, and Benjamin Miller. You can download it from my papers' page: andrescaicedo.wordpress.com/papers –  Andres Caicedo Dec 2 '12 at 2:49

$\newcommand{\ms}{\mathscr}$What you call the core is also called the kernel of the sunflower. (By the way, another term for sunflower, especially in infinite combinatorics, is $\Delta$-system.)

The theorem as stated is false for $p=1$: if $p=1$, then $(p−1)^\ell\ell!=0$, but an empty family clearly does not contain a sunflower with one petal. With a small change, however, you can make it true even in the case $\ell=1$; the result, due to Erdős and Rado, is known as the

Sunflower Lemma: Let $\ms{A}$ be a family of sets such that $|A|\le\ell$ for each $A\in\ms{A}$. If $|\ms{A}|>(p-1)^\ell\ell!$, then $\ms{A}$ contains a sunflower with $p$ petals.

Proof: The proof is by induction on $\ell$. The result is clear for $\ell=1$: any $p$-subset of $\ms A$ is a sunflower with $p$ petals (and empty kernel). (Note that one of the petals may be empty, if $\varnothing\in\ms A$.)

Now suppose that $\ell\ge 2$, let $\ms A$ be family of more than $(p-1)^\ell\ell!$ sets of cardinality at most $\ell$, and let $\ms D=\{A_1,\dots,A_m\}$ be a maximal pairwise disjoint subfamily of $\ms A$. If $m\ge p$, $\ms D$ contains a sunflower with $p$ petals (and empty kernel), so assume that $m<p$. Let $D=\bigcup\ms D$; clearly $|D|\le m\ell\le(p-1)\ell$. Since $\ms D$ is maximal, $A\cap D\ne\varnothing$ for each $A\in\ms A$, so by the pigeonhole principle some $x\in D$ belongs to at least $$\left\lceil\frac{|\ms A|}{|D|}\right\rceil>\frac{(p-1)^\ell\ell!}{(p-1)\ell}=(p-1)^{\ell-1}(\ell-1)!$$ members of $\ms A$. Let $\ms{A}_0=\big\{A\setminus\{x\}:x\in A\in\ms A\big\}$; then each element of $\ms A_0$ has cardinality at most $\ell-1$, and $|\ms A_0|>(p-1)^{\ell-1}(\ell-1)!$, so by the induction hypothesis $\ms A_0$ contains a sunflower $\ms A$ with $p$ petals. Clearly $\big\{S\cup\{x\}:S\in\ms S\big\}$ is a subset of $\ms A$ that forms a sunflower with $p$ petals. $\dashv$

Let $\varphi(\ell,p)$ be the smallest positive integer such that each family of $\varphi(\ell,p)$ sets, each of cardinality at most $\ell$, contains a sunflower with $p$ petals. The sunflower lemma says that $\varphi(\ell,p)\le(p-1)^\ell\ell!+1$. The question asks to replace this bound by $(p-1)^\ell\ell!$ when $\ell>1$, and we saw above that for this improvement we must also require that $p>1$. Let’s see what happens when we try to prove the stronger result.

The induction step in the proof of the sunflower lemma still works: we get some $x\in D$ that belongs to at least $(p-1)^{\ell-1}(\ell-1)!$ members of $\ms A$, which is all that is needed to apply the induction hypothesis. To get the induction off the ground, however, we must show that if $\ms A$ is a family of $2(p-1)^2$ sets of cardinality at most $2$, then $\ms A$ contains a sunflower with $p$ petals.

This is clear when $p=2$: then $2(p-1)^2=2$, and any pair of sets of cardinality at most $2$ is a sunflower with two petals. Suppose that $p>2$. As before let $\ms D$ be a maximal pairwise disjoint subset of $\ms A$; if $|\ms D|\ge p$, we’re done, so suppose that $|\ms D|<p$. Let $D=\bigcup\ms D$; $|D|\le2(p-1)$. If $|D|<2(p-1)$, some $x\in D$ belongs to at least $p$ members of $\ms A$, and we can argue as before to find a sunflower in $\ms A$ with $p$ petals. Assume, then, that $|D|=2(p-1)$ and further that each $x\in D$ belongs to exactly $p-1$ members of $\ms A$. Then $\ms D$ contains exactly $p-1$ doubletons, and each point of $D$ is contained in exactly $p-1$ members of $\ms A$. For $x\in D$ let $\ms A_x=\{A\in\ms A:x\in A\}$; then for each $x\in D$ we have $|\ms A_x|=p-1$ and $|\ms A_x\cap\ms D|=1$, so $$|\ms A|=|\ms D|+\sum_{x\in D}\big(|\ms A_x|-1\big)=p-1+2(p-1)(p-2)=2(p-1)\left(p-\frac32\right)<2(p-1)^2\;,$$ which is a contradiction. Thus, $\ms A$ must in fact contain a sunflower with $p$ petals, and the induction does get off the ground.

This shows that the desired result holds provided that $p,\ell>1$.

share|improve this answer

Your Answer

 
discard

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