Baranyai's theorem

A partition of a complete graph into perfect matchings, the case r = 2 of Baranyai's theorem

In combinatorial mathematics, Baranyai's theorem (proved by and named after Zsolt Baranyai) deals with the decompositions of complete hypergraphs.

Statement of the theorem

The statement of the result is that if $2\le r are natural numbers and r divides k, then the complete hypergraph $K^k_r$ decomposes into 1-factors. $K^k_r$ is a hypergraph with k vertices, in which every subset of r vertices forms a hyperedge; a 1-factor of this hypergraph is a set of hyperedges that touches each vertex exactly once, or equivalently a partition of the vertices into subsets of size r. Thus, the theorem states that the k vertices of the hypergraph may be partitioned into subsets of r vertices in $\binom{k}{r}\frac{r}{k}$ different ways, in such a way that each r-element subset appears in exactly one of the partitions.

↑Jump back a section

History

The r = 2 case can be rephrased as stating that every complete graph with an even number of vertices has an edge coloring whose number of colors equals its degree, or equivalently that its edges may be partitioned into perfect matchings. It may be used to schedule round-robin tournaments, and its solution was already known in the 19th century. The case that k = 2r is also easy.

The r = 3 case was established by R. Peltesohn in 1936. The general case was proved by Zsolt Baranyai in 1975.

↑Jump back a section

References

↑Jump back a section