Satz von Baranyai

mathematischer Satz

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 Bearbeiten

Der Satz von Baranyai lässt sich auf verschiedene Weisen formulieren. Die graphentheoretische Formulierung lautet: Der vollständige Hypergraph   besitzt genau dann eine 1-Faktorisierung, wenn   ein Teiler von   ist. Hier besteht   aus   Knoten, die durch Hyperkanten verbunden sind. Eine Hyperkante verbindet dabei   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   eine  -elementige Menge. Gesucht sind   Familien   von Teilmengen von  , sodass gilt:

  • Die Elemente von   sind  -elementige Teilmengen von  , jede solche Teilmenge kommt in genau einem   vor.
  • Jedes   ist eine Partition von  , die enthaltenen Mengen sind also disjunkt, ihre Vereinigung ist  .

Der Satz von Baranyai besagt nun, dass solche Familien genau dann existieren, wenn   ein Teiler von   ist und   gilt.

Beweis Bearbeiten

Der Beweis für die eine Richtung der Äquivalenzaussage ist sehr leicht: Wenn solche Familien von Mengen existieren, dann müssen diese alle gleichviele Teilmengen enthalten, die Anzahl sei  . Aus der Tatsache, dass es sich um Partitionen handelt, folgt  , also ist   ein Teiler von  . Zusammen enthalten die Familien   Teilmengen. Es gibt    -elementige Teilmengen von  , folglich gilt  .

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 Bearbeiten

Der Fall   war bereits im 19. Jahrhundert bekannt. Den ersten Beweis für den Fall   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 Bearbeiten

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 Bearbeiten

  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)

Literatur Bearbeiten

  • 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 Bearbeiten