Conjecture de Hirsch

Cet article est une ébauche concernant la théorie des graphes.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

En mathématiques, et plus précisément en théorie de l'optimisation et en théorie des graphes, la conjecture de Hirsch affirme que le graphe des sommets et des arêtes d'un polytope de dimension d ayant n faces (de dimension d-1) a un diamètre ne dépassant pas n − d, c'est-à-dire que deux sommets du polytope peuvent toujours être reliés par un chemin formé d'au plus n − d arêtes. Cette conjecture apparut dans une lettre écrite par Warren M. Hirsch à George Dantzig en 1957[1],[2] ; elle était motivée par l'analyse de l'algorithme du simplexe (en programmation linéaire), car le diamètre d'un polytope est une borne inférieure du nombre d'étapes demandées par cet algorithme.

La conjecture de Hirsch fut démontrée pour d < 4 et pour de nombreux autres cas particuliers[3]. Cependant, les meilleures bornes supérieures connues montraient seulement que le diamètre des polytopes était une fonction sous-exponentielle de n et d[4]. Après plus de cinquante ans, un contre-exemple fut annoncé en mai 2010 par Francisco Santos (de l'université de Cantabrie)[5],[6],[7]. Ce résultat fut présenté lors de la conférence 100 Years in Seattle : the mathematics of Klee and Grünbaum. De nombreuses formes équivalentes de la conjecture étaient connues, comme la conjecture des d étapes, qui affirme que le diamètre d'un polytope de dimension d, ayant 2d faces, est au plus d[1],[8] ; cette conjecture était démontrée pour d < 6[8]. Là encore, un contre-exemple est à présent connu en dimension 43 (un polytope à 86 faces de diamètre > 43)[5]. Ces contre-exemples n'ont cependant pas d'incidence directe sur l'analyse de l'algorithme du simplexe, le nombre d'étapes de ce dernier pouvant rester linéaire, ou du moins polynomial.

Santos a reçu le prix Fulkerson en 2015 pour son contre-exemple[9].

Notes

  1. ↑ a et b Ziegler 1994, p. 84
  2. ↑ Dantzig 1998, p. 160 et 168
  3. ↑ Voir par exemple Naddef 1989 pour les 0-1 polytopes.
  4. ↑ Kalai et Kleitman 1992
  5. ↑ a et b Santos 2012
  6. ↑ Kalai 2010
  7. ↑ (es) Annonce de la découverte du contre-exemple
  8. ↑ a et b Klee et Walkup 1967
  9. ↑ « 2015 Fulkerson Prize Citation », sur Mathematical Optimization Society.

Références

  • (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Hirsch conjecture » (voir la liste des auteurs).
  • (en) George Dantzig, Linear Programming and Extensions, Princeton Univ. Press, coll. « Princeton Landmarks in Mathematics », , 11e éd. (1re éd. 1963), 627 p. (ISBN 978-0-691-05913-6, lire en ligne)
  • (en) Gil Kalai, « Francisco Santos Disproves the Hirsch Conjecture », sur gilkalai.wordpress.com,
  • (en) Gil Kalai et Daniel J. Kleitman, « A quasi-polynomial bound for the diameter of graphs of polyhedra », Bulletin of the American Mathematical Society, vol. 26, no 2,‎ , p. 315-316 (DOI 10.1090/S0273-0979-1992-00285-9), lien Math Reviews, arXiv:math/9204233
  • (en) Victor Klee et David W. Walkup, « The d-step conjecture for polyhedra of dimension d < 6 », Acta Mathematica, vol. 133,‎ , p. 53-78 (DOI 10.1007/BF02395040, MR 0206823)
  • (en) Denis Naddef, « The Hirsch conjecture is true for (0,1)-polytopes », Mathematical Programming, vol. 45, no 1,‎ , p. 109-110 (DOI 10.1007/BF01589099, MR 1017214)
  • (en) Francisco Santos, « A counterexample to the Hirsch conjecture », Annals of Mathematics, vol. 176, no 1,‎ , p. 383-412 (DOI 10.4007/annals.2012.176.1.7), arXiv:1006.2814
  • (en) Günter M. Ziegler, Lectures on Polytopes, Springer, coll. « GTM » (no 152), , « The Hirsch Conjecture », p. 83-93
  • icône décorative Portail de l'informatique théorique