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.