Conjetura de Hirsch

En programación matemática y combinatoria poliédrica , la conjetura de Hirsch es la afirmación de que el grafo arista - vértice de un politopo de n facetas en un espacio euclidiano de dimensión d tiene un diámetro no mayor que n  −  d . Es decir, dos vértices cualesquiera del politopo deben estar conectados entre sí por un camino de longitud como máximo n  −  d . La conjetura fue planteada por primera vez en una carta de Warren M. Hirsch  ^[es] a George B. Dantzig en 1957 ^{[1] [2]} y fue motivada por el análisis del método simplex en programación lineal , ya que el diámetro de un politopo proporciona un límite inferior en el número de pasos necesarios para el método simplex. Ahora se sabe que la conjetura es falsa en general.

La conjetura de Hirsch fue probada para d < 4 y para varios casos especiales, ^[3] mientras que las cotas superiores más conocidas sobre el diámetro son solo subexponenciales en n y d . ^[4] Después de más de cincuenta años, un contraejemplo fue anunciado en mayo de 2010 por Francisco Santos Leal , de la Universidad de Cantabria . ^{[5] [6] [7]} El resultado fue presentado en la conferencia 100 Years in Seattle: the mathematics of Klee and Grünbaum y apareció en Annals of Mathematics . ^[8] En concreto, el artículo presentó un politopo de 43 dimensiones de 86 facetas con un diámetro de más de 43. El contraejemplo no tiene consecuencias directas para el análisis del método símplex, ya que no descarta la posibilidad de un número de pasos mayor pero aún lineal o polinomial.

Se han dado varias formulaciones equivalentes del problema, como la conjetura de d -pasos, que establece que el diámetro de cualquier politopo de 2 d -caras en el espacio euclidiano de d -dimensionalidad no es mayor que d ; el contraejemplo de Santos Leal también refuta esta conjetura. ^{[1] [9]}

El grafo de un politopo convexo es cualquier grafo cuyos vértices están en biyección con los vértices de de tal manera que dos vértices cualesquiera del grafo están unidos por una arista si y solo si los dos vértices correspondientes de están unidos por una arista del politopo. El diámetro de , denotado , es el diámetro de cualquiera de sus grafos. Estas definiciones están bien definidas ya que dos grafos cualesquiera del mismo politopo deben ser isomorfos como grafos. Podemos entonces enunciar la conjetura de Hirsch de la siguiente manera: ${\estilo de visualización P}$${\estilo de visualización P}$${\estilo de visualización P}$${\estilo de visualización P}$${\displaystyle \delta (P)}$

Conjetura Sea un politopo convexo de dimensión d con n facetas. Entonces . ${\estilo de visualización P}$${\displaystyle \delta(P)\leq nd}$

Por ejemplo, un cubo en tres dimensiones tiene seis facetas. La conjetura de Hirsch indica entonces que el diámetro de este cubo no puede ser mayor que tres. Aceptar la conjetura implicaría que dos vértices cualesquiera del cubo pueden estar conectados por un camino de vértice a vértice usando, como máximo, tres pasos. Para todos los politopos de dimensión al menos 8, este límite es realmente óptimo; ningún politopo de dimensión tiene un diámetro menor que nd , siendo n el número de sus facetas, como antes. ^[10] En otras palabras, para casi todos los casos, la conjetura proporciona el número mínimo de pasos necesarios para unir dos vértices cualesquiera de un politopo por un camino a lo largo de sus bordes. Dado que el método símplex opera esencialmente construyendo un camino desde algún vértice de la región factible hasta un punto óptimo, la conjetura de Hirsch proporcionaría un límite inferior necesario para que el método símplex termine en el peor de los casos. ${\displaystyle d\geq 8}$

La conjetura de Hirsch es un caso especial de la conjetura polinómica de Hirsch , que afirma que existe algún entero positivo k tal que, para todos los politopos , , donde n es el número de facetas de P . ${\estilo de visualización P}$${\displaystyle \delta (P)=O(n^{k})}$

La conjetura de Hirsch se ha demostrado cierta en varios casos. Por ejemplo, cualquier politopo con dimensión 3 o inferior satisface la conjetura. Cualquier politopo d -dimensional con n facetas tal que cumpla con la conjetura también. ^[10]${\displaystyle nd\leq 6}$

