Choose many r-element subsets of an n-element ground set, requiring every two chosen subsets to share at least one element. When r is no more than half of n, Erdős–Ko–Rado gives the numerical ceiling binom(n−1,r−1) for the number of chosen subsets.
A visual guide to the theorem's hypotheses, structure, and conclusion; the exact statement gives the formal detail.
Erdős–Ko–Rado at a glance
Loading full-resolution image…
Complements and an iterated-shadow bound turn pairwise intersection into the cardinality obstruction behind Erdős–Ko–Rado.Open original image in a new tab
Complements and an iterated-shadow bound turn pairwise intersection into the cardinality obstruction behind Erdős–Ko–Rado. Explanatory diagram.Detailed visual description
The poster makes the three hypotheses and upper bound primary, using a three-card example whose pairwise overlaps are different. Its source route takes complements, descends by an iterated shadow, uses disjointness from the original family, invokes the Lovász Kruskal–Katona bound, and finishes with Pascal’s binomial identity. The footer excludes equality classification.
This map summarizes the statement's structure; the exact Mathlib declaration remains authoritative.
Erdős–Ko–Rado Theorem — scientific diagram
Loading full-resolution image…
A uniform family can be pairwise intersecting through different shared elements; pairwise intersection does not require one element common to every member.Open original image in a new tab
A uniform family can be pairwise intersecting through different shared elements; pairwise intersection does not require one element common to every member. Explanatory scientific diagram.Detailed visual description
The schematic uses three illustrative 3-subsets of a six-element ground set. Each row has exactly three filled incidence cells. Rows one and two share column three, rows one and three share column one, and rows two and three share column five. This local example illustrates uniformity and pairwise intersection without depicting the theorem’s upper bound, a star construction, sharpness, or an equality case.
Why it matters
A mathematical landmark
Erdős–Ko–Rado is a foundational extremal set theorem. Mathlib derives its upper bound through complements, an iterated shadow, disjointness, and the Lovász form of Kruskal–Katona, giving the page a theorem-specific checked proof architecture.
Accepted Atlas resultNot recorded for the preferred artifact
Mathlib is the source of the theorem; the local Lean replay and page review are separate.
Claim boundary
No new theorem is claimed
This page indexes Mathlib’s finite-family theorem for 𝒜 : Finset (Finset (Fin n)). The family is pairwise intersecting, every member has exactly r elements, and the hypothesis is exactly r ≤ n / 2. The selected declaration proves only #𝒜 ≤ (n−1).choose (r−1); it does not construct a star family, prove a separate sharpness result, or classify equality cases.
ProofAtlas did not originate the Erdős–Ko–Rado theorem or Mathlib’s declaration.
The selected declaration is not a theorem about arbitrary infinite set families.
It does not assert that all members share one common element.
It does not formalize an extremal construction or classify equality cases.
The generated explanation and visuals are not proof evidence.
