Erdős–Ko–Rado Theorem¶

For n at least 2k, a pairwise-intersecting family of k-subsets of an n-element set has at most C(n-1,k-1) members, attained by every full star.

Version: v2 · 2026-09-06 · History
Domain-specific #: 1785
Origin domain: extremal combinatorics
Subdomain: intersection theorems
Aliases: EKR theorem

Core Idea¶

Let \([n]=\{1,\ldots,n\}\), and let \(\binom{[n]}{k}\) denote all \(k\)-element subsets of \([n]\). A family \(\mathcal F\subseteq\binom{[n]}{k}\) is intersecting when \(A\cap B\ne\varnothing\) for every \(A,B\in\mathcal F\). The Erdős–Ko–Rado theorem states that, if \(n\ge 2k\), then

\[ |\mathcal F|\le \binom{n-1}{k-1}. \]

The bound is attained by a full star: fix one element \(x\in[n]\) and take every \(k\)-set containing \(x\). There are \(\binom{n-1}{k-1}\) such sets because the other \(k-1\) elements are chosen freely from the remaining \(n-1\). Erdős, Ko, and Rado published the foundational intersection theorem in 1961.^[1]

The threshold and equality regime are essential. When \(n>2k\), every maximum family is a full star. At the boundary \(n=2k\), the numerical bound remains sharp but maximum families need not be stars: each \(k\)-set is paired with its complement, and choosing exactly one member from every complementary pair gives a maximum intersecting family. When \(n<2k\), every two \(k\)-sets intersect, so the entire \(\binom{[n]}{k}\) is allowed and the EKR bound is not the relevant maximum.

The theorem is a canonical extremal inference: a local pairwise-overlap condition forces a global bound on family size, and an explicit construction shows sharpness. Modern treatments connect it to cyclic-permutation counting, shifting, spectral methods, hypergraphs, and Kneser graphs.^[2]^[3]

Structural Signature¶

Finite ground set: a set \([n]\) of \(n\) distinguishable elements.
Uniform layer: every object is a distinct \(k\)-subset, not an arbitrary-size subset.
Pairwise intersection: no two selected members are disjoint.
Nontrivial range: \(n\ge 2k\), so disjoint \(k\)-sets are possible.
Extremal quantity: maximize \(|\mathcal F|\) under the intersection constraint.
Sharp star construction: all \(k\)-sets through one fixed element attain \(\binom{n-1}{k-1}\).
Equality boundary: star uniqueness holds for \(n>2k\), but not generally for \(n=2k\).
Equivalent graph model: \(\mathcal F\) is an independent set in the Kneser graph \(KG(n,k)\).

Recognition test. Verify uniform \(k\)-sets, pairwise nonempty intersection, and the parameter range before invoking the binomial bound. Then exhibit a star to certify sharpness and separate the equality statement for \(n>2k\) from the boundary case \(n=2k\).

What It Is Not¶

It is not the assertion that all sets share one common element. Pairwise intersection does not imply total intersection: \(\{1,2\},\{1,3\},\{2,3\}\) are pairwise intersecting but have empty common intersection. The theorem concludes that a maximum family is star-shaped only in the strict regime \(n>2k\); it does not insert a common element into every smaller intersecting family.

It is not a bound for arbitrary nonuniform families. If member sizes vary, antichain or hereditary-family hypotheses and different theorems may be needed. It is not Sperner’s theorem, which bounds an inclusion antichain rather than a pairwise-intersecting uniform family.

It is not the Erdős–Rado theorem from partition calculus, the Hilton–Milner theorem for large nontrivial intersecting families, or the Ahlswede–Khachatrian complete intersection theorem for \(t\)-intersection. Those results have different hypotheses or targets.

Scope of Application¶

The classical theorem belongs to extremal set theory. It applies directly to uniform hypergraphs whose edges are pairwise intersecting: it bounds the number of edges in an intersecting \(k\)-uniform hypergraph on \(n\) vertices. In Kneser-graph language, vertices are \(k\)-sets and disjoint pairs are adjacent, so the theorem computes

\[ \alpha(KG(n,k))=\binom{n-1}{k-1} \]

for \(n\ge 2k\).

EKR-type questions ask analogous maximum-intersecting-family questions for permutations, vector subspaces over finite fields, strings, signed sets, graph copies, and other homogeneous objects. Those analogues reuse the extremal schema but have their own threshold and equality theorems. They should not be quoted as automatic consequences of the classical set theorem.

