Baranyai-tétel
Eszközök
Műveletek
Általános
Nyomtatás/exportálás
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 természetes számok és r osztja k-t, akkor a
hipergráf felbomlik 1-faktorokra. Azaz, ha S egy k elemű halmaz és
az S összes r elemű részhalmazából álló rendszer, akkor
felbomlik (pontosabban particionálható), mint
ahol minden
rendszer az S halmaz egy partíciója.
Ez -re már a 19. században ismert volt, az
esetet R. Peltesohn 1936-ban igazolta. Az általános esetet 1975-ben bizonyította Baranyai Zsolt.