Baranyais sats

En uppdelning av en komplett graf på 8 hörn i 7 färger ( perfekt matchning ), fallet r = 2 i Baranyais sats

I kombinatorisk matematik behandlar Baranyais sats (bevisad av och uppkallad efter Zsolt Baranyai ) uppdelningen av fullständiga hypergrafer .

Uttalande av satsen

Påståendet om resultatet är att om $2\leq r<k$ är heltal och r delar k , så bryts hela hypergrafen ${\displaystyle K_{r}^{k}} ner$ i 1-faktorer . $K_{r}^{k}$ är en hypergraf med k hörn, där varje delmängd av r hörn bildar en hyperkant; en 1-faktor för denna hypergraf är en uppsättning hyperkanter som berör varje vertex exakt en gång, eller motsvarande en uppdelning av hörnen i undergrupper av storleken r . Således anger satsen att hypergrafens k hörn kan delas upp i delmängder av r hörn i ${\binom {k}{r}}{ \frac {r}{k}}={\binom {k-1}{r-1}}$ olika sätt, på ett sådant sätt att varje delmängd r -element visas i exakt en av partitionerna.

Fallet $r=2$

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

Historia

Fallet r =2 kan omformuleras som 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 motsvarande att dess kanter kan delas upp i perfekta matchningar . Det kan användas för att schemalägga round-robin-turneringar , och dess lösning var känd redan på 1800-talet. Fallet att k = 2 r är också lätt.

Fallet r = 3 etablerades av R. Peltesohn 1936. Det allmänna fallet bevisades av Zsolt Baranyai 1975.

• Baranyai, Zs. (1975), "On the factorization of the complete uniform hypergraph", i Hajnal, A. ; Rado, R .; Sós, VT (red.), Infinite and Finite Sets, Proc. Coll. Keszthely, 1973 , Colloquia Math. Soc. János Bolyai, vol. 10, North-Holland, s. 91–107 .
• van Lint, JH ; Wilson, RM (2001), A Course in Combinatorics (2:a upplagan), Cambridge University Press .
• Peltesohn, R. (1936), Das Turnierproblem für Spiele zu je dreien , Inaugural dissertation , Berlin .