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 Statements Referenced by

Observed surface forms (1)

Surface form	Occurrences
Hilton–Milner theorem	1

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 NERFINISHED ⓘ Erdős–Ko–Rado-type theorems on hypergraphs NERFINISHED ⓘ Erdős–Ko–Rado-type theorems on permutations NERFINISHED ⓘ Erdős–Ko–Rado-type theorems on vector spaces NERFINISHED ⓘ Hilton–Milner theorem NERFINISHED ⓘ
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 NERFINISHED ⓘ Paul Erdős NERFINISHED ⓘ Richard Rado NERFINISHED ⓘ
originallyProvedBy	Chao Ko NERFINISHED ⓘ Paul Erdős NERFINISHED ⓘ Richard Rado NERFINISHED ⓘ
publishedIn	Journal of the London Mathematical Society NERFINISHED ⓘ
relatedTo	Sperner's theorem NERFINISHED ⓘ 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 NERFINISHED ⓘ 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 ⓘ

Referenced by (4)

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 ⓘ

this entity surface form: Hilton–Milner theorem