The Erdős–Ko–Rado theorem
Statement
Let and let be a family of -element subsets of such that any two sets of intersect. Prove that
Hint
Place the numbers around a circle in some order and look at the arcs of consecutive numbers. Show that an intersecting family contains at most arcs, then double count over all circular orders.
Show solutionHide solution
Solution
Idea (Katona). Count pairs (circular arrangement, arc of the arrangement belonging to ).
Step 1: at most arcs. Fix an arrangement of at positions of a circle, and call the arc of consecutive positions starting at . Suppose . Any other arc meeting starts at a position or . For the two arcs and are consecutive blocks of positions, hence disjoint because . Being intersecting, contains at most one of , . So at most arcs of the arrangement are in .
Step 2: double counting. Over all arrangements, the number of pairs (arrangement, arc in ) satisfies . On the other hand, a given set is an arc in exactly arrangements. So
∎
Sharpness. All -sets containing the element form an intersecting family of size .
Lesson. A cyclic arrangement turns a global set-system problem into a local one; then double count.