# Sunflower Lemma - Allow Duplicates?

The sunflower lemma states that if we have a family of sets $S_1, S_2, \cdots, S_m$ such that $|S_i| \leq l$ for each $i$, then $m > (p-1)^{l+1}l!$ implies that the family contains a sunflower with $p$ petals. My question is, do the $S_i$'s need to be distinct sets or can there be duplicates (i.e $S_i = S_j$ for some $i \neq j$). Would both of these sets be a part of the sunflower in such a case?

The usual statement of the lemma requires only that $m>(p-1)^\ell\ell!$, and in that case the sets must be distinct. Your version allows duplicates. To see this, suppose that $m>(p-1)^{\ell+1}\ell!$, and we have sets $S_1,\ldots,S_m$ such that $|S_k|\le\ell$ for $k=1,\ldots,m$. If there are $p$ or more duplicates of some set $S$, any $p$ of those duplicates form a sunflower with kernel $S$, each of the $p$ petals also being $S$. Otherwise, there are at most $p-1$ copies of each distinct set in the family, and $$m>(p-1)\cdot(p-1)^\ell\ell!\;,$$ so there must be more than $(p-1)^\ell\ell!$ distinct members of the family. We can apply the usual form of the sunflower lemma to these distinct members to get a sunflower with $p$ petals.
In other words, requiring that $m>(p-1)^{\ell+1}\ell!$ allows you to apply the lemma to multisets rather than just to sets, but the resulting sunflower may also be a multiset of petals rather than a set of petals.
• In your first paragraph, should each of the $p$ petals be the empty set rather than $S$? – Nizbel99 Jul 23 '15 at 21:31
• @Nizbel99: Depends on what you mean by petal. I use the term for the sets in the sunflower family, so for me it’s $S$; if you’re using it for the non-kernel part of the set, then it’s $\varnothing$. – Brian M. Scott Jul 23 '15 at 21:32
From what I read in Wikipedia, the lemma is about a collection of sets, not a family of sets. So duplicates are disallowed. Indeed, Let $S_0=\{1,2\}$ and $S_2=\ldots =S_m=\{1,3\}$ then no sunflower with $p=3$ petals can be formed, but we can certainly make $m>(p-1)^{l+1}l!$.
• The OP’s version, with exponent $\ell+1$ instead of $\ell$, actually allows duplicates. – Brian M. Scott Jul 23 '15 at 21:24