Теорема Бараньяи

Теорема Бараньяи — теорема о разбиениях полных гиперграфов. Доказана Жолтом Бараньяи и названа его именем.

Формулировка

Если ${\displaystyle 2\leqslant r<k}$ являются натуральными числами и r делит k, то полный гиперграф ${\displaystyle K_{r}^{k}}$ можно разложить на 1-факторы.

Замечания

• ${\displaystyle K_{r}^{k}}$ — это гиперграф с k вершинами, в котором каждое подмножество из r вершин образует гиперребро.
• 1-фактор этого гиперграфа — это набор гиперрёбер, которые содержат каждую вершину в рёбрах ровно раз, что эквивалентно разбиению вершин на подмножества размера r.

Таким образом, теорема утверждает, что k вершин гиперграфа могут быть разбиты на подмножества r вершин ${\displaystyle {\binom {k}{r}}{\frac {r}{k}}={\binom {k-1}{r-1}}}$ различными способами таким образом, что каждое r-элементное подмножество появляется ровно раз в разбиении.

Случай ${\displaystyle r=2}$

В специальном случае ${\displaystyle r=2}$ мы имеем полный граф ${\displaystyle K_{n}}$ с ${\displaystyle n}$ вершинами и хотим раскрасить рёбра в ${\displaystyle {\binom {n}{2}}{\frac {2}{n}}=n-1}$ цветов так, что рёбра каждого цвета образуют совершенное паросочетание. Теорема Бараньяи утверждает, что мы можем это сделать, если ${\displaystyle n}$ чётно.

История

Случай r = 2 можно переформулировать как утверждение, что любой полный граф с чётным числом вершин имеет рёберную раскраску, число цветов которой равно его степени, или, эквивалентно, что рёбра могут быть разбиты на совершенные паросочетания. Это можно использовать для создания круговых турниров и решение было известно в 19-м веке. Случай k = 2r также прост.

Случай r = 3 рассмотрел в 1963 году Р. Пелтесон. Общий случай доказал в 1975 году Жолт Бараньяи.

Литература

Эта страница в последний раз была отредактирована 24 декабря 2021 в 07:08.