Theorem

Erdos-Ko-Rado Theorem

Combinatorics and Graph Theory

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

Statement

The 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 Year

1961 1

Proved in 1938 by Erdos, Ko and Rado; not published until 1961, matching this atlas convention of recording the publication year (see Gauss-Bonnet Theorem, EntityId 288550).

Classification

Statement Form

Existence Theorem 1

Statement Form

Inequality 1

Connections

In Branch

Combinatorics

Proved By

Paul Erdos

Sources

1. Erdos-Ko-Rado Theorem (Wikipedia)

Wikimedia Foundation

lead 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.

Switch Atlas

The Inner World

The Civil World

The Natural World

Erdos-Ko-Rado Theorem

In Branch

Proved By