Oberwolfach-Problem

Ungelöstes Problem aus der diskreten Mathematik

Das Oberwolfach-Problem ist ein Problem aus der diskreten Mathematik. Es wurde 1967 von Gerhard Ringel in einem Seminar zur Graphentheorie am Mathematischen Forschungsinstitut Oberwolfach formuliert. Motiviert durch die Platzierung von Konferenzteilnehmern an Esstischen stellt das Problem die Frage nach der Zerlegung eines Graphen in kantendisjunkte Kreise. Im Jahr 2021 wurde gezeigt, dass das Problem ab einer hinreichend großen Teilnehmerzahl bzw. Knotenzahl des Graphen immer lösbar ist. Allerdings ist offen, wie groß diese Zahl gewählt werden muss.

Motivation

Bearbeiten
 
Hauptgebäude des Mathe­matischen Forschungs­instituts Oberwolfach

Bei Konferenzen, die am Mathematischen Forschungsinstitut in Oberwolfach im Schwarzwald stattfinden, essen die Teilnehmer gemeinsam in einem Speisesaal an Tischen verschiedener Größe. Dabei werden ihnen feste Sitzplätze zugeordnet, die jedoch bei jedem Essen neu verteilt werden. Gerhard Ringel nutzte diese Tatsache 1967 auf einem Seminar zur Graphentheorie als Motivation für das Oberwolfach-Problem.[1]

Die Frage des Problems lautet, ob für eine gegebene Anzahl   von Teilnehmern und eine vorgegebene Menge von runden Tischen mit jeweils mindestens drei und insgesamt genau   Sitzplätzen eine Folge von Platzzuweisungen existiert, bei der jeder Teilnehmer der Konferenz genau einmal neben jedem anderen Teilnehmer speist. Berücksichtigt werden dabei nur die direkten Tischnachbarn, das heißt jeder Teilnehmer sitzt während eines Essens neben genau zwei anderen Teilnehmern. Daraus folgt direkt, dass es nur Lösungen geben kann, wenn die Anzahl der Teilnehmer ungerade ist. Bei einer geraden Teilnehmerzahl legt man deshalb für jeden Teilnehmer genau einen anderen Teilnehmer fest, neben dem er nicht sitzen darf bzw. nicht sitzen muss.

Eine Instanz des Oberwolfach-Problems kann mit   angegeben werden, wobei   natürliche Zahlen   sind und den Anzahlen der Plätze der   Tische entsprechen. Sind mehrere Tische derselben Größe vorhanden, wird oft eine Schreibweise mit Exponenten benutzt, das heißt   steht beispielsweise für die Instanz   und nicht für die Instanz  .

Mathematische Modellierung

Bearbeiten
 
Dekomposition des vollstän­digen Graphen   in drei Kopien des  , die durch unterschiedliche Farben der Kanten dargestellt werden. Dies ist eine Lösung der Oberwolfach-Instanz  .

Das Problem wird meist graphentheoretisch modelliert. Ein Graph ist ein mathematisches Objekt, das aus einer Menge von Knoten und einer Menge von Kanten besteht, wobei jede Kante jeweils zwei Knoten des Graphen verbindet. Die Knoten repräsentieren hier die Teilnehmer, eine Kante zwischen zwei Knoten steht für ein nebeneinander eingenommenes Essen. Die Sitzordnung an einem Tisch modelliert man mithilfe eines Kreisgraphen, ein zusammenhängender Graph bei dem jeder Knoten mit genau zwei anderen Knoten über eine Kante verbunden ist. Eine vollständige Sitzordnung an   Tischen mit den Größen   wird durch den Graph   repräsentiert, eine disjunkte Vereinigung von   Kreisgraphen mit der jeweiligen Knotenzahl  .

Für das Oberwolfach-Problem mit ungerader Teilnehmeranzahl   betrachtet man den vollständigen Graph  , das heißt den Graph mit   Knoten, die alle paarweise mit einer Kante verbunden sind. Die Frage lautet nun, ob dieser Graph sich als kantendisjunkte Vereinigung von Kopien von   darstellen lässt. Für gerade   betrachtet man dieselbe Frage für einen  , aus dem die Kanten eines 1-Faktors (auch perfektes Matching genannt) entfernt wurden.

Ergebnisse

Bearbeiten

Schon vor der Formulierung des Problems durch Gerhard Ringel wurden für einige Instanzen Lösungen gefunden. So wurde bereits 1850 das Problem der 15 Schulmädchen gelöst, bei dem 15 Mädchen sieben Tage hintereinander in Dreiergruppen spazieren gehen wollen, ohne dass zwei Mädchen mehr als einmal in derselben Gruppe spazieren müssen.[2] Das Problem ist äquivalent zur Instanz  

1883 stellte der französische Mathematiker Édouard Lucas im zweiten Band seiner Récréations mathématiques das „Problem der Runde“ (französisch problème de ronde) vor. Darin fragt er, ob man   Personen an   aufeinanderfolgenden Nächten so an einem Tisch platzieren kann, dass keiner zweimal neben derselben Person sitzen muss. Dies ist also der Spezialfall   für ungerade  . Lucas präsentierte in dem Buch auch einen Beweis für die Existenz solcher Lösungen für jedes ungerade  , den er einer Person namens Walecki zuschrieb.[3]

