Oberwolfach-Problem

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.

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 ${\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)}$.

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.

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] 2021 konnten zwei Forschergruppen unabhängig voneinander zeigen, dass es eine natürliche Zahl ${\displaystyle n_{0}}$ gibt, ab der für alle Teilnehmerzahlen ${\displaystyle n}$ größer ${\displaystyle n_{0}}$ jede Oberwolfach-Instanz ${\displaystyle OP(\ell _{1},\ldots ,\ell _{k})}$ mit ${\displaystyle \ell _{1}+\ldots +\ell _{k}=n}$ lösbar ist.^[8][9] Offen bleibt jedoch, wie klein diese Zahl ${\displaystyle n_{0}}$ gewählt werden kann.

Daneben konnte gezeigt werden, dass, abgesehen von den genannten Negativfällen, alle Instanzen mit einer festen Tischgröße ${\displaystyle OP(x^{y})}$^[10][11] sowie alle Instanzen mit genau zwei Tischen ${\displaystyle OP(x,y)}$^[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]

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

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 ${\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). 
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 ${\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]).