Erdos-Ko-Rado Theorem

The Erdos-Ko-Rado theorem is a cornerstone of extremal set theory, providing a tight upper bound on the size of an intersecting family of $k$ -element subsets and characterizing the extremal families.

Statement

Theorem4.3Erdos-Ko-Rado Theorem

Let $n \geq 2k$ and let $\mathcal{F} \subseteq \binom{[n]}{k}$ be an intersecting family, meaning $A \cap B \neq \emptyset$ for all $A, B \in \mathcal{F}$ . Then $|\mathcal{F}| \leq \binom{n-1}{k-1}.$ Moreover, if $n > 2k$ , equality holds if and only if $\mathcal{F}$ is a star, i.e., all members of $\mathcal{F}$ contain a common element.

Proof via Double Counting

Proof

We use the elegant Katona proof via cyclic permutations. Consider the $n!$ permutations of $[n]$ , and for each permutation $\sigma$ , define the $n$ arcs of length $k$ cyclically: $A_i(\sigma) = \{\sigma(i), \sigma(i+1), \ldots, \sigma(i+k-1)\}$ where indices are taken modulo $n$ .

Claim: Among any $n$ cyclically consecutive $k$ -subsets, at most $k$ can belong to an intersecting family $\mathcal{F}$ .

Indeed, if $A_i, A_j \in \mathcal{F}$ with $i < j$ , then $A_i \cap A_j \neq \emptyset$ forces the arcs to overlap, so $j - i < k$ or $j - i > n - k$ . Thus the indices of arcs in $\mathcal{F}$ form an intersecting family of arcs on the cycle, and at most $k$ arcs can be mutually intersecting.

Now count pairs $(\sigma, A)$ where $\sigma$ is a permutation and $A \in \mathcal{F}$ is one of the $n$ cyclic arcs of $\sigma$ . Each set $A \in \mathcal{F}$ appears as a cyclic arc in exactly $k!(n-k)! \cdot n / n = k!(n-k)!$ permutations (there are $n$ starting positions, but each set is counted once). So the count is $|\mathcal{F}| \cdot k!(n-k)!$ . On the other hand, for each permutation, at most $k$ arcs belong to $\mathcal{F}$ , giving an upper bound of $n! \cdot k$ . Therefore: $|\mathcal{F}| \cdot k!(n-k)! \leq k \cdot n! \implies |\mathcal{F}| \leq \frac{k \cdot n!}{k!(n-k)!} = \binom{n-1}{k-1}. \qquad \square$

■

Extensions

Definition4.4$t$-Intersecting Family

A family $\mathcal{F} \subseteq \binom{[n]}{k}$ is $t$ -intersecting if $|A \cap B| \geq t$ for all $A, B \in \mathcal{F}$ . The Frankl-Wilson theorem and the Complete Intersection theorem (Ahlswede-Khachatrian) generalize the EKR bound to $t$ -intersecting families.

ExampleIntersecting Families with $n = 2k$

When $n = 2k$ , the bound $|\mathcal{F}| \leq \binom{2k-1}{k-1} = \frac{1}{2}\binom{2k}{k}$ still holds, but uniqueness of the extremal family fails. For instance, with $n = 4, k = 2$ , both the star $\{\{1,2\}, \{1,3\}, \{1,4\}\}$ and the family $\{\{1,2\}, \{1,3\}, \{2,3\}\}$ achieve the maximum size $3 = \binom{3}{1}$ .

RemarkCross-Intersecting Generalization

The cross-intersecting version states: if $\mathcal{A}, \mathcal{B} \subseteq \binom{[n]}{k}$ satisfy $A \cap B \neq \emptyset$ for all $A \in \mathcal{A}, B \in \mathcal{B}$ , and $n \geq 2k$ , then $|\mathcal{A}| \cdot |\mathcal{B}| \leq \binom{n-1}{k-1}^2$ .