Теорема Бараньяи
Теорема Бараньяи — теорема о разбиениях полных гиперграфов. Доказана Жолтом Бараньяи и названа его именем.
Формулировка
Если являются натуральными числами и r делит k, то полный гиперграф можно разложить на 1-факторы.
Замечания
- — это гиперграф с k вершинами, в котором каждое подмножество из r вершин образует гиперребро.
- 1-фактор этого гиперграфа — это набор гиперрёбер, которые содержат каждую вершину в рёбрах ровно раз, что эквивалентно разбиению вершин на подмножества размера r.
Таким образом, теорема утверждает, что k вершин гиперграфа могут быть разбиты на подмножества r вершин различными способами таким образом, что каждое r-элементное подмножество появляется ровно раз в разбиении.
Случай
В специальном случае мы имеем полный граф с вершинами и хотим раскрасить рёбра в цветов так, что рёбра каждого цвета образуют совершенное паросочетание. Теорема Бараньяи утверждает, что мы можем это сделать, если чётно.
История
Случай r = 2 можно переформулировать как утверждение, что любой полный граф с чётным числом вершин имеет рёберную раскраску, число цветов которой равно его степени, или, эквивалентно, что рёбра могут быть разбиты на совершенные паросочетания. Это можно использовать для создания круговых турниров и решение было известно в 19-м веке. Случай k = 2r также прост.
Случай r = 3 рассмотрел в 1963 году Р. Пелтесон. Общий случай доказал в 1975 году Жолт Бараньяи.
Литература
- Zsolt Baranyai. On the factorization of the complete uniform hypergraph // Infinite and Finite Sets, Proc. Coll. Keszthely, 1973 / András Hajnal, Richard Rado, Vera T. Sós. — North-Holland, 1975. — Т. 10. — С. 91–107. — (Colloquia Math. Soc. János Bolyai)..
- Jack van Lint, R. M. Wilson. A Course in Combinatorics. — 2nd. — Cambridge University Press, 2001.
- Peltesohn R. Das Turnierproblem für Spiele zu je dreien. — Berlin, 1936. — (Inaugural dissertation).