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.

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.

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.

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.

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.

A fixed \(k\)-set appears as a consecutive block in the same number of cyclic orderings.

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.

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