In extremal combinatorics,there is a theorem called sunflower lemma:
Let $\mathcal F$ be a family of non-empty $s$-subsets of a set $X$.If $|\mathcal F|>s!(k-1)^s$ then $\mathcal F$ contains a sunflower with $k$-petals.
I should give the definitions of the terminologies used in the statement.Here they are:
Definition(Sunflower): A sunflower with $k$-petals and a core/kernel $Y$ is a collection of sets $S_1,S_2,...,S_k$ such that $S_i\cap S_j=Y$ for all $i\neq j$.The sets $S_i\setminus Y$ are called petals and are required to be non-empty.However the core can be empty.
Having stated the theorem,let us take a look at the proof of the theorem:
Proof: The proof uses induction on $s$.
When $s=1$ let $|\mathcal F|>1!(k-1)^1=k-1$.Then $\mathcal F$ contains at least $k$ singletons,which are disjoint and hence form a sunflower with $k$-petals with empty core.
Now take $s\geq 2$ and let the result hold for sets of cardinality $\leq s-1$.
Now,take a maximal family of pairwise disjoint members of $\mathcal F$ say $\mathcal A=\{A_1,...,A_t\}$
If $t\geq k$ then there is a sunflower with $k$-petals and empty core.
So assume $t\leq k-1$.
Let $B=A_1\cup...\cup A_t$,then $|B|\leq st\leq s(k-1)$.
By maximality of $\mathcal A$, $B$ intersects any member of $\mathcal F$.
By pigeonhole principle,$\exists x\in B$ such that $x$ is in at least $\frac{|\mathcal F|}{|B|}$ members of $\mathcal F$.$(\color{red}{\text{How does pigeonhole apply and why will this number be an integer?}})$.Note that $\frac{|\mathcal F|}{|B|}>\frac{s!(k-1)^s}{s(k-1)}=(s-1)!(k-1)^{s-1}$.
Name the collection of these members of $\mathcal F$ to be $\mathcal C$.
Let, $\mathcal F_x=\{S\setminus \{x\}:x\in S,S\in \mathcal F\}$,then $|\mathcal F_x|=|\mathcal C|=(s-1)!(k-1)^{s-1}(\color{red}{\text{Why does cardinality equal to this number?}})$
So,by induction hypothesis,this $\mathcal F_x$ contains a sunflower of $k$-petals so that $\mathcal C$ forms a sunflower with $k$-petals.
I have doubts in the two lines marked above and the queries are also mentioned.Can someone give me some analogy or a concrete example of:
$(1)$ How pigeonhole principle applies here and why is the quotient an integer?
$(2)$ Why is $|\mathcal C|$ equal to that quantity?
$(1)$ Intuitively, the no. of elements in $B$ is quite small compared to the size of $\mathcal{F}$. Therefore, since every element in $\mathcal{F}$ must intersect non-trivially with $B$, each element must, on average, be in a large no. of members (approx. $\frac{|\mathcal{F}|}{|B|} $) of $\mathcal{F}$.
We can apply PHP to this in this form: If the average of $k$ non-negative numbers is $n$, then there is a number that is at least $\geq n$.
Rigorously, write $G_x$ to be subsets in $\mathcal{F}$ that contain $x\in B$ . We have that $\cup_{x\in B} G_x=\mathcal{F}$ and so, $\sum_{x\in B} |G_x| \geq |\mathcal{F}| \implies \frac{\sum_{x\in B} |G_x|}{|B|}\geq \frac{|\mathcal{F}|}{|B|}$.
No, the quotient need not be an integer. PHP still applies and $|\mathcal{C}|\geq \lceil \frac{|\mathcal{F}|}{|B|}\rceil$.
$(2)$ I don't think it needs to be necessarily equal to that number. For induction to be applicable, we just need it to be greater than that number $(s-1)!(k-1)^{s-1}$ and it certainly is.