What is the lower bound of $f(s,k)$?

167 Views Asked by At

$\underline {\textbf {Sunflower Lemma}}$ $:$

Let $\mathcal F$ be a family of non-empty sets each of cardinality $s\ ( \geq 1)$. If $\lvert \mathcal F \rvert > s!\ (k-1)^s$ then $\mathcal F$ contains a sunflower with $k$-petals.

Now let $f(s,k)$ be the least integer such that any family of $f(s,k)$ non-empty sets each of cardinality $s$, contains a sunflower with $k$-petals. Then sunflower lemma gives an upper bound of $f(s,k)$ which is $s!\ (k-1)^s + 1$. So $f(s,k) \leq s!\ (k-1)^s + 1$. Also our instructor has left as an exercise to prove that $f(s,k) > (k-1)^s$. But how do I prove that? According to me if we can find a family $\mathcal F$ with $\lvert \mathcal F \rvert = (k-1)^s$ such that $\mathcal F$ doesn't contain any sunflower with $k$-petals then we are through. But how do I find such an example. Please help me in this regard.

Thank you very much.

1

There are 1 best solutions below

5
On BEST ANSWER

I'm going to guess that by "sunflower with $k$ petals" (which you didn't define) you mean a family of $k$ sets whose pairwise intersections are all the same; in other words, any element which belongs to more than one of them must belong to all of them.

You want a family $\mathcal F$ of $s$-element sets with $|\mathcal F|=(k-1)^s$. Let's try the most obvious example of such a family: take $s$ disjoint sets $A_1,\dots,A_s$ with $|A_1|=\cdots=|A_s|=k-1$ and let $\mathcal F$ be the family of sets obtained by choosing one element from each $A_i$. Plainly $|\mathcal F|=(k-1)^s$ and each element of $\mathcal F$ has $s$ elements.

Assume for a contradiction that $\{S_1,S_2,\dots,S_k\}\subseteq\mathcal F$ is a sunflower with $k$ petals. Then for each $i\in\{1,\dots,s\}$, the family $\{S_1\cap A_i,S_2\cap A_i,\dots,S_k\cap A_i\}$ is a sunflower. Since $A_i$ has only $k-1$ elements, this is only possibly if $S_1\cap A_i=S_2\cap A_i=\cdots=S_k\cap A_i=\{a_i\}$ for some element $a_i\in A_i$. But this means that $S_1=S_2=\cdots=S_k$, contradicting the assumption of a sunflower with $k$ petals.