Baranyai tétel

Baranyai tétele teljes hipergráfok partícióira vonatkozó tétel . Baranyai Zsolt által bebizonyított és róla elnevezett.

Megfogalmazás

Ha természetes számok és r osztja k -t , akkor a teljes hipergráf 1-tényezősre bontható . $2\leqslant r<k$ ${\displaystyle K_{r}^{k))$

Jegyzetek

${\displaystyle K_{r}^{k))$ egy k csúcsú hipergráf, amelyben az r csúcsok mindegyik részhalmaza egy hiperélt alkot.
Ennek a hipergráfnak az 1-tényezője a hiperélek halmaza, amelyek minden csúcsot pontosan egyszer tartalmaznak az élekben, ami egyenértékű a csúcsok r méretű részhalmazokra való felosztásával .

Így a tétel kimondja, hogy a hipergráf k csúcsa különféle módon particionálható r csúcsok részhalmazaira úgy , hogy minden r elemű részhalmaz pontosan egyszer jelenik meg a partícióban. ${\binom {k}{r}}{\frac {r}{k}}={\binom {k-1}{r-1}}$

Case $r=2$

Egy speciális esetben egy komplett gráfunk van csúcsokkal, és az éleket szeretnénk színekkel színezni úgy, hogy az egyes színek élei tökéletes illeszkedést alkossanak. Baranyai tétele kimondja, hogy ezt akkor tehetjük meg, ha páros. $r=2$ $K_n$ $n$ ${\binom {n}{2}}{\frac {2}{n}}=n-1$ $n$

Történelem

Az r = 2 eset újrafogalmazható úgy, hogy minden páros számú csúcsú teljes gráfnak van élszínezése , amelynek színeinek száma megegyezik annak mértékével , vagy ennek megfelelően az élek tökéletes illeszkedésre bonthatók . Ezzel körmérkőzéses versenyeket lehet létrehozni és a megoldást a XIX. A k = 2 r eset is egyszerű.

Az r = 3 esetet 1963-ban vizsgálta R. Pelteson. Az általános esetet 1975-ben Baranyai Zsolt bizonyította.

Irodalom

Baranyai Zsolt. A teljes egységes hipergráf faktorizálásáról // Infinite and Finite Sets, Proc. Coll. Keszthely, 1973 / András Hajnal, Richard Rado, Vera T. Sos. - Észak-Holland, 1975. - T. 10. - S. 91-107. - (Colloquia Math. Soc. Bolyai János). .
Jack van Lint, R. M. Wilson. Kombinatorika tanfolyam . — 2. – Cambridge University Press , 2001.
Peltesohn R. Das Turnierproblem für Spiele zu je dreien. - Berlin, 1936. - ( Beavató értekezés ).