Twierdzenie Baranyai'a

Podział pełnego grafu na 8 wierzchołkach na 7 kolorów ( idealne dopasowania ), przypadek r = 2 twierdzenia Baranyai'a

W matematyce kombinatorycznej twierdzenie Baranyai (udowodnione i nazwane na cześć Zsolta Baranyai ) dotyczy rozkładów pełnych hipergrafów .

Stwierdzenie twierdzenia

Stwierdzenie wyniku jest takie, że jeśli są $r$ i dzieli k , to kompletny hipergraf $}$ r } ^ } na czynniki 1 . ${\ Displaystyle K_ {r} ^ {k}}$ jest hipergrafem z k wierzchołkami, w którym każdy podzbiór r wierzchołków tworzy hiperkrawędź; współczynnik 1 tego hipergrafu to zbiór hiperkrawędzi, który dotyka każdego wierzchołka dokładnie raz, lub równoważnie podział wierzchołków na podzbiory o rozmiarze r . Zatem twierdzenie stwierdza, że ​​k wierzchołków hipergrafu można podzielić na podzbiory r wierzchołków w ${\ Displaystyle {\ binom {k} {r}} \frac {r}{k}}={\binom {k-1}{r-1}}}$ na różne sposoby, w taki sposób, że każdy r -elementowy podzbiór występuje dokładnie w jednej z partycji.

Przypadek ${\ displaystyle r = 2}$

${\ Displaystyle {\ binom {n} {2}} {\ Frac {2} {n}} = n-1}$ szczególnym przypadku mamy pełny $na$ wierzchołkach $i$$pomocą$ krawędzie kolory tak, że krawędzie każdego koloru tworzą idealne dopasowanie. Twierdzenie Baranyai mówi, że możemy to zrobić, gdy $parzysta$ .

Historia

Przypadek r = 2 można przeformułować jako stwierdzający, że każdy pełny graf o parzystej liczbie wierzchołków ma kolorowanie krawędzi , którego liczba kolorów jest równa jego stopniowi , lub równoważnie, że jego krawędzie można podzielić na idealne dopasowania . Może służyć do planowania turniejów kołowych , a jego rozwiązanie znane było już w XIX wieku. Przypadek, że k = 2 r jest również łatwy.

Przypadek r = 3 został ustalony przez R. Peltesohna w 1936 r. Przypadek ogólny został udowodniony przez Zsolta Baranyai w 1975 r.

• Baranyai, Zs. (1975), "O faktoryzacji kompletnego jednolitego hipergrafu", w: Hajnal, A .; Rado R. ; Sós, VT (red.), Nieskończone i skończone zbiory, Proc. kol. Keszthely, 1973 , Colloquia Math. soc. János Bolyai, t. 10, Holandia Północna, s. 91–107 .
• van Lint, JH ; Wilson, RM (2001), Kurs kombinatoryki (wyd. 2), Cambridge University Press .
• Peltesohn, R. (1936), Das Turnierproblem für Spiele zu je dreien , Rozprawa inauguracyjna , Berlin .