En programación matemática y combinatoria poliédrica , la conjetura de Hirsch es la afirmación de que el gráfico de borde - vértice de un politopo de n - facetas en el espacio euclidiano d - dimensional tiene un diámetro no mayor que n - d . Es decir, dos vértices cualesquiera del politopo deben estar conectados entre sí mediante una ruta de longitud como máximo n - d . La conjetura fue presentada por primera vez en una carta por Warren M. Hirsch [ es ] a George B. Dantzig en 1957 [1] [2] y fue motivado por el análisis del método simplex en la programación lineal , ya que el diámetro de un politopo proporciona un límite inferior en el número de pasos necesarios por 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 diversos casos especiales, [3] , mientras que los límites superiores más conocidos en el diámetro sólo son sub-exponencial de 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 se presentó en la conferencia 100 años en Seattle: las matemáticas de Klee y Grünbaum y apareció en Annals of Mathematics . [8] En concreto, el trabajo presentó un politopo de 43 dimensiones de 86 facetas con un diámetro superior a 43. El contraejemplo no tiene consecuencias directas para el análisis del método simplex, ya que no descarta la posibilidad de un mayor pero todavía lineal o polinomial número de pasos.
Se habían dado varias formulaciones equivalentes del problema, como la conjetura del paso d , que establece que el diámetro de cualquier politopo de 2 d- facetas en el espacio euclidiano d- dimensional no es mayor que d ; El contraejemplo de Santos Leal también refuta esta conjetura. [1] [9]
Declaración de la conjetura
La gráfica 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 gráfico estén unidos por una arista si y sólo si los dos vértices correspondientes de están unidos por un borde del politopo. El diametro de, denotado , es el diámetro de cualquiera de sus gráficos. Estas definiciones están bien definidas ya que dos gráficos del mismo politopo deben ser isomorfos como gráficos. Entonces podemos enunciar la conjetura de Hirsch de la siguiente manera:
Conjetura Letser un politopo convexo d -dimensional con n facetas. Luego.
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 de 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; sin politopo de dimensióntiene 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 mediante una ruta a lo largo de sus bordes. Dado que el método simplex 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 simplex termine en el peor de los casos.
La conjetura de Hirsch es un caso especial de la conjetura polinomial 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 .
Progreso y resultados intermedios
Se ha demostrado que la conjetura de Hirsch es cierta en varios casos. Por ejemplo, cualquier politopo con dimensión 3 o menor satisface la conjetura. Cualquier politopo d -dimensional con n facetas tales quetambién satisface la conjetura. [11]
Otros intentos de resolver la conjetura se manifestaron por un 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 en realidad se ha demostrado que es equivalente a ella.
Teorema Las siguientes afirmaciones son equivalentes:
- para todos los politopos d -dimensionalescon n facetas.
- para todos los politopos d -dimensionalescon 2d facetas.
En otras palabras, para probar o refutar la conjetura de Hirsch, solo es necesario considerar los 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 solo si es válida para todos los politopos simples . [12]
Contraejemplo
Desafortunadamente, la conjetura de Hirsch no es cierta en todos los casos, como lo demostró Francisco Santos en 2011. La construcción explícita de Santos de un contraejemplo proviene tanto del hecho de que la conjetura puede ser relajada para considerar solo politopos simples, como de la equivalencia entre el Hirsch y conjeturas de pasos d . [13] En particular, Santos produce su contraejemplo al examinar una clase particular de politopos llamados husos .
Definición Un d- husillo es un politopo d -dimensional para lo cual existen un par de vértices distintos de modo que cada faceta de contiene exactamente uno de estos dos vértices.
La longitud del camino más corto entre estos dos vértices se denomina longitud del eje. La refutación de la conjetura de Hirsch se basa en el siguiente teorema, conocido como el teorema fuerte del paso d para husillos .
Teorema (Santos) Seaser un eje d . Sea n el número de sus facetas y sea l su longitud. Entonces existe un-huso, , con facetas y una longitud limitada por debajo por . En particular, si, luego viola la conjetura d -step.
Santos luego procede a construir un eje de 5 dimensiones con una longitud de 6, lo que demuestra que existe otro eje que sirve como contraejemplo de la conjetura de Hirsch. El primero de estos dos ejes tiene 48 facetas y 322 vértices, mientras que el eje que en realidad refuta la conjetura tiene 86 facetas y es de 43 dimensiones. Este contraejemplo no refuta la conjetura polinomial de Hirsch, que sigue siendo un problema abierto. [14]
Notas
- ↑ a b Ziegler (1994) , p. 84.
- ^ Dantzig (1963) , págs. 160 y 168.
- ^ Por ejemplo, ver Naddef (1989) para politopos 0-1.
- ^ Kalai y Kleitman (1992) .
- ↑ Santos (2011) .
- ^ Kalai (2010) .
- ^ "Francisco Santos encuentra un contraejemplo que refuta la conjetura de Hirsch" , Gaussianos , 24 de mayo de 2010
- ↑ Santos (2011)
- ^ Klee y Walkup (1967) .
- ^ Ziegler (1994)
- ^ Ziegler (1994)
- ^ Ziegler (1994)
- ↑ Santos (2011)
- ↑ Santos (2011)
Referencias
- Dantzig, George B. (1963), Programación lineal y extensiones , Princeton Univ. prensa. Reimpreso en la serie Princetonmarks in Mathematics , Princeton University Press, 1998.
- Kalai, Gil (10 de mayo de 2010). "Francisco Santos refuta la conjetura de Hirsch" . Consultado el 11 de mayo de 2010 .
- Kalai, Gil ; Kleitman, Daniel J. (1992), "Un cuasi-polinomio ligado para el diámetro de las gráficas de poliedros", Boletín de la American Mathematical Society , 26 (2): 315–316, arXiv : math / 9204233 , doi : 10.1090 / S0273-0979-1992-00285-9 , MR 1.130.448 , 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) , Newsletter of the European Mathematical Society (86): 31–36.
- Naddef, Denis (1989), "La conjetura de Hirsch es cierta para (0,1) -politopos", 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 , Princeton University and Institute for Advanced Study, 176 (1): 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", Conferencias sobre politopos , Textos de posgrado en matemáticas, 152 , Springer-Verlag, págs. 83-93.