Baranyais sætning

Baranyais sætning er en sætning om partitioner af komplette hypergrafer . Bevist af Zsolt Baranyai og opkaldt efter ham.

Ordlyd

Hvis er naturlige tal og r deler k , så kan hele hypergrafen dekomponeres i 1-faktorer . $2\leqslant r<k$ ${\displaystyle K_{r}^{k))$

Noter

${\displaystyle K_{r}^{k))$ er en hypergraf med k hjørner, hvor hver delmængde af r hjørner danner en hyperkant.
1-faktoren for denne hypergraf er sættet af hyperkanter, der indeholder hvert toppunkt i kanterne nøjagtigt én gang, hvilket svarer til at opdele hjørnerne i delmængder af størrelsen r .

Således siger sætningen, at k hjørner af en hypergraf kan opdeles i delmængder af r knudepunkter på forskellige måder, således at hver r -element delmængde optræder nøjagtigt én gang i partitionen. ${\binom {k}{r}}{\frac {r}{k}}={\binom {k-1}{r-1}}$

Sag $r=2$

I et særligt tilfælde har vi en komplet graf med hjørner, og vi ønsker at farve kanterne med farver, så kanterne på hver farve danner et perfekt match. Baranyais teorem siger, at vi kan gøre dette, hvis det er lige. $r=2$ $K_n$ $n$ ${\binom {n}{2}}{\frac {2}{n}}=n-1$ $n$

Historie

Tilfældet r = 2 kan omformuleres til at sige, at enhver komplet graf med et lige antal hjørner har en kantfarve , hvis antal farver er lig med dens grad , eller tilsvarende, at kanterne kan dekomponeres til perfekte matchninger . Dette kan bruges til at skabe round robin-turneringer, og løsningen var kendt i det 19. århundrede. Tilfældet k = 2 r er også enkelt.

Tilfældet r = 3 blev overvejet i 1963 af R. Pelteson. Den generelle sag blev bevist i 1975 af Zsolt Baranyai.

Litteratur

Zsolt Baranyai. Om faktoriseringen af den fuldstændige ensartede hypergraf // Infinite and Finite Sets, Proc. Saml. Keszthely, 1973 / András Hajnal, Richard Rado, Vera T. Sos. - Nord-Holland, 1975. - T. 10. - S. 91-107. - (Colloquia Math. Soc. Janos Bolyai). .
Jack van Lint, R.M. Wilson. Et kursus i kombinatorik . — 2. — Cambridge University Press , 2001.
Peltesohn R. Das Turnierproblem für Spiele zu je dreien. - Berlin, 1936. - ( Indvielsesdisputats ).