En programación matemática y combinatoria poliédrica , la conjetura de Hirsch es la afirmación de que el gráfico borde - vértice de un politopo de n facetas en un espacio euclidiano de d dimensiones 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 expuesta por primera vez en una carta de Warren M. Hirsch a George B. Dantzig en 1957 [1] [2] y fue motivada por el análisis del método simplex en programación lineal , como 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 los límites superiores más conocidos del diámetro son sólo 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 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] Específicamente, el artículo presenta 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 simplex, ya que no descarta la posibilidad de un politopo más grande pero número de pasos todavía lineal o polinómico.
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 facetas d en el espacio euclidiano d -dimensional no es mayor que d ; El contraejemplo de Santos Leal también desmiente esta conjetura. [1] [9]
La gráfica de un politopo convexo es cualquier gráfica 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 una arista de la politopo. El diámetro de , denotado , es el diámetro de cualquiera de sus gráficas. Estas definiciones están bien definidas ya que dos gráficos cualesquiera del mismo politopo deben ser isomórficos como gráficos. Entonces podemos plantear la conjetura de Hirsch de la siguiente manera:
Conjetura Sea un politopo convexo d -dimensional con n facetas. Entonces .
Por ejemplo, un cubo en tres dimensiones tiene seis caras. 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 utilizando, 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 mediante un camino a lo largo de sus bordes. Dado que el método símplex esencialmente opera 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.
La conjetura de Hirsch es un caso especial de la conjetura polinómica de Hirsch , que afirma que existe algún número entero positivo k tal que, para todos los politopos , donde n es el número de facetas de P.
La conjetura de Hirsch ha demostrado ser 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 también satisfaga la conjetura. [10]
Otros intentos de resolver la conjetura se manifestaron por el 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:
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 se cumple para todos los politopos si y sólo si se cumple para todos los politopos simples . [10]
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 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 conjeturas de d -paso. [8] En particular, Santos produce su contraejemplo examinando una clase particular de politopos llamados husos .
Definición Un d -husillo es un d -politopo dimensional para el cual existe un par de vértices distintos de modo que cada faceta contiene exactamente uno de estos dos vértices.
La longitud del camino más corto entre estos dos vértices se llama longitud del huso. La refutación de la conjetura de Hirsch se basa en el siguiente teorema, denominado teorema del paso d fuerte para husillos .
Teorema (Santos) Sea un d -huso. 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 . En particular, si , entonces viola la conjetura del paso d .
Luego, Santos procede a construir un huso de 5 dimensiones con longitud 6, 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 en realidad refuta la conjetura tiene 86 facetas y tiene 43 dimensiones. Este contraejemplo no refuta la conjetura polinómica de Hirsch, que sigue siendo un problema abierto. [8]
