Erdős–Ko–Rado theorem

For n ≥ 2k, any family of k-element subsets of an n-element set in which every pair intersects has at most \(\binom{n-1}{k-1}\) members. Equality is attained by all k-subsets containing one fixed element.

Katona's cyclic permutation method: A counting technique that arranges elements cyclically to prove bounds on set families. It proves the theorem by bounding how many members of an intersecting family can appear as cyclic intervals.
Uniform set family: A collection of sets all having the same cardinality. The theorem concerns families whose members each contain exactly k elements.
Paul Erdős: A Hungarian mathematician known for prolific collaboration and major contributions to combinatorics and number theory. He co-formulated the theorem and helped establish its early proof.
Intersecting code: A code whose distinct codewords have supports with nonempty intersection. Uniform supports of codewords can form families bounded by the theorem.
Hilton–Milner theorem: A bound on the largest nontrivial intersecting family of k-subsets when n is sufficiently large relative to k. It sharpens the bound when no single element belongs to every member.
Intersecting family: A family of sets in which every two distinct members have nonempty intersection. The theorem bounds the largest uniform intersecting families.
Binomial coefficient: The number of ways to choose a fixed number of elements from a finite set. It gives the exact maximum number of sets in the theorem.
Chao Ko: A mathematician who co-authored the 1938 paper introducing the Erdős–Ko–Rado theorem. His joint paper with Erdős gave the theorem its first proof.
Erdős–Ko–Rado theorem for permutations: An extremal result bounding pairwise-agreeing families of permutations. It transfers the intersecting-family question from subsets to permutations.
Erdős–Ko–Rado theorem for n less than 2k: Extremal bounds for intersecting k-subset families when the ground set has fewer than 2k elements. Below the theorem’s threshold, every two k-subsets intersect, so its bound no longer applies.

Linked from 5 pages