# Problème d'Oberwolfach

Le problème d'Oberwolfach, qui est un problème mathématique encore non résolu, est un problème d'attribution de places pour les convives d'un repas ; vu plus abstraitement, c'est un problème de théorie des graphes sur la couverture de graphes complets par des cycles. Il porte le nom de l' Institut de recherches mathématiques d'Oberwolfach, où le problème a été posé en 1967 par Gerhard Ringel. Le problème est résolu pour tous les graphes complets suffisamment grands.

## Formulation

Dans les conférences qui ont lieu à l'Institut de mathématiques d'Oberwolfach, il est de coutume que les participants dînent ensemble dans une salle autour de tables circulaires, pas toutes de la même taille, et avec des places attribuées qui mélangent les convives de repas en repas. Le problème d'Oberwolfach demande de proposer un plan de table pour un ensemble de tables donné de sorte que les tables soient pleines à chaque repas et que deux participants à la conférence soient assis l'un à côté de l'autre exactement une fois. Une instance de ce problème peut être notée par $OP(x,y,z,\dots )$ où $x,y,z,\dots$ sont les tailles de table données. Lorsque certaines tailles de table sont répétées, on peut aussi utiliser une notation exponentielle ; par exemple, $OP(5^{3})$ décrit une instance avec trois tables de taille cinq.
Formulé comme un problème en théorie des graphes, les personnes assises côte à côte lors d'un même repas sont représentées par des sommets d'une union disjointe de graphes cycliques $G=C_{x}+C_{y}+C_{z}+\cdots$ des longueurs spécifiées, avec un cycle pour chacune des tables. Cette union de cycles est un graphe 2-régulier, et tout graphe 2-régulier a cette forme. Si le graphe a $n$ sommets, la question est de savoir si le graphe complet $K_{n}$ de taille $n$ peut être représenté comme une union à arêtes disjointes de copies de $G$.
Pour qu'une solution existe, le nombre total de convives ou, de manière équivalente, la capacité totale des tables, ou encore le nombre total de sommets des graphes cycliques donnés, doit être un nombre impair. En effet, à chaque repas, un participant est assis à côté de deux voisins, donc le nombre total de voisins de chaque participant doit être pair, et cela n'est possible que lorsque le nombre total $n$ de participants est impair.
Le problème a également été étendu à des valeurs paires de $n$ en demandant si toutes les arêtes du graphe complet à l'exception d'un couplage parfait peuvent être couvertes par des copies du graphe 2-régulier donné. Comme le problème des ménages, cette variante du problème peut être formulée en supposant que le nombre $n$ les dîneurs soit disposés en $n/2$ couples mariés, et que la disposition des sièges place chaque convive exactement une fois l'un à côté d'un autre, à l'exception de leur propre conjoint.

## Résultats connus

Il n'y a pas de solution des problèmes d'Oberwolfach $OP(3^{2})$, $OP(3^{4})$, $OP(4,5)$, et $OP(3,3,5)$. Il est conjecturé que toutes les autres instances ont une solution. La conjecture est étayée par des solutions non constructives asymptotiques pour de grands graphes complets assez grands$^,$.
Les cas pour lesquels une solution constructive est connue incluent :
* Les occurrences $OP(x^{y})$ sauf $OP(3^{2})$ et $OP(3^{4})$$^,$$^,$$^,$$^,$
* Les instances dans lesquelles les cycles ont tous une longueur paire$^,$.
* Les instances (autres que les exceptions connues) avec $n\leq 60$$^,$.
* Les instances pour certains choix de $n$, dans des sous-ensembles infinis des nombres naturels$^,$.
* Les occurrences $OP(x,y)$ autre que $OP(3,3)$ et $OP(4,5)$.

## Problèmes voisins

Le problème des 15 écolières de Kirkman consiste à grouper quinze écolières en rangées de trois de sept manières différentes, afin que chaque paire de filles apparaisse une fois dans chaque triplet. C'est un cas particulier du problème d'Oberwolfach $OP(3^{5})$. Le problème de la décomposition hamiltonienne d'un graphe complet $K_{n}$ est un autre cas particulier, à savoir du cas $OP(n)$.
Le problème de ronde est décrit dans le deuxième volume de Récréations mathématiques d'Édouard Lucas datant de 1883. Il demande si l'on peut placer $2m+1$ personnes à une table pendant $m$ nuits consécutives de telle sorte que personne ne doive s'asseoir deux fois à côté de la même personne. C'est donc le cas particulier $OP(n)$ pour $n$ impair. Lucas a également présenté dans le livre une preuve de l'existence de telles solutions pour chaque $n$ impair, qu'il a attribuée à une personne appelée Walecki.
La conjecture d'Alspach (en) sur la décomposition d'un graphe complet en cycles de tailles données, est liée au problème d'Oberwolfach, mais ne sont des cas particuliers ni de l'un ni l'autre. Si $G$ est un graphe 2-régulier avec $n$ sommets qui est une union disjointe de cycles de certaines longueurs, une solution au problème d'Oberwolfach pour $G$ fournirait également une décomposition du graphe complet en $(n-1)/2$ copies de chacun des cycles de $G$. Cependant, toutes les décompositions de $K_{n}$ en ce nombre de cycles de chaque taille peuvent être regroupées en cycles disjoints qui forment des copies de $G$, et d'autre part toutes les instances de la conjecture d'Alspach n'impliquent pas des ensembles de cycles qui possèdent $(n-1)/2$ copies de chaque cycle.