The Erdős–Ko–Rado theorem
ProvedFamousTheorems.erdos_ko_radoThe Erdős–Ko–Rado theorem. Let . If is a family of -element subsets of an -element set in which every two members intersect, then
The bound is attained by the star of all -sets through a fixed point. It is the founding result of extremal set theory. Katona's cyclic-permutation proof and its many variants for vector spaces, permutations and graphs make it a model for intersection theorems.
Formalization note. Mathlib's Finset.erdos_ko_rado, for families of finsets of Fin n; Set.Intersecting and Set.Sized r express pairwise intersection and uniform size .
Preamble
import Mathlib
Formal statement
namespace FamousTheorems
theorem erdos_ko_rado {n r : ℕ} {𝒜 : Finset (Finset (Fin n))} (h𝒜 : (𝒜 : Set (Finset (Fin n))).Intersecting)
(hr𝒜 : (𝒜 : Set (Finset (Fin n))).Sized r) (hr : r ≤ n / 2) : 𝒜.card ≤ (n - 1).choose (r - 1) := by sorry
end FamousTheoremsSource
Listed in Mathlib's curated theorem manifests (docs/1000.yaml); formalized in Mathlib as `Finset.erdos_ko_rado`. Proof here reduces to that Mathlib result.