« Conjecture de Hirsch » : différence entre les versions
Nouvelle page : {{ébauche|théorie des graphes}} En mathématiques, et plus précisément en théorie de l'optimisation et en théorie des graphes, la ... |
(Aucune différence)
|
Version du 3 avril 2012 à 19:12
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 nfaces (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 Dantzigen 1957[1][2] ; elle était motivée par and was motivated 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]. Puis, après plus de cinquante ans, un contre-exemple fut annoncé en mai 2010 par Francisco Santos Leal (de l'université de Cantabrie)[5],[6],[7]. Ce résultat fur présenté lors de la conférence 100 Years in Seattle : the mathematics ofKlee 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 2dfaces 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 poluytope à 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.
Notes
- Ziegler 1994, p. 84.
- Dantzig 1963, pp. 160 and 168.
- Voir par exemple Naddef 1989 pour les 0-1 polytopes.
- Kalai et Kleitman 1992.
- Santos 2010.
- Kalai 2010.
- (es)Annonce (en espagnol) de la découvrte du contre-exemple
- Klee et Walkup 1967.
Références
- (en) George B. Dantzig, « Linear Programming and Extensions », {{Article}} : paramètre «
périodique» manquant, Princeton Univ. Press, . Reprinted in the series Princeton Landmarks in Mathematics, Princeton University Press, 1998. - (en) Gil Kalai, « Francisco Santos Disproves the Hirsch Conjecture »,
- (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, MR 1130448, 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, (sur arxiv)
- (en) Günter M. Ziegler, Lectures on Polytopes, vol. 152, Springer-Verlag, coll. « Graduate Texts in Mathematics », , 83–93 p..
