Erdos Ko Rado Theorem

Let $\mathcal{F}$ be a family of $ k $-element subsets of $ \{ 1,2,\dots,n \} $ such that  every two sets in $\mathcal{F} $ intersect in at least one element. Then show that $ | \mathcal{F}  | \leq \binom{n-1}{k-1}$

Claim : Let $ X $ be any permutation of $ \{ 1,2 \dots, n \} $ on a circle. Consider all the intervals of the length $k$. Then at most $k$ such intervals belongs to $ \mathcal{F} $

Proof : Consider all the intervals $ \in \mathcal{F} $ ( in clockwise order ), we color the last element of the interval blue, and the element just before its first term red.

The marked set represents the interval

Now we show that no element has both the colors.

Suppose on the contrary, $ \exists $ an element which is both colored blue as well as red, then the two intervals defined by this element are disjoint, which gives us a contradiction. 

Now consider the element which is colored blue. Then, in the next $ n - 2k $ elements, none of them can be colored red, because or else, the two intervals would be disjoint.

The blue points are obtained from the red points by moving $k$ units in clockwise direction. So as $ \exists $ an interval of length $ n -2k $, with no red points $ \Rightarrow \exists $ an interval of length $ n - 2k $, with no blue points.

Now, rotate this interval of length $ n - 2k $ until the first time its first element is following a blue point, then this interval of $ n-2k $ has no blue points as well as no red points. So the remaining $ 2k  $ points contains all the red and blue points, and as each element has only one color, we get there are at most $k$ red points and $k$ blue points. Hence there are at most $k$ such intervals, which completes our claim.

Now we are going to use another very fundamental strategy in combinatorics problem, which is double counting. 

Let us count the number of tuples 

$ T = \{ (A, \sigma ) | A \in \mathcal{F} \mbox{ and } \sigma \mbox{ be a cyclic permutation of }\{1,2,\dots,n \} \mbox{ which contains } A \} $

First let us fix $A$, then there are $ k!(n-k)! $ permutations of $ \{ 1,2,\dots,n\} $ on a circle such that it contains $A$.

$ \Rightarrow | T | = | \mathcal{F} | k!(n-k)! $

Now let us fix $ \sigma $, then by our claim $ \exists $ at most $ k $ intervals $\in \mathcal{F} $.

$\Rightarrow |T| \leq (n-1)! k$

$ \therefore | \mathcal{F} | k!(n-k)! \leq (n-1)! k $

$ \boxed{ \Rightarrow | \mathcal{F} | \leq \binom{n-1}{k-1} } $

Hence, proved.