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.

Motivation

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.

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

Mathematische Modellierung

Dekomposition des vollstän­digen Graphen $K_7$ in drei Kopien des $C_3+C_4$, die durch unterschiedliche Farben der Kanten dargestellt werden. Dies ist eine Lösung der Oberwolfach-Instanz $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 $k$ Tischen mit den Größen $({\ell }_1,{\ell }_2,\dots ,{\ell }_k)$ wird durch den Graph $F=C_{{\ell }_1}+C_{{\ell }_2}+\dots +C_{{\ell }_k}$ repräsentiert, eine disjunkte Vereinigung von $k$ Kreisgraphen mit der jeweiligen Knotenzahl ${\ell }_i$.

Für das Oberwolfach-Problem mit ungerader Teilnehmeranzahl $n$ betrachtet man den vollständigen Graph $K_n$, das heißt den Graph mit $n$ Knoten, die alle paarweise mit einer Kante verbunden sind. Die Frage lautet nun, ob dieser Graph sich als kantendisjunkte Vereinigung von Kopien von $F$ darstellen lässt. Für gerade $n$ betrachtet man dieselbe Frage für einen $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. Das Problem ist äquivalent zur Instanz $OP(3^5).$

1883 stellte der französische Mathematiker Édouard Lucas im zweiten Band seiner Vorlage:Lang das „Problem der Runde“ (Vorlage:FrS) vor. Darin fragt er, ob man $2m+1$ Personen an $m$ aufeinanderfolgenden Nächten so an einem Tisch platzieren kann, dass keiner zweimal neben derselben Person sitzen muss. Dies ist also der Spezialfall $OP(n)$ für ungerade $n$. Lucas präsentierte in dem Buch auch einen Beweis für die Existenz solcher Lösungen für jedes ungerade $n$, den er einer Person namens Walecki zuschrieb.

Bisher sind nur vier Instanzen des Oberwolfach-Problems bekannt, für die keine Lösung existiert. Dies sind $OP(3^2)$, $OP(3^4)$, $OP(4,5)$ und $OP(3^2,5)$. Bis zu einer Teilnehmerzahl von $n=60$ wurden für alle anderen Instanzen Lösungen gefunden. 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. 2021 konnten zwei Forschergruppen unabhängig voneinander zeigen, dass es eine natürliche Zahl $n_0$ gibt, ab der für alle Teilnehmerzahlen $n$ größer $n_0$ jede Oberwolfach-Instanz $OP({\ell }_1,\dots ,{\ell }_k)$ mit ${\ell }_1+\dots +{\ell }_k=n$ lösbar ist. Offen bleibt jedoch, wie klein diese Zahl $n_0$ gewählt werden kann.

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

Weblinks

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