Baranyai-tétel

A Wikipédiából, a szabad enciklopédiából
(Baranyai tétele szócikkből átirányítva)

A kombinatorikában Baranyai tétele egy nevezetes, teljes hipergráfok felbontására vonatkozó állítás.

A tétel azt állítja, hogy ha 2\leq r<k természetes számok és r osztja k-t, akkor a K^k_r 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[szerkesztés | forrásszöveg szerkesztése]