В комбинаторной математике теорема Бараньяи (доказанная и названная в честь Жолта Бараньяи ) имеет дело с разложениями полных гиперграфов .
Формулировка теоремы
Формулировка результата такова: если натуральные числа и r делит k , то полный гиперграф разлагается на 1-фактор .гиперграф с k вершинами, в котором каждое подмножество из r вершин образует гиперребро; 1-фактор этого гиперграфа - это множество гиперребер, которые касаются каждой вершины ровно один раз, или, что то же самое, разбиение вершин на подмножества размера r . Таким образом, теорема утверждает, что k вершин гиперграфа можно разбить на подмножества из r вершин вразличными способами, таким образом, чтобы каждое подмножество r- элементов появлялось ровно в одном из разделов.
Дело
В частном случае , у нас есть полный граф на вершин, и мы хотим покрасить края в цвета, так что края каждого цвета идеально сочетаются. Теорема Бараньяи гласит, что мы можем сделать это всякий раз, когда даже.
История
Г = 2 случай можно перефразировать как утверждение о том , что каждый полном графе с четным числом вершин имеет край окраску которого количество цветов равна его степень , или , что эквивалентно , что ее края могут быть разделены на совершенные паросочетания . Его можно использовать для планирования круговых турниров , и его решение было известно еще в 19 веке. Случай k = 2 r также прост.
Г = 3 случай , было установлено Р. Peltesohn в 1936 году общий случай был доказан Жолт Baranyai в 1975 году.
Рекомендации
- Бараняй, З. (1975), «О факторизации полного равномерного гиперграфа», в Hajnal, A .; Rado, R .; Сос, VT (ред.), Бесконечные и конечные множества, Proc. Coll. Кестхей, 1973 , Математический коллоквиум. Soc. Янош Бойяи, 10 , Северная Голландия, стр. 91–107..
- ван Линт, JH ; Уилсон, Р.М. (2001), Курс комбинаторики (2-е изд.), Cambridge University Press.
- Peltesohn, R. (1936), Das Turnierproblem für Spiele zu je dreien , Первая диссертация , Берлин.