Problème d'Oberwolfach

 

Décomposition du graphe complet ${\displaystyle K_{7}}$ en trois copies de ${\displaystyle C_{3}+C_{4}}$ : une solution du problème d'Oberwolfach pour le couple de paramètres ${\displaystyle (3,4)}$.

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

Résultats connus

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].

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 ${\displaystyle OP(3^{5})}$. Le problème de la décomposition hamiltonienne d'un graphe complet ${\displaystyle K_{n}}$ est un autre cas particulier, à savoir du cas ${\displaystyle OP(n)}$[10].

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 ${\displaystyle 2m+1}$ personnes à une table pendant ${\displaystyle 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 ${\displaystyle OP(n)}$ pour ${\displaystyle n}$ impair. Lucas a également présenté dans le livre une preuve de l'existence de telles solutions pour chaque ${\displaystyle n}$ impair, qu'il a attribuée à une personne appelée Walecki[15].

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 ${\displaystyle G}$ est un graphe 2-régulier avec ${\displaystyle n}$ sommets qui est une union disjointe de cycles de certaines longueurs, une solution au problème d'Oberwolfach pour ${\displaystyle G}$ fournirait également une décomposition du graphe complet en ${\displaystyle (n-1)/2}$ copies de chacun des cycles de ${\displaystyle G}$. Cependant, toutes les décompositions de ${\displaystyle K_{n}}$ en ce nombre de cycles de chaque taille peuvent être regroupées en cycles disjoints qui forment des copies de ${\displaystyle G}$, et d'autre part toutes les instances de la conjecture d'Alspach n'impliquent pas des ensembles de cycles qui possèdent ${\displaystyle (n-1)/2}$ copies de chaque cycle.

Références

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Oberwolfach problem » (voir la liste des auteurs).

1. Hanfried Lenz et Gerhard Ringel, « A brief review on Egmont Köhler's mathematical work », Discrete Mathematics, vol. 97, n^os 1–3,‎ 1991, p. 3–16 (DOI 10.1016/0012-365X(91)90416-Y , MR 1140782)
2. Charlotte Huang, Anton Kotzig et Alexander Rosa, « On a variation of the Oberwolfach problem », Discrete Mathematics, vol. 27, n^o 3,‎ 1979, p. 261–277 (DOI 10.1016/0012-365X(79)90162-6 , MR 541472)
3. Fabio Salassa, Gabriele Dragotto, Tommaso Traetta, Marco Buratti et Federico Della Croce, « Merging Combinatorial Design and Optimization: the Oberwolfach Problem », Australas. J. Comb., vol. 79, Pat 1,‎ 2021, p. 141-166 (zbMATH 1465.05147, arXiv 1903.12112)
4. Stefan Glock, Felix Joos, Jaehoon Kim, Daniela Kühn et Deryk Osthus, « Resolution of the Oberwolfach problem », Journal of the European Mathematical Society, vol. 23, n^o 8,‎ 2021, p. 2511–2547 (DOI 10.4171/jems/1060, MR 4269420, arXiv 1806.04644)
5. Peter Keevash et Katherine Staden, « The generalised Oberwolfach problem », Journal of Combinatorial Theory B, vol. 152,‎ 2022, p. 281–318 (DOI 10.1016/j.jctb.2021.09.007, MR 4332743, lire en ligne)
6. Roland Häggkvist, « A lemma on cycle decompositions », dans Cycles in graphs (Burnaby, B.C., 1982), Amsterdam, North-Holland, coll. « North-Holland Math. Stud. » (n^o 115), 1985 (DOI 10.1016/S0304-0208(08)73015-9, MR 821524), p. 227–232
7. Brian Alspach et Roland Häggkvist, « Some observations on the Oberwolfach problem », Journal of Graph Theory, vol. 9, n^o 1,‎ 1985, p. 177–187 (DOI 10.1002/jgt.3190090114, MR 785659)
8. Brian Alspach, P. J. Schellenberg, Doug Stinson et David Wagner, « The Oberwolfach problem and factors of uniform odd length cycles », Journal of Combinatorial Theory A, vol. 52, n^o 1,‎ 1989, p. 20–43 (DOI 10.1016/0097-3165(89)90059-9 , MR 1008157)
9. D. G. Hoffman et P. J. Schellenberg, « The existence of ${\displaystyle C_{k}}$-factorizations of ${\displaystyle K_{2n}-F}$ », Discrete Mathematics, vol. 97, n^os 1–3,‎ 1991, p. 243–250 (DOI 10.1016/0012-365X(91)90440-D , MR 1140806)
10. Darryn Bryant et Peter Danziger, « On bipartite 2-factorizations of ${\displaystyle K_{n}-I}$ and the Oberwolfach problem », Journal of Graph Theory, vol. 68, n^o 1,‎ 2011, p. 22–37 (DOI 10.1002/jgt.20538, MR 2833961, lire en ligne)
11. A. Deza, F. Franek, W. Hua, M. Meszka et A. Rosa, « Solutions to the Oberwolfach problem for orders 18 to 40 », Journal of Combinatorial Mathematics and Combinatorial Computing, vol. 74,‎ 2010, p. 95–102 (MR 2675892, lire en ligne)
12. Darryn Bryant et Victor Scharaschkin, « Complete solutions to the Oberwolfach problem for an infinite set of orders », Journal of Combinatorial Theory B, vol. 99, n^o 6,‎ 2009, p. 904–918 (DOI 10.1016/j.jctb.2009.03.003 , MR 2558441)
13. Brian Alspach, Darryn Bryant, Daniel Horsley, Barbara Maenhaut et Victor Scharaschkin, « On factorisations of complete graphs into circulant graphs and the Oberwolfach problem », Ars Mathematica Contemporanea, vol. 11, n^o 1,‎ 2016, p. 157–173 (DOI 10.26493/1855-3974.770.150, MR 3546656, arXiv 1411.6047, lire en ligne)
14. Tommaso Traetta, « A complete solution to the two-table Oberwolfach problems », Journal of Combinatorial Theory A, vol. 120, n^o 5,‎ 2013, p. 984–997 (DOI 10.1016/j.jcta.2013.01.003 , MR 3033656)
15. Brian Alspach, « The wonderful Walecki construction », Bulletin of the Institute of Combinatorics and its Applications, vol. 52,‎ 2008, p. 7-20 (lire en ligne)

Voir aussi

• Tommaso Traetta, « A constructive solution to the Oberwolfach problem with a large cycle », Discrete Mathematics, vol. 347, n^o 5,‎ mai 2024, article n^o 113947 (DOI 10.1016/j.disc.2024.113947, lire en ligne, consulté le 21 mars 2024)