If and is intersecting, then .
For an intersecting family of -sets with , the rank- lower shadow of its complement family is disjoint from the original family. Iterating the Kruskal-Katona theorem shows that exceeding original members would force this shadow to have more than members, contradicting the total number of -sets.
Katona's circle method places a finite ground set in a uniformly counted cyclic order, proves a bound for the members of a set family that appear as cyclic intervals, and double-counts pairs of a member and a compatible cyclic order.
In any cyclic ordering on points, an antichain contains at most nonempty proper cyclic intervals. The intervals with one prescribed final position are nested, so at most one belongs to the antichain. Summing over final positions proves the bound. Averaging it over cyclic orderings proves the LYM inequality; the empty set and full set must be handled separately.
An intersecting family of cyclic intervals of length in a cyclic order of positions has at most members when . Rotate one selected interval to end at position . Intervals ending at miss it. Pair the remaining endpoints, other than , as for ; each pair represents two disjoint intervals, hence contributes at most one member. This gives . Counting such intervals over all permutations proves the Erdős-Ko-Rado theorem.
Articles by others on the same topic
The Erdős–Ko–Rado theorem is a fundamental result in combinatorial set theory, particularly in the area concerning intersecting families of sets. It was first proved by Paul Erdős, Chao Ko, and Ronald Rado in 1961. ### Statement of the Theorem: For a finite set \( X \) with \( n \) elements, let \( k \) be a positive integer such that \( k \leq \frac{n}{2} \).