Probabilistic Method – 2

Q.1. Let $n \geq 2k$ be positive integers. Let $\mathcal{C}$ be a collection of pairwise intersecting $k-$element subsets of $[n] = \{1, 2, \ldots, n\}$  (i.e. if $A, B \in \mathcal{C}$, then $A \cap B \neq \phi$). Prove that $|C| \leq { {n-1} \choose {k-1}}$.

Solution.

Let $A$ be a $k-$element subset of $[n]$ selected uniformly at random from the ${n} \choose {k}$ possible such subsets.

Now, $Pr[A \in \mathcal{C}] \leq k/n \Rightarrow |C| \leq { {n} \choose {k} } . k/n = { {n-1} \choose {k-1}}$.

We will try to prove that $Pr[ A \in \mathcal{C}] \leq k/n$.

Let $A$ be selected as follows. Take a random permutation $\sigma \in \mathcal{S}_n$. Take a random index $1 \leq i \leq n$, and let $A = \{i, \ldots, i + k-1\}$ (wrapped around $n$).

Now, if given a fixed $\sigma$, $Pr[ A \in \mathcal{C}| \sigma] \leq k/n$, then $Pr[ A \in \mathcal{C}] \leq k/n$.

Further, since there are at most $k$ possible indices for $i$ such that $\{\sigma(i), \ldots, \sigma(i+k-1)\}$ (wrapping around $n$) can be a part of $\mathcal{C}$ (due to the property of pairwise intersection), $Pr[ A \in \mathcal{C} | \sigma ] \leq k/n$.

$--$