Bisher sind nur vier Instanzen des Oberwolfach-Problems bekannt, für die keine Lösung existiert. Dies sind  ,  ,   und  . Bis zu einer Teilnehmerzahl von   wurden für alle anderen Instanzen Lösungen gefunden.[4][5] Außerdem wurde für Zahlen, die gewisse Eigenschaften bezüglich ihrer Teilbarkeit erfüllen, die Existenz von Lösungen für jede mögliche Tischkonfiguration bewiesen.[6][7] 2021 konnten zwei Forschergruppen unabhängig voneinander zeigen, dass es eine natürliche Zahl   gibt, ab der für alle Teilnehmerzahlen   größer   jede Oberwolfach-Instanz   mit   lösbar ist.[8][9] Offen bleibt jedoch, wie klein diese Zahl   gewählt werden kann.

Daneben konnte gezeigt werden, dass, abgesehen von den genannten Negativfällen, alle Instanzen mit einer festen Tischgröße  [10][11] sowie alle Instanzen mit genau zwei Tischen  [12] gelöst werden können. Außerdem gibt es immer eine Lösung, wenn alle Tische eine gerade Anzahl von Plätzen haben.[13][14]

Bearbeiten

Einzelnachweise

Bearbeiten
  1. Hanfried Lenz, Gerhard Ringel: A brief review on Egmont Köhler's mathematical work. In: Discrete Mathematics. Band 97, Nr. 1–3, 1991, S. 3–16, doi:10.1016/0012-365X(91)90416-Y (englisch).
  2. Arthur Cayley: On the triadic arrangements of seven and fifteenthings. In: The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science. Band 37, Nr. 247, 1850, S. 50–53, doi:10.1080/14786445008646550 (englisch).
  3. Brian Alspach: The wonderful Walecki construction. In: Bulletin of the Institute of Combinatorics and its Applications. Band 52, 2008, S. 7–20 (englisch, researchgate.net).
  4. Antoine Deza, Frantisek Franek, William Hua, Mariusz Meszka, Alexander Rosa: Solutions to the Oberwolfach problem for orders 18 to 40. In: Journal of Combinatorial Mathematics and Combinatorial Computing. Band 74, 2010, S. 95–102 (englisch, mcmaster.ca [PDF; 152 kB]).
  5. Fabio Salassa, Gabriele Dragotto, Tommaso Traetta, Marco Buratti, Federico Della Croce: Merging Combinatorial Design and Optimization: the Oberwolfach Problem. In: Australasian Journal of Combinatorics. Band 79, Nr. 1, 2021, S. 141–166, arxiv:1903.12112 (englisch, edu.au [PDF; 444 kB]).
  6. Darryn Bryan, Victor Scharaschkin: Complete solutions to the Oberwolfach problem for an infinite set of orders. In: Journal of Combinatorial Theory, Series B. Band 99, Nr. 6, 2009, S. 904–918, doi:10.1016/j.jctb.2009.03.003 (englisch).
  7. Brian Alspach, Darryn Bryant, Daniel Horsle, Barbara Maenhaut, Victor Scharaschkin: On factorisations of complete graphs into circulant graphs and the Oberwolfach problem. In: Ars Mathematica Contemporanea. Band 11, Nr. 1, 2016, S. 157–173, doi:10.26493/1855-3974.770.150 (englisch).
  8. Peter Keevash, Katherine Staden: The generalised Oberwolfach problem. In: Journal of Combinatorial Theory, Series B. Band 152, 2021, S. 281–318, doi:10.1016/j.jctb.2021.09.007, arxiv:2004.09937 (englisch).
  9. Stefan Glock, Felix Joos, Jaehoon Kim, Daniela Kühn, Deryk Osthus: Resolution of the Oberwolfach problem. In: Journal of the European Mathematical Society. Band 23, Nr. 8, 2021, S. 2511–2547, doi:10.4171/JEMS/1060 (englisch).
  10. Brian Alspach, Paul J. Schellenberg, Doug Stinson, David Wagner: The Oberwolfach problem and factors of uniform odd length cycles. In: Journal of Combinatorial Theory, Series A. Band 52, Nr. 1, 1989, S. 20–43, doi:10.1016/0097-3165(89)90059-9 (englisch).
  11. Dean G. Hoffman, Paul J. Schellenberg: The existence of  -factorizations of  . In: Discrete Mathematics. Band 97, Nr. 1–3, 1991, S. 243–250, doi:10.1016/0012-365X(91)90440-D (englisch).
  12. Tommaso Traetta: A complete solution to the two-table Oberwolfach problems. In: Journal of Combinatorial Theory, Series A. Band 120, Nr. 5, 2013, S. 984–997, doi:10.1016/j.jcta.2013.01.003 (englisch).
  13. Roland Häggkvist: A lemma on cycle decompositions. In: Brian R. Alspach, Chris D. Godsil (Hrsg.): Cycles in graphs (= North-Holland Mathematics Studies. Band 115). North-Holland, Amsterdam 1985, S. 227–232, doi:10.1016/S0304-0208(08)73015-9 (englisch).
  14. Darryn Bryant, Peter Danziger: On bipartite 2-factorizations of   and the Oberwolfach problem. In: Journal of Graph Theory. Band 68, Nr. 1, 2011, S. 22–37, doi:10.1002/jgt.20538 (englisch, edu.au [PDF; 185 kB]).