Oberwolfach-Problem

Das Oberwolfach-Problem i​st ein Problem a​us der diskreten Mathematik. Es w​urde 1967 v​on Gerhard Ringel i​n einem Seminar z​ur Graphentheorie a​m Mathematischen Forschungsinstitut Oberwolfach formuliert. Motiviert d​urch die Platzierung v​on Konferenzteilnehmern a​n Esstischen stellt d​as Problem d​ie Frage n​ach der Zerlegung e​ines Graphen i​n kantendisjunkte Kreise. Das Problem i​st offen, bisher wurden n​ur einige Spezialfälle gelöst.

Motivation

Hauptgebäude des Mathe­matischen Forschungs­instituts Oberwolfach

Bei Konferenzen, d​ie am Mathematischen Forschungsinstitut i​n Oberwolfach i​m Schwarzwald stattfinden, e​ssen die Teilnehmer gemeinsam i​n einem Speisesaal a​n Tischen verschiedener Größe. Dabei werden i​hnen feste Sitzplätze zugeordnet, d​ie jedoch b​ei jedem Essen n​eu verteilt werden. Gerhard Ringel nutzte d​iese Tatsache 1967 a​uf einem Seminar z​ur Graphentheorie a​ls Motivation für d​as Oberwolfach-Problem.[1]

Die Frage des Problems lautet, ob für eine gegebene Anzahl ${\displaystyle n}$ von Teilnehmern und eine vorgegebene Menge von runden Tischen mit jeweils mindestens drei und insgesamt genau ${\displaystyle n}$ 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 ${\displaystyle OP(\ell _{1},\ldots ,\ell _{k})}$ angegeben werden, wobei ${\displaystyle \ell _{1},\ldots ,\ell _{k}}$ natürliche Zahlen ${\displaystyle \geq 3}$ sind und den Anzahlen der Plätze der ${\displaystyle k}$ Tische entsprechen. Sind mehrere Tische derselben Größe vorhanden, wird oft eine Schreibweise mit Exponenten benutzt, das heißt ${\displaystyle OP(5^{3})}$ steht beispielsweise für die Instanz ${\displaystyle OP(5,5,5)}$ und nicht für die Instanz ${\displaystyle OP(125)}$.

Mathematische Modellierung

Dekomposition des vollstän­digen Graphen ${\displaystyle K_{7}}$ in drei Kopien des ${\displaystyle C_{3}+C_{4}}$, die durch unterschiedliche Farben der Kanten dargestellt werden. Dies ist eine Lösung der Oberwolfach-Instanz ${\displaystyle OP(3,4)}$.

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 ${\displaystyle k}$ Tischen mit den Größen ${\displaystyle (\ell _{1},\ell _{2},\ldots ,\ell _{k})}$ wird durch den Graph ${\displaystyle F=C_{\ell _{1}}+C_{\ell _{2}}+\ldots +C_{\ell _{k}}}$ repräsentiert, eine disjunkte Vereinigung von ${\displaystyle k}$ Kreisgraphen mit der jeweiligen Knotenzahl ${\displaystyle \ell _{i}}$.

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

Ergebnisse

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 ${\displaystyle OP(3^{5}).}$

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 ${\displaystyle 2m+1}$ Personen an ${\displaystyle m}$ aufeinanderfolgenden Nächten so an einem Tisch platzieren kann, dass keiner zweimal neben derselben Person sitzen muss. Dies ist also der Spezialfall ${\displaystyle OP(n)}$ für ungerade ${\displaystyle n}$. Lucas präsentierte in dem Buch auch einen Beweis für die Existenz solcher Lösungen für jedes ungerade ${\displaystyle n}$, 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 ${\displaystyle OP(3^{2})}$, ${\displaystyle OP(3^{4})}$, ${\displaystyle OP(4,5)}$ und ${\displaystyle OP(3^{2},5)}$. Bis zu einer Teilnehmerzahl von ${\displaystyle n=60}$ 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] Es gibt also unendlich viele Teilnehmerzahlen ${\displaystyle n}$, für die jede Oberwolfach-Instanz ${\displaystyle OP(\ell _{1},\ldots ,\ell _{k})}$ mit ${\displaystyle \ell _{1}+\ldots +\ell _{k}=n}$ lösbar ist.

Daneben konnte gezeigt werden, dass, abgesehen von den genannten Negativfällen, alle Instanzen mit einer festen Tischgröße ${\displaystyle OP(x^{y})}$[8][9] sowie alle Instanzen mit genau zwei Tischen ${\displaystyle OP(x,y)}$[10] gelöst werden können. Außerdem gibt es immer eine Lösung, wenn alle Tische eine gerade Anzahl von Plätzen haben.[11][12]

Weblinks

• Sarah Holliday: Sarah’s Oberwolfach Problem Page. Kennesaw State University.

Einzelnachweise

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. 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).
9. Dean G. Hoffman, Paul J. Schellenberg: The existence of ${\displaystyle C_{k}}$-factorizations of ${\displaystyle K_{2n}-F}$. In: Discrete Mathematics. Band 97, Nr. 1–3, 1991, S. 243–250, doi:10.1016/0012-365X(91)90440-D (englisch).
10. 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).
11. 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).
12. Darryn Bryant, Peter Danziger: On bipartite 2-factorizations of ${\displaystyle K_{n}-I}$ 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]).