The statement concerns finite sets and exact pairwise intersection. Variants can require \(|A\cap B|\ge t\), cross-intersection between different families, or stability near the extremal size. Each change can alter the extremal construction and range.

Clarity¶

Three cardinalities must remain distinct: \(n\) is the ground-set size, \(k\) is the common member size, and \(|\mathcal F|\) is the number of selected \(k\)-sets. The theorem bounds the third by a function of the first two. It does not bound \(|A\cap B|\) beyond requiring it to be at least one.

“Intersecting” is pairwise and includes comparing any two distinct family members. “Star” means all members contain one designated point; a full star contains every eligible \(k\)-set through that point. A subfamily of a star is intersecting but need not be maximum.

The inequality \(n\ge2k\) is not technical decoration. It is exactly the point at which disjoint \(k\)-sets can exist. Equality classification must also state whether \(n=2k\) or \(n>2k\); omitting the distinction produces a false uniqueness claim.

Manages Complexity¶

There are \(\binom nk\) possible \(k\)-sets and exponentially many possible families. Directly searching all families is infeasible even for modest parameters. The theorem replaces that search with one formula and one canonical construction.

It also converts a dense web of pairwise constraints into an extremal certificate. The upper bound proves that no clever dispersed construction beats a star, while the star proves the bound is attainable. In graph language, a difficult maximum-independent-set question on a highly symmetric graph receives a closed-form answer.

The theorem does not enumerate all intersecting families or measure their internal diversity. It manages only the maximum cardinality and, away from the boundary, the extremal shape. Stability and counting questions require stronger results.

Abstract Reasoning¶

Katona’s circle method supplies a compact proof schema. Arrange \([n]\) cyclically and consider the \(n\) intervals of length \(k\). When \(n\ge2k\), an intersecting selection of these cyclic intervals contains at most \(k\) members. Now average this local bound over all cyclic orderings.^[2]

A fixed \(k\)-set appears as a consecutive block in the same number of cyclic orderings. Double-counting pairs \((F,C)\), where \(F\in\mathcal F\) is consecutive in cyclic ordering \(C\), therefore compares the family’s total incidence with the at-most-\(k\)-per-ordering bound. Simplifying yields

\[ |\mathcal F|\le \frac{k}{n}\binom nk =\binom{n-1}{k-1}. \]

The identity follows from \(\binom nk=(n/k)\binom{n-1}{k-1}\). This proof exposes the mechanism: symmetry makes every \(k\)-set equally visible, while pairwise intersection limits how many can occupy one circular test configuration.

Knowledge Transfer¶

The EKR template transfers inside combinatorics: choose a homogeneous universe of objects, define incompatibility as disjointness or nonintersection, seek the largest compatible family, construct a point-stabilizer or star, and prove no larger family exists. Permutation and vector-space analogues preserve this workflow but not necessarily the same formula.

In graph theory, the transfer is exact for the classical theorem because Kneser-graph adjacency is defined by disjointness. An intersecting family is literally an independent vertex set. Hypergraph language is likewise a reformulation, not merely an analogy.

Outside combinatorics, “everyone overlaps with everyone else, so there must be a hub” is not a valid EKR transfer. Pairwise overlap alone does not ensure a common point, and the extremal conclusion depends on uniformity, symmetry, and the parameter range.

Examples¶

A star at \(n=5,k=2\). All pairs containing 1 form \(\{12,13,14,15\}\). The family is intersecting and has size \(4=\binom41\), so it is maximum. Because \(5>4\), every maximum family is a star.

Boundary nonuniqueness. For \(n=4,k=2\), the three pairs \(\{12,13,23\}\) form a triangle. They are pairwise intersecting, have size \(3=\binom31\), and are maximum, but no single element belongs to all three. This is why star uniqueness needs \(n>2k\).

Trivial range. For \(n=5,k=3\), any two 3-subsets intersect because their total size exceeds five. The entire family of ten triples is intersecting; applying the EKR bound \(\binom42=6\) would be wrong because \(n<2k\).

Kneser graph. In \(KG(5,2)\), vertices are the ten pairs and edges join disjoint pairs. The four pairs through one point form an independent set, and EKR says no independent set is larger.

Structural Tensions¶

