Erdős–Ko–Rado theorem

E554298

result in extremal combinatorics theorem

The Erdős–Ko–Rado theorem is a fundamental result in extremal combinatorics that determines the maximum size of a family of subsets of a finite set in which every pair of subsets has a non-empty intersection.

Try in SPARQL Jump to: Surface forms Disambiguation Statements Elicitation Referenced by

All labels observed (8)

Label	Occurrences
Erdős–Ko–Rado theorem canonical	4
Hilton–Milner theorem	2
Erdos–Ko–Rado theorem	1
Erdos–Ko–Rado type problems	1
Erdős–Ko–Rado type problems	1
Erdős–Ko–Rado-type theorems on hypergraphs	1
Erdős–Ko–Rado-type theorems on permutations	1
Erdős–Ko–Rado-type theorems on vector spaces	1

How this entity was disambiguated

This entity first appeared as the object of triple T5896705 — resolving that mention is where its identity was fixed. The disambiguator weighed these candidate entities and picked the highlighted one (or “None”, minting a new entity). This is how homonymy is resolved: the same surface form can point to different entities.

NED1 Entity disambiguation (via context triple) gpt-5-mini-2025-08-07

Target entity: Erdős–Ko–Rado theorem
Context triple: [Pál Erdős, knownFor, Erdős–Ko–Rado theorem]

A. Sperner family
A Sperner family is a collection of subsets of a finite set in which no subset is contained within another, central in extremal set theory and combinatorics.
B. Erdős–Szekeres theorem
The Erdős–Szekeres theorem is a fundamental result in combinatorial geometry that guarantees the existence of large convex polygons within sufficiently large sets of points in the plane in general position.
C. de Bruijn–Erdős theorem
The de Bruijn–Erdős theorem is a fundamental result in combinatorics and graph theory that relates finite and infinite structures, notably asserting that certain properties of infinite graphs or set systems are determined by their finite substructures.
D. Radon’s theorem
Radon’s theorem is a fundamental result in convex geometry stating that any set of sufficiently many points in Euclidean space can be partitioned into two disjoint subsets whose convex hulls intersect.
E. Helly’s theorem
Helly’s theorem is a fundamental result in convex geometry that gives conditions under which a family of convex sets in Euclidean space has a nonempty common intersection.
F. None of above. chosen
G. Unsure - the case is ambiguous/there is not enough information to decide.

NED2 Entity disambiguation (via description) gpt-5-mini-2025-08-07

Target entity: Erdős–Ko–Rado theorem
Target entity description: The Erdős–Ko–Rado theorem is a fundamental result in extremal combinatorics that determines the maximum size of a family of subsets of a finite set in which every pair of subsets has a non-empty intersection.

A. Sperner family
A Sperner family is a collection of subsets of a finite set in which no subset is contained within another, central in extremal set theory and combinatorics.
B. Erdős–Szekeres theorem
The Erdős–Szekeres theorem is a fundamental result in combinatorial geometry that guarantees the existence of large convex polygons within sufficiently large sets of points in the plane in general position.
C. de Bruijn–Erdős theorem
The de Bruijn–Erdős theorem is a fundamental result in combinatorics and graph theory that relates finite and infinite structures, notably asserting that certain properties of infinite graphs or set systems are determined by their finite substructures.
D. Radon’s theorem
Radon’s theorem is a fundamental result in convex geometry stating that any set of sufficiently many points in Euclidean space can be partitioned into two disjoint subsets whose convex hulls intersect.
E. Helly’s theorem
Helly’s theorem is a fundamental result in convex geometry that gives conditions under which a family of convex sets in Euclidean space has a nonempty common intersection.
F. None of above. chosen

Statements (47)

Predicate	Object
instanceOf	result in extremal combinatorics ⓘ theorem ⓘ
assumption	n ≥ 2k ⓘ
boundaryCase	for n = 2k, there exist non-star maximum intersecting families ⓘ
characterizes	maximum size of an intersecting family of k-subsets of [n] ⓘ
concerns	families of k-element subsets ⓘ intersecting families of sets ⓘ maximum size of intersecting families ⓘ
defines	intersecting family as a family of sets in which every pair of sets has non-empty intersection ⓘ
domain	finite sets ⓘ
field	combinatorics ⓘ extremal combinatorics ⓘ
hasApplication	coding theory ⓘ design theory ⓘ graph theory ⓘ probabilistic combinatorics ⓘ
hasGeneralization	Ahlswede–Khachatrian complete intersection theorem ⓘ Erdős–Ko–Rado-type theorems on hypergraphs ⓘ linked to: Erdős–Ko–Rado theorem Erdős–Ko–Rado-type theorems on permutations ⓘ linked to: Erdős–Ko–Rado theorem Erdős–Ko–Rado-type theorems on vector spaces ⓘ linked to: Erdős–Ko–Rado theorem Hilton–Milner theorem ⓘ linked to: Erdős–Ko–Rado theorem
hasProofMethod	algebraic methods ⓘ compression method ⓘ graph-theoretic methods ⓘ shifting technique ⓘ
implies	any intersecting family of k-subsets of [n] with n ≥ 2k has size at most C(n−1, k−1) ⓘ
maximumAttainedBy	family of all k-subsets containing a fixed element ⓘ
namedAfter	Chao Ko ⓘ Paul Erdős ⓘ linked to: Pál Erdős Richard Rado ⓘ
originallyProvedBy	Chao Ko ⓘ Paul Erdős ⓘ linked to: Pál Erdős Richard Rado ⓘ
publishedIn	Journal of the London Mathematical Society ⓘ
relatedTo	Sperner's theorem ⓘ linked to: Sperner family Turán-type extremal problems ⓘ intersection theorems ⓘ
statement	For n ≥ 2k, the largest size of an intersecting family of k-subsets of an n-element set is C(n−1, k−1). ⓘ
topic	extremal set theory ⓘ linked to: extremal combinatorics intersection properties of set families ⓘ
typicalExtremalFamily	star family of k-subsets containing a fixed element ⓘ
uniquenessCondition	for n > 2k, the only maximum intersecting families are stars ⓘ
usesConcept	binomial coefficients ⓘ intersecting set systems ⓘ k-uniform set systems ⓘ
yearProved	1938 ⓘ
yearPublished	1961 ⓘ

How these facts were elicited

Referenced by (12)

Full triples — surface form annotated when it differs from this entity's canonical label.

Pál Erdős → knownFor → Erdős–Ko–Rado theorem ⓘ

Szekeres–Lindström theorem → relationTo → Erdős–Ko–Rado theorem ⓘ

Szekeres–Lindström theorem → relatedTo → Erdős–Ko–Rado theorem ⓘ

Szekeres–Lindström theorem → relatedTo → Hilton–Milner theorem ⓘ