Teorema de Baranyai

De Viquipèdia
Dreceres ràpides: navegació, cerca

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 | modifica el codi]

La l'enunciat del del teorema és que si 2 ≤ rk 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-elments 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 | modifica el codi]

El cas r = 2 ja era conegut al segle 19è.

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 | modifica el codi]

  • 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.
  • R. Peltesohn: Das Turnierproblem für Spiele zu je dreien, Inaugural dissertation, Berlin, 1936.