![]() | ||
In combinatorial mathematics, Baranyai's theorem (proved by and named after Zsolt Baranyai) deals with the decompositions of complete hypergraphs.
Contents
Statement of the theorem
The statement of the result is that if
Special Case r = 2
In the special case r = 2, we have a complete graph Kn on n vertices, and we wish to color the edges with
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.