Satz von Baranyai

Der Satz von Baranyai ist ein mathematischer Satz aus dem Gebiet der Kombinatorik. Benannt ist er nach dem ungarischen Mathematiker Zsolt Baranyai, der den Satz 1973 bewies. Anschaulicher Ausgangspunkt der vom Satz behandelten Fragestellung ist das aus vielen Sportligen bekannte Rundenturnier. Dabei sollen mehrere Mannschaften an verschiedenen Spieltagen Spiele austragen, und zwar so, dass jede Mannschaft genau ein Spiel pro Spieltag hat und am Ende jede Mannschaft genau einmal gegen jede andere gespielt hat. Damit dies aufgehen kann, muss offensichtlich die Zahl aller Mannschaften gerade sein (andernfalls könnte nicht jede Mannschaft pro Spieltag genau ein Spiel austragen). Es ist jedoch keineswegs klar, dass dies bereits ausreicht um einen solchen Spielplan zu ermöglichen. Der einfachste Fall des Satzes von Baranyai besagt nun gerade, dass es tatsächlich möglich ist. Der Satz verallgemeinert die Aussage, indem er nicht nur den Fall behandelt, dass jeweils zwei Mannschaften aufeinander treffen sollen, sondern analoge Aussagen auch für Gruppen größerer Anzahlen macht, also beispielsweise ein Skatturnier, bei dem jede mögliche Dreiergruppe genau einmal zusammen spielen soll.

Ein vollständiger Graph wird in perfekte Matchings zerlegt. Dass dies möglich ist, ist der einfachste Fall des Satzes von Baranyai.

Aussage

Der Satz von Baranyai lässt sich auf verschiedene Weisen formulieren. Die graphentheoretische Formulierung lautet: Der vollständige Hypergraph $K_{n}^{m}$ besitzt genau dann eine 1-Faktorisierung, wenn $m$ ein Teiler von $n$ ist. Hier besteht $K_{n}^{m}$ aus $n$ Knoten, die durch Hyperkanten verbunden sind. Eine Hyperkante verbindet dabei $m$ Knoten, dass der Graph vollständig ist, bedeutet, dass alle möglichen Kanten in ihm vorkommen. Ein 1-Faktor ist eine Menge von Hyperkanten, sodass jeder Knoten von genau einer Kante berührt wird. Eine 1-Faktorisierung des Graphen ist eine disjunkte Zerlegung seiner Kanten in 1-Faktoren.

Die Aussage lässt sich damit allein mit Mengen umformulieren: Sei $A$ eine $n$ -elementige Menge. Gesucht sind $M$ Familien ${\mathcal {A}}_{1},\ldots ,{\mathcal {A}}_{M}$ von Teilmengen von $A$ , sodass gilt:

Die Elemente von ${\mathcal {A}}_{i}$ sind $m$ -elementige Teilmengen von $A$ , jede solche Teilmenge kommt in genau einem ${\mathcal {A}}_{i}$ vor.
Jedes ${\mathcal {A}}_{i}$ ist eine Partition von $A$ , die enthaltenen Mengen sind also disjunkt, ihre Vereinigung ist $A$ .

Der Satz von Baranyai besagt nun, dass solche Familien genau dann existieren, wenn $m$ ein Teiler von $n$ ist und $M={n-1 \choose m-1}$ gilt.

Beweis

Der Beweis für die eine Richtung der Äquivalenzaussage ist sehr leicht: Wenn solche Familien von Mengen existieren, dann müssen diese alle gleich viele Teilmengen enthalten, die Anzahl sei $k$ . Aus der Tatsache, dass es sich um Partitionen handelt, folgt $km=n$ , also ist $m$ ein Teiler von $n$ . Zusammen enthalten die Familien $kM$ Teilmengen. Es gibt ${n \choose m}$ $m$ -elementige Teilmengen von $A$ , folglich gilt $M={\frac {n \choose m}{k}}={\frac {m}{n}}{n \choose m}={n-1 \choose m-1}$ .

Für die andere, schwierigere Richtung gibt es verschiedene Beweise. Die meisten dieser Beweise zeigen eine verallgemeinerte Aussage, die zwar keine eigenständigen Anwendungen besitzt, aber einen Beweis mittels vollständiger Induktion über eine Variable erlaubt, die in der ursprünglichen Aussage nicht vorkommt. Besondere Verbreitung gefunden hat dabei die Idee von Andries Brouwer und Alexander Schrijver, die das Max-Flow-Min-Cut-Theorem zum Beweis des Induktionsschritts einsetzten.

Geschichte

Der Fall $m=2$ war bereits im 19. Jahrhundert bekannt. Den ersten Beweis für den Fall $m=3$ lieferte Rose Peltesohn 1936. Der allgemeine Fall war als sylvestersche Vermutung bekannt, bis Baranyai den Satz 1973 bewies. Veröffentlicht wurde sein Beweis zwei Jahre später. Inzwischen gibt es eine Reihe unterschiedlicher Beweise für den Satz sowie verschiedene Verallgemeinerungen.

Anwendungen

Aus einem konstruktiven Beweis des Satzes von Baranyai ließe sich tatsächlich ein Spielplan für ein Rundenturnier erstellen, allerdings sind auch wesentlich einfachere Konstruktionsmethoden bekannt. In der Realität gibt es zudem noch viele Nebenbedingungen, die eingehalten werden müssen, sodass Algorithmen aus der kombinatorischen Optimierung eingesetzt werden müssen.^[1]

Ebenfalls Anwendung findet der Satz in der Informationstheorie.^[2]

Eine innermathematische Anwendung findet der Satz bei der Bestimmung der Cliquenzahl von Kneser-Graphen.

Einzelnachweise

↑ Sigrid Knust: Construction methods for sports league schedules. Abgerufen am 11. Februar 2015.
↑ Ulrich Tamm: Applications of Baranyai’s Theorem in Information Theory. In: A. J. Han Vinck, Adriaan van Wijngaarden (Hrsg.): Proceedings of 6th Benelux-Japan Workshop on Coding and Information Theory. Essen, 1996. (online)

Literatur

Zsolt Baranyai: On the Factorization of the Complete Uniform Hypergraph. In: András Hajnal, Richard Rado, Vera T. Sós: Infinite and Finite Sets. Amsterdam, 1975. S. 91–108.
Andries Brouwer, Alexander Schrijver: Uniform Hypergraphs. In: Packing and Covering in Combinatorics. Mathematical Centre Tracts, No. 106, 1979. S. 39–73.
Dieter Jungnickel, Konrad Jacobs: Einführung in die Kombinatorik. de Gruyter, 2. Auflage 2004, ISBN 3-11-008736-7. 3.4: Der Satz von Baranyai.

Weblinks

Eric W. Weisstein: Baranyai’s Theorem. In: MathWorld (englisch).

[1] Sigrid Knust: Construction methods for sports league schedules. Abgerufen am 11. Februar 2015.

[2] Ulrich Tamm: Applications of Baranyai’s Theorem in Information Theory. In: A. J. Han Vinck, Adriaan van Wijngaarden (Hrsg.): Proceedings of 6th Benelux-Japan Workshop on Coding and Information Theory. Essen, 1996. (online)

[1]

[2]