2
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ In your first paragraph, should each of the $p$ petals be the empty set rather than $S$? $\endgroup$ – Nizbel99 Jul 23 '15 at 21:31
  • 1
    $\begingroup$ @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$. $\endgroup$ – Brian M. Scott Jul 23 '15 at 21:32
0
$\begingroup$

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!$.

$\endgroup$
  • $\begingroup$ The OP’s version, with exponent $\ell+1$ instead of $\ell$, actually allows duplicates. $\endgroup$ – Brian M. Scott Jul 23 '15 at 21:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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