Baranyai-tétel

A Baranyai-tétel a hipergráfok teljes felbontására vonatkozó állítás a kombinatorikában.

A tétel azt állítja, hogy ha $2\leq r<k$ természetes számok és r osztja k-t, akkor a $K_{r}^{k}$ hipergráf felbomlik 1-faktorokra. Azaz, ha S egy k elemű halmaz és ${\mathcal {H}}$ az S összes r elemű részhalmazából álló rendszer, akkor ${\mathcal {H}}$ felbomlik (pontosabban particionálható), mint ${\mathcal {H}}={\mathcal {F}}_{1}\cup \cdots \cup {\mathcal {F}}_{n}$ ahol minden ${\mathcal {F}}_{i}$ rendszer az S halmaz egy partíciója.

Ez $r=2$-re már a 19. században ismert volt, az $r=3$ esetet R. Peltesohn 1936-ban igazolta. Az általános esetet 1975-ben bizonyította Baranyai Zsolt.

További információk

• Gyárfás András, Hraskó András: Teljes gráfok felbontásairól.Új matematikai mozaik, Typotex, Budapest, 2002.