Problème d'Oberwolfach

Un article de Wikipédia, l'encyclopédie libre.

 

Décomposition du graphe complet en trois copies de  : une solution du problème d'Oberwolfach pour le couple de paramètres .

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[modifier | modifier le code]

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 où 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, 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 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 sommets, la question est de savoir si le graphe complet de taille peut être représenté comme une union à arêtes disjointes de copies de [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 de participants est impair.

Le problème a également été étendu à des valeurs paires de 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 les dîneurs soit disposés en 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[modifier | modifier le code]

Il n'y a pas de solution des problèmes d'Oberwolfach , , , et [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 sauf et [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 [11],[3].
  • Les instances pour certains choix de , dans des sous-ensembles infinis des nombres naturels[12],[13].
  • Les occurrences autre que et [14].

Problèmes voisins[modifier | modifier le code]

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 . Le problème de la décomposition hamiltonienne d'un graphe complet est un autre cas particulier, à savoir du cas [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 personnes à une table pendant 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 pour impair. Lucas a également présenté dans le livre une preuve de l'existence de telles solutions pour chaque 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 est un graphe 2-régulier avec sommets qui est une union disjointe de cycles de certaines longueurs, une solution au problème d'Oberwolfach pour fournirait également une décomposition du graphe complet en copies de chacun des cycles de . Cependant, toutes les décompositions de en ce nombre de cycles de chaque taille peuvent être regroupées en cycles disjoints qui forment des copies de , et d'autre part toutes les instances de la conjecture d'Alspach n'impliquent pas des ensembles de cycles qui possèdent copies de chaque cycle.

Références[modifier | modifier le code]

  1. ↑ a b et c Hanfried Lenz et Gerhard Ringel, « A brief review on Egmont Köhler's mathematical work », Discrete Mathematics, vol. 97, nos 1–3,‎ , p. 3–16 (DOI 10.1016/0012-365X(91)90416-Y Accès libre, MR 1140782)
  2. ↑ a et b Charlotte Huang, Anton Kotzig et Alexander Rosa, « On a variation of the Oberwolfach problem », Discrete Mathematics, vol. 27, no 3,‎ , p. 261–277 (DOI 10.1016/0012-365X(79)90162-6 Accès libre, MR 541472)
  3. ↑ a et b 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,‎ , 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, no 8,‎ , 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,‎ , p. 281–318 (DOI 10.1016/j.jctb.2021.09.007, MR 4332743, lire en ligne)
  6. ↑ a et b Roland Häggkvist, « A lemma on cycle decompositions », dans Cycles in graphs (Burnaby, B.C., 1982), Amsterdam, North-Holland, coll. « North-Holland Math. Stud. » (no 115), (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, no 1,‎ , 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, no 1,‎ , p. 20–43 (DOI 10.1016/0097-3165(89)90059-9 Accès libre, MR 1008157)
  9. ↑ D. G. Hoffman et P. J. Schellenberg, « The existence of -factorizations of  », Discrete Mathematics, vol. 97, nos 1–3,‎ , p. 243–250 (DOI 10.1016/0012-365X(91)90440-D Accès libre, MR 1140806)
  10. ↑ a et b Darryn Bryant et Peter Danziger, « On bipartite 2-factorizations of and the Oberwolfach problem », Journal of Graph Theory, vol. 68, no 1,‎ , 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,‎ , 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, no 6,‎ , p. 904–918 (DOI 10.1016/j.jctb.2009.03.003 Accès libre, 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, no 1,‎ , 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, no 5,‎ , p. 984–997 (DOI 10.1016/j.jcta.2013.01.003 Accès libre, MR 3033656)
  15. ↑ Brian Alspach, « The wonderful Walecki construction », Bulletin of the Institute of Combinatorics and its Applications, vol. 52,‎ , p. 7-20 (lire en ligne)

Voir aussi[modifier | modifier le code]

  • Tommaso Traetta, « A constructive solution to the Oberwolfach problem with a large cycle », Discrete Mathematics, vol. 347, no 5,‎ , article no 113947 (DOI 10.1016/j.disc.2024.113947, lire en ligne, consulté le )
Ce document provient de « https://fr.wikipedia.org/w/index.php?title=Problème_d%27Oberwolfach&oldid=213546296 ».