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: v3 · 2026-09-19 · History
Domain-specific #: 1785
Domain group: Formal Sciences
Origin domain: Mathematics
Subdomains: Extremal Combinatorics, Intersection Theorems → Mathematics
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.

How would you explain it like I'm…

Teams That Always Share

Imagine making lots of little teams from a group of kids, and every two teams must share at least one kid. A math rule says how many teams you can make at most, as long as there are plenty of kids. One way to reach that most is to put the same kid on every team.

Everyone-Overlaps Team Limit

Say you have n kids and you form teams of exactly k kids each. The rule is that any two teams must have at least one kid in common. The Erdős–Ko–Rado Theorem says that if n is at least twice k, you can never have more teams than the number of teams that all contain one chosen kid. That 'everyone shares one kid' plan, called a star, actually reaches the limit. If there are too few kids (fewer than 2k), every two teams overlap anyway, so the rule stops being the useful limit.

Maximum Intersecting Families

A family of k-element subsets of {1,…,n} is called intersecting if every two sets in it share an element. The Erdős–Ko–Rado Theorem says that when n ≥ 2k, such a family has at most C(n−1, k−1) sets. A 'full star', meaning all k-sets containing one fixed element, reaches exactly this number, so the bound is sharp. When n > 2k, the stars are the only families that reach the maximum. At n = 2k, you can also reach it by taking one set from each pair of complementary sets. When n < 2k, any two k-sets overlap automatically, so the theorem doesn't apply.

Let F be a family of k-subsets of [n] such that A ∩ B ≠ ∅ for all A, B in F. The Erdős–Ko–Rado Theorem states that if n ≥ 2k, then |F| ≤ C(n−1, k−1). Equality is attained by the full star of all k-sets containing a fixed x, since the remaining k−1 elements are chosen freely from n−1. For n > 2k the extremal families are exactly the stars. At n = 2k the k-sets split into complementary pairs, and choosing one set from each pair also reaches the bound, so non-star extremal families exist. For n < 2k the whole of C([n], k) is intersecting, so the bound is irrelevant. The result is a model extremal argument: a local pairwise condition forces a global size bound, and an explicit construction shows the bound is sharp. Standard proofs use cyclic permutations, shifting, or spectral methods on Kneser graphs.

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) — outgoing typed relations

Erdős–Ko–Rado Theorem presupposes Intersection Prime

prime:intersection is the broader abstraction this entry instantiates by composition/presupposition.

Hierarchy path (1) — routes to 1 parentless root

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

Neighborhood in Abstraction Space¶

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

Family — Extremal Graph Theory & Bounds (7 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-25