Teorema de Baranyai

De Viquipèdia
Jump to navigation Jump to search

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 ≤ 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-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 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]

  • 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.