Теорема Баранья - Baranyais theorem

Перегородка полный график на 8 вершинах в 7 цветов (идеальное соответствие ), случай р = 2 теоремы Бараньяи

В комбинаторный математика, Теорема Бараньяи (подтверждено и названо в честь Жолт Бараньяи ) касается разложения полного гиперграфы.

Формулировка теоремы

Формулировка результата такова: если ${\displaystyle 2\leq r<k}$ натуральные числа и р разделяет k, то полный гиперграф ${\displaystyle K_{r}^{k}}$ разлагается на 1-факторы. ${\displaystyle K_{r}^{k}}$ гиперграф с k вершин, в которых каждое подмножество р вершины образуют гиперребро; 1-фактор этого гиперграфа - это набор гиперребер, который касается каждой вершины ровно один раз, или, что эквивалентно раздел вершин на подмножества размерар. Таким образом, теорема утверждает, что k вершины гиперграфа можно разбить на подмножества р вершины в ${\displaystyle {\binom {k}{r}}{\frac {r}{k}}={\binom {k-1}{r-1}}}$ разными способами, таким образом, чтобы каждый рПодмножество -element появляется ровно в одном из разделов.

Дело ${\displaystyle r=2}$

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

История

В р = 2 case можно перефразировать как утверждающее, что каждый полный график с четным числом вершин имеет окраска края чье количество цветов равно его степень, или, что то же самое, его края можно разбить на идеальное соответствие. Его можно использовать для планирования круговые турниры, и его решение было известно уже в 19 веке. Дело, что k = 2р тоже легко.

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

Рекомендации

• Бараняй, З. (1975), «О факторизации полного равномерного гиперграфа», в Хайнал, А.; Радо, Р.; Сош, В. Т. (ред.), Бесконечные и конечные множества, Proc. Coll. Кестхей, 1973 г., Colloquia Math. Soc. Янош Бойяи, 10, Северная Голландия, стр. 91–107..
• ван Линт, Дж. Х.; Уилсон, Р.М. (2001), Курс комбинаторики (2-е изд.), Издательство Кембриджского университета.
• Пелтесон, Р. (1936), Das Turnierproblem für Spiele zu je dreien, Инаугурационная диссертация, Берлин.