Если <math>2\leqslant r<k</math> являются натуральными числами и r делит k, то полный гиперграф <math>K^k_r</math> можно разложить на 1-факторы.
Замечания
<math>K^k_r</math> — это гиперграф с k вершинами, в котором каждое подмножество из r вершин образует гиперребро.
1-фактор этого гиперграфа — это набор гиперрёбер, которые содержат каждую вершину в рёбрах ровно раз, что эквивалентно разбиению вершин на подмножества размера r.
Таким образом, теорема утверждает, что k вершин гиперграфа могут быть разбиты на подмножества r вершин <math>\binom{k}{r}\frac{r}{k} = \binom{k-1}{r-1}</math> различными способами таким образом, что каждое r-элементное подмножество появляется ровно раз в разбиении.
Случай <math>r = 2</math>
В специальном случае <math>r = 2</math> мы имеем полный граф <math>K_n</math> с <math>n</math> вершинами и хотим раскрасить рёбра в <math>\binom{n}{2}\frac{2}{n} = n-1 </math> цветов так, что рёбра каждого цвета образуют совершенное паросочетание. Теорема Бараньяи утверждает, что мы можем это сделать, если <math>n</math> чётно.
История
Случай r = 2 можно переформулировать как утверждение, что любой полный граф с чётным числом вершин имеет рёберную раскраску, число цветов которой равно его степени, или, эквивалентно, что рёбра могут быть разбиты на совершенные паросочетания. Это можно использовать для создания круговых турниров и решение было известно в 19-м веке. Случай k = 2r также прост.
Случай r = 3 рассмотрел в 1963 году Р. Пелтесон. Общий случай доказал в 1975 году Жолт Бараньяи.
