Maths WorkshopMaths problems with full solutions
Exercise 2237Combinatorics › Counting principlesOlympiadAdded 5 Nov 2026

The Erdős–Ko–Rado theorem

#set systems#double counting#intersecting families#Katona

Statement

Let n≥2kn\ge2k and let F\mathcal F be a family of kk-element subsets of {1,…,n}\{1,\dots,n\} such that any two sets of F\mathcal F intersect. Prove that
∣F∣≤(n−1k−1).|\mathcal F|\le\binom{n-1}{k-1}.

Hint

Place the numbers around a circle in some order and look at the nn arcs of kk consecutive numbers. Show that an intersecting family contains at most kk arcs, then double count over all circular orders.

Show solutionHide solution

Solution

Idea (Katona). Count pairs (circular arrangement, arc of the arrangement belonging to F\mathcal F).

Step 1: at most kk arcs. Fix an arrangement of 1,…,n1,\dots,n at positions 0,…,n−10,\dots,n-1 of a circle, and call ItI_t the arc of kk consecutive positions starting at tt. Suppose I0∈FI_0\in\mathcal F. Any other arc meeting I0I_0 starts at a position t∈{1,…,k−1}t\in\{1,\dots,k-1\} or t∈{−1,…,−(k−1)}t\in\{-1,\dots,-(k-1)\}. For i=1,…,k−1i=1,\dots,k-1 the two arcs IiI_i and Ii−kI_{i-k} are consecutive blocks of kk positions, hence disjoint because 2k≤n2k\le n. Being intersecting, F\mathcal F contains at most one of IiI_i, Ii−kI_{i-k}. So at most 1+(k−1)=k1+(k-1)=k arcs of the arrangement are in F\mathcal F.

Step 2: double counting. Over all n!n! arrangements, the number NN of pairs (arrangement, arc in F\mathcal F) satisfies N≤k⋅n!N\le k\cdot n!. On the other hand, a given set A∈FA\in\mathcal F is an arc in exactly n k! (n−k)!n\,k!\,(n-k)! arrangements. So
N=∣F∣⋅n k! (n−k)!≤k⋅n! ⟹ ∣F∣≤kn(nk)=(n−1k−1).N=|\mathcal F|\cdot n\,k!\,(n-k)!\le k\cdot n!\ \Longrightarrow\ |\mathcal F|\le\frac kn\binom nk=\binom{n-1}{k-1}.
∎

Sharpness. All kk-sets containing the element 11 form an intersecting family of size (n−1k−1)\binom{n-1}{k-1}.

Lesson. A cyclic arrangement turns a global set-system problem into a local one; then double count.