Otros intentos de resolver la conjetura surgieron a partir del deseo de formular un problema diferente cuya solución implicaría la conjetura de Hirsch. Un ejemplo de particular importancia es la conjetura del paso d , una relajación de la conjetura de Hirsch que, de hecho, se ha demostrado que es equivalente a ella.

Teorema Las siguientes afirmaciones son equivalentes:

1. ${\displaystyle \delta(P)\leq nd}$para todos los politopos de dimensión d con n facetas.${\estilo de visualización P}$
2. ${\displaystyle \delta (P)\leq d}$para todos los politopos de dimensión d con facetas 2d .${\estilo de visualización P}$

En otras palabras, para probar o refutar la conjetura de Hirsch, sólo es necesario considerar politopos con exactamente el doble de facetas que su dimensión. Otra relajación significativa es que la conjetura de Hirsch es válida para todos los politopos si y sólo si es válida para todos los politopos simples . ^[10]

Desafortunadamente, la conjetura de Hirsch no es verdadera en todos los casos, como lo demostró Francisco Santos en 2011. La construcción explícita de un contraejemplo por parte de Santos proviene tanto del hecho de que la conjetura puede relajarse para considerar solo politopos simples, como de la equivalencia entre las conjeturas de Hirsch y d -step. ^[8] En particular, Santos produce su contraejemplo examinando una clase particular de politopos llamados husos .

Definición Un huso d es un politopo de dimensión d para el cual existe un par de vértices distintos tales que cada faceta de contiene exactamente uno de estos dos vértices. ${\estilo de visualización P}$${\estilo de visualización P}$

La longitud del camino más corto entre estos dos vértices se denomina longitud del huso. La refutación de la conjetura de Hirsch se basa en el siguiente teorema, conocido como el teorema fuerte del paso d para husos .

Teorema (Santos) Sea un huso d . Sea n el número de sus facetas y l su longitud. Entonces existe un huso, , con facetas y una longitud acotada inferiormente por . En particular, si , entonces viola la conjetura del paso d .${\estilo de visualización P}$${\estilo de visualización (nd)}$${\estilo de visualización P'}$${\estilo de visualización 2n-2d}$${\displaystyle l+n-2d}$$Estilo de visualización l>d$${\estilo de visualización P'}$

Santos procede entonces a construir un huso de cinco dimensiones con una longitud de seis, demostrando así que existe otro huso que sirve como contraejemplo de la conjetura de Hirsch. El primero de estos dos husos tiene 48 facetas y 322 vértices, mientras que el huso que realmente refuta la conjetura tiene 86 facetas y es de 43 dimensiones. Este contraejemplo no refuta la conjetura polinómica de Hirsch, que sigue siendo un problema abierto. ^[8]

• Dantzig, George B. (1963), Programación lineal y extensiones , Princeton Univ. Press. Reimpreso en la serie Princeton Landmarks in Mathematics , Princeton University Press, 1998.
• Kalai, Gil (10 de mayo de 2010). «Francisco Santos desmiente la conjetura de Hirsch» . Consultado el 11 de mayo de 2010 .
• Kalai, Gil ; Kleitman, Daniel J. (1992), "Un límite cuasi-polinomial para el diámetro de los gráficos de poliedros", Boletín de la Sociedad Matemática Americana , 26 (2): 315–316, arXiv : math/9204233 , doi :10.1090/S0273-0979-1992-00285-9, MR  1130448, S2CID  37821778.
• Klee, Victor ; Walkup, David W. (1967), "La conjetura del paso d para poliedros de dimensión d  < 6", Acta Mathematica , 133 : 53–78, doi : 10.1007/BF02395040 , MR  0206823.
• Miranda, Eva (2012), "La conjetura de Hirsch ha sido refutada: Una entrevista con Francisco Santos" (PDF) , Boletín de la Sociedad Matemática Europea (86): 31–36.
• Naddef, Denis (1989), "La conjetura de Hirsch es verdadera para los politopos (0,1)", Programación matemática , 45 (1): 109–110, doi :10.1007/BF01589099, MR  1017214, S2CID  24632864.
• Santos, Francisco (2011), "Un contraejemplo de la conjetura de Hirsch", Annals of Mathematics , 176 (1), Princeton University and Institute for Advanced Study: 383–412, arXiv : 1006.2814 , doi :10.4007/annals.2012.176.1.7, MR  2925387, S2CID  15325169
• Ziegler, Günter M. (1994), "La conjetura de Hirsch", Lectures on Polytopes , Textos de posgrado en matemáticas, vol. 152, Springer-Verlag, págs. 83-93.