Pairwise overlap versus common core: pairwise intersection can exist with empty total intersection. Diagnostic: compute the intersection of the whole family separately instead of inferring it from pairwise tests.
Sharp bound versus equality classification: attaining the number does not always imply a star. Diagnostic: distinguish \(n=2k\) from \(n>2k\) before naming all extremizers.
Uniformity versus apparent generality: mixed-size families may look similar but evade the theorem. Diagnostic: verify every member has cardinality exactly \(k\).
Nontrivial versus automatic intersection: below the threshold every pair already intersects. Diagnostic: check \(n\ge2k\) before using the EKR formula.
Classical theorem versus analogue: q-analogues and permutation results may have different exceptional cases. Diagnostic: identify the object universe and cite its own theorem rather than substituting the set formula.
Maximum size versus near-maximum structure: the theorem settles the optimum but not every large family. Diagnostic: use a stability or Hilton–Milner-type result when a non-star or near-extremal conclusion is required.

Structural–Framed Character¶

The theorem is highly structural: finite uniform sets, intersection, symmetry, and cardinality determine its content. Labels on the ground set do not matter. Relabeling preserves intersecting families, stars, and the bound.

Its framing is nevertheless mathematical and exact. “Intersection,” “uniform,” “star,” and “maximum” are not loose metaphors. Removing any one of the parameter, uniformity, or pairwise-condition obligations changes the problem.

Structural Core vs. Domain Accent¶

The portable core is an incompatibility-constrained extremal problem: local pairwise compatibility restricts global family size. The domain accent fixes finite \(k\)-subsets, disjointness, binomial enumeration, and the star construction.

The schema inspires many analogues, but the exact theorem does not recur literally across unrelated substrates. Its formula and equality cases belong to extremal combinatorics, so it is domain-specific rather than prime.

prime:intersection is the proposed minimal parent by composition/presupposition. Pairwise nonempty set intersection is the defining constraint from which the extremal question begins. Intersection alone supplies neither uniformity, the \(n\ge2k\) threshold, the binomial bound, nor star extremizers.

prime:cardinality is the measured output but not the structural genus. Generic Measure is more remote. Kneser graphs provide an equivalent representation, not a broader parent. No accepted theorem node exactly contains this statement.

Relationships to Other Abstractions¶

Current abstraction Erdős–Ko–Rado Theorem Domain-specific

Parents (1) — more general patterns this builds on

Erdős–Ko–Rado Theorem presupposes Intersection Prime

prime:intersection is the proposed minimal parent by composition/presupposition.

Hierarchy path (1) — routes to 1 parentless root

Erdős–Ko–Rado Theorem → Intersection → Set and Membership

Neighborhood in Abstraction Space¶

Erdős–Ko–Rado Theorem sits in a sparse region of the domain-specific corpus (81^st percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Set Measures & Geometric Nullity (11 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-09-08

Not to Be Confused With¶

Erdős–Rado theorem: an infinite-cardinal partition theorem.
Sperner’s theorem: a maximum-antichain result under set inclusion.
Hilton–Milner theorem: the maximum size of a nontrivial intersecting uniform family.
Complete intersection theorem: the general \(t\)-intersecting extremal result.
Helly’s theorem: conditions under which intersections of convex sets imply a total intersection.
Sunflower lemma: a statement about large set systems containing a common-core pattern.
Kneser’s conjecture/theorem: the chromatic number of Kneser graphs, not their independence number.

References¶

[1] Paul Erdős, Chao Ko, and Richard Rado, “Intersection Theorems for Systems of Finite Sets,” Quarterly Journal of Mathematics 12 (1961): 313–320, https://doi.org/10.1093/qmath/12.1.313; author archive, https://www.renyi.hu/~p_erdos/1961-07.pdf. registry ↩

[2] Peter Frankl and Norihide Tokushige, Extremal Problems for Finite Sets, Student Mathematical Library 86, American Mathematical Society, 2018, preview sections on the Erdős–Ko–Rado theorem and Katona’s circle method, https://www.ams.org/bookstore/pspdf/stml-86-prev.pdf. registry ↩a ↩b

[3] MIT OpenCourseWare 18.218, “Lectures 11–12: Erdős–Ko–Rado Type Theorem, the p-biased Cube, and Properties of Quasi-random Families,” https://ocw.mit.edu/courses/18-218-topics-in-combinatorics-analysis-of-boolean-functions-spring-2021/resources/mit18_218s21_lec11-12/. registry ↩