Baranyais sats

Baranyais sats är en sats om partitioner av kompletta hypergrafer . Bevisad av Zsolt Baranyai och uppkallad efter honom.

Formulering

Om är naturliga tal och r delar k , så kan hela hypergrafen delas upp i 1-faktorer . $2\leqslant r<k$ ${\displaystyle K_{r}^{k))$

Anteckningar

${\displaystyle K_{r}^{k))$ är en hypergraf med k hörn, där varje delmängd av r hörn bildar en hyperkant.
1-faktorn för denna hypergraf är uppsättningen hyperkanter som innehåller varje vertex i kanterna exakt en gång, vilket motsvarar att dela upp hörnen i delmängder med storleken r .

Således säger satsen att k hörn i en hypergraf kan delas in i delmängder av r hörn på olika sätt så att varje r -element delmängd förekommer exakt en gång i partitionen. ${\binom {k}{r}}{\frac {r}{k}}={\binom {k-1}{r-1}}$

Fall $r=2$

I ett specialfall har vi en komplett graf med hörn och vi vill färga kanterna med färger så att kanterna på varje färg bildar en perfekt matchning. Baranyais teorem säger att vi kan göra detta om det är jämnt. $r=2$ $K_n$ $n$ ${\binom {n}{2}}{\frac {2}{n}}=n-1$ $n$

Historik

Fallet r = 2 kan omformuleras till att säga att varje komplett graf med ett jämnt antal hörn har en kantfärgning , vars antal färger är lika med dess grad , eller på motsvarande sätt att kanterna kan brytas upp till perfekta matchningar . Detta kan användas för att skapa round robin-turneringar och lösningen var känd på 1800-talet. Fallet k = 2 r är också enkelt.

Fallet r = 3 övervägdes 1963 av R. Pelteson. Det allmänna fallet bevisades 1975 av Zsolt Baranyai.

Litteratur

Zsolt Baranyai. Om faktoriseringen av den fullständiga enhetliga hypergrafen // Infinite and Finite Sets, Proc. Coll. 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. En kurs i kombinatorik . — 2:a. — Cambridge University Press , 2001.
Peltesohn R. Das Turnierproblem für Spiele zu je dreien. - Berlin, 1936. - ( Invigningsavhandling ).