Conjecture de Hirsch

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