Teorema lui Baranyai

Teorema lui Baranyai este o teoremă asupra partițiilor de hipergrafe complete . Dovedit de Zsolt Baranyai și numit după el.

Formulare

Dacă sunt numere naturale și r împarte k , atunci hipergraful complet poate fi descompus în 1-factori . $2\leqslant r<k$ $K_{r}^{k)$

Note

$K_{r}^{k)$ este un hipergraf cu k vârfuri, în care fiecare submulțime de r vârfuri formează o hipermuchie.
Factorul 1 al acestui hipergraf este setul de hipermuchii care conțin fiecare vârf în muchii exact o dată, ceea ce este echivalent cu împărțirea vârfurilor în submulțimi de dimensiunea r .

Astfel, teorema afirmă că k vârfuri ale unui hipergraf pot fi împărțite în submulțimi de r vârfuri în diferite moduri, astfel încât fiecare submulțime de r -element să apară exact o dată în partiție. ${\binom {k}{r}}{\frac {r}{k}}={\binom {k-1}{r-1}}$

Caz $r=2$

Într-un caz special, avem un grafic complet cu vârfuri și dorim să colorăm marginile cu culori astfel încât marginile fiecărei culori să formeze o potrivire perfectă. Teorema lui Baranyai spune că putem face asta dacă este egal. $r=2$ $K_n$ $n$ ${\binom {n}{2}}{\frac {2}{n}}=n-1$ $n$

Istorie

Cazul r = 2 poate fi reformulat spunând că orice graf complet cu un număr par de vârfuri are o colorare a muchiilor , al cărei număr de culori este egal cu gradul său , sau, echivalent, că muchiile pot fi descompuse în potriviri perfecte . Acesta poate fi folosit pentru a crea turnee round robin, iar soluția era cunoscută în secolul al XIX-lea. Cazul k = 2 r este de asemenea simplu.

Cazul r = 3 a fost considerat în 1963 de R. Pelteson. Cazul general a fost dovedit în 1975 de Zsolt Baranyai.

Literatură

Zsolt Baranyai. Despre factorizarea hipergrafului uniform complet // Mulțimi infinite și finite, Proc. col. Keszthely, 1973 / András Hajnal, Richard Rado, Vera T. Sos. - Olanda de Nord, 1975. - T. 10. - S. 91-107. - (Colocvii Math. Soc. Janos Bolyai). .
Jack van Lint, R.M. Wilson. Un curs de combinatorică . — al 2-lea. — Cambridge University Press , 2001.
Peltesohn R. Das Turnierproblem für Spiele zu je dreien. - Berlin, 1936. - ( Disertație inaugurală ).