Problème d'Oberwolfach

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 ${\displaystyle OP(x,y,z,\dots )}$ où ${\displaystyle 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, ${\displaystyle OP(5^{3})}$ décrit une instance avec trois tables de taille cinq^[1].

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 ${\displaystyle 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 ${\displaystyle n}$ sommets, la question est de savoir si le graphe complet ${\displaystyle K_{n}}$ de taille ${\displaystyle n}$ peut être représenté comme une union à arêtes disjointes de copies de ${\displaystyle G}$^[1].

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 ${\displaystyle n}$ de participants est impair.

Le problème a également été étendu à des valeurs paires de ${\displaystyle 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 ${\displaystyle n}$ les dîneurs soit disposés en ${\displaystyle 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^[2].

Il n'y a pas de solution des problèmes d'Oberwolfach ${\displaystyle OP(3^{2})}$, ${\displaystyle OP(3^{4})}$, ${\displaystyle OP(4,5)}$, et ${\displaystyle OP(3,3,5)}$^[3]. 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^[4],[5].

Les cas pour lesquels une solution constructive est connue incluent :

• Les occurrences ${\displaystyle OP(x^{y})}$ sauf ${\displaystyle OP(3^{2})}$ et ${\displaystyle OP(3^{4})}$^{[6],[7],[8],[9],[2]}
• Les instances dans lesquelles les cycles ont tous une longueur paire^[6],[10].
• Les instances (autres que les exceptions connues) avec ${\displaystyle n\leq 60}$^[11],[3].
• Les instances pour certains choix de ${\displaystyle n}$, dans des sous-ensembles infinis des nombres naturels^[12],[13].
• Les occurrences ${\displaystyle OP(x,y)}$ autre que ${\displaystyle OP(3,3)}$ et ${\displaystyle OP(4,5)}$^[14].