Baranyai tétele
A Wikipédiából, a szabad lexikonból.
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
természetes számok és r osztja k-t, akkor a
hipergráf felbomlik 1-faktorokra. Azaz, ha S egy k-elemű halmaz és H az S összes r elemű részhalmazából álló rendszer, akkor H felbomlik (pontosabban partícionálható), mint
ahol minden Fi 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.
[szerkesztés] Külső hivatkozás
- Gyárfás András, Hraskó András: Teljes gráfok felbontásairól.Új matematikai mozaik, Typotex, Budapest, 2002.


