2 theorems

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

The theorem is as follows. If , and A is a family of distinct subsets of {1,2,...,n}, such that each subset is of size r (thus making A a uniform hypergraph of rank r), and each pair of subsets intersects, then the maximum number of sets that can be in A is given by the binomial coefficient

.

Baranyai's Theorem

If , then the complete -uniform hypergraph on vertices decomposes into 1-factors, where a 1-factor is a set of pairwise disjoint -sets. Brouwer and Schrijver (1979) give a beautiful proof using the maximum flow, minimum cut theorem of network flows.