*** Welcome to piglix ***

Erdős–Ko–Rado theorem


In combinatorics, the Erdős–Ko–Rado theorem of Paul Erdős, Chao Ko, and Richard Rado is a theorem on intersecting set families. It is part of the theory of hypergraphs, specifically, uniform hypergraphs of rank r.

The theorem is as follows. Suppose that A is a family of distinct subsets of such that each subset is of size r and each pair of subsets has a nonempty intersection, and suppose that n ≥ 2r. Then the number of sets in A is less than or equal to the binomial coefficient

A family of sets may also be called a hypergraph, and when all the sets are the same size it is called a uniform hypergraph. Since every set in A has size r, is an r-uniform hypergraph.


...
Wikipedia

...