Teorema de Baranyai
En matemàtiques combinatòries el teorema de Baranyai tracta amb descomposicions de hipergrafs complets, va ser demostrat per Zsolt Baranyai.
Enunciat del teorema
[modifica]La l'enunciat del del teorema és que si 2 ≤ r < k són nombres naturals i r divideix k, llavors l'hipergraf complet Kkr es descompon en 1-factors. És a dir, si S és un conjunt de k-elements H consisteix en tots els subconjunts de r-elements de S, llavors
H es pot partir com H = F 1 ∪ ... ∪ F n on cada sistema F i és una partició de S.
Història
[modifica]El cas r = 2 ja era conegut al segle xixè.
El cas r = 3 va quedar establert per R. Peltesohn el 1936. El cas general el va demostrar Zsolt Baranyai el 1975.
Referències
[modifica]- Zs. Baranyai: On the factorization of the complete uniform hypergraph, in: Infinite and finite sets, Proc. Coll. Keszthely, 1973, (A. Hajnal, R. Rado and V.T. Sós, eds.), Colloquia Math. Soc. János Bolyai 10, North-Holland, 1975, 91–107.
- J. H. van Lint, R. M. Wilson: A Course in Combinatorics, 2a edició, Cambridge University Press, 2001.
- R. Peltesohn: Das Turnierproblem für Spiele zu je dreien, Inaugural dissertation, Berlin, 1936.