Gives the exact maximum size of a family of k-element subsets of a larger set, drawn from a set large enough relative to k, in which every two subsets in the family share at least one common element. Proved by Paul Erdos, Chao Ko and Richard Rado, it is a foundational result of extremal set theory.
Facts
StatementThe Erdos-Ko-Rado theorem limits the number of sets in a family of sets for which every two sets have at least one element in common. 1 Proof YearProved in 1938 by Erdos, Ko and Rado; not published until 1961, matching this atlas convention of recording the publication year (see Gauss-Bonnet Theorem). Classification
Statement Form Statement Form Erdos-Ko-Rado Theorem
Filter Results1 entry
Connections
Has Statement Form
In Branch
Principal Result Of
Source Erdos-Ko-Rado Theorem (Wikipedia)
Source Richard Rado (Wikipedia)
Proved By
Sources
1. Erdos-Ko-Rado Theorem (Wikipedia)
Wikimedia Foundationlead paragraph, opening sentence
the Erdős-Ko-Rado theorem limits the number of sets in a family of sets for which every two sets have at least one element in common.
lead paragraph, sentence naming the proof and publication years
Paul Erdős, Chao Ko, and Richard Rado proved the theorem in 1938, but did not publish it until 1961.
Principal Result Of: Paul Erdos, Lead sentence of the article on the result
Paul Erdős, Chao Ko, and Richard Rado proved the theorem in 1938, but did not publish it until 1961.
In Group: Ramsey Theory and Extremal Combinatorics, Lead section
did not publish it until 1961. It is part of the field of combinatorics, and one of the central results of extremal set
View the Source Richard Rado (Wikipedia)
Principal Result Of: Richard Rado, ContributionsQuote, Principal Result Of: Richard Rado, Contributions
Rado published it with Erdős and Chao Ko in 1961
Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.