Conjetura de Hirsch

En optimización y en combinatoria poliédrica, la conjetura de Hirsch afirma que "si un poliedro está definido por n desigualdades lineales en d variables siempre ha de ser posible viajar de cualquier vértice a cualquier otro vértice recorriendo como mucho n-d aristas".[1] En términos un poco más técnicos, afirma que el grafo arista-vértice de un politopo de n-caras en un espacio euclidiano d-dimensional tiene un diámetro no mayor que n − d. Es decir, que cualquiera de dos vértices del politopo deben estar conectados el uno con el otro por una trayectoria de longitud n − d como máximo. La conjetura fue presentada primero en 1957 en una carta de Warren M. Hirsch a George B. Dantzig[2][3] y es motivada por el análisis del método simplex en programación lineal, a medida que el diámetro de un politopo proporciona un límite más bajo en el número de pasos necesarios por el método simplex.

La conjetura de Hirsch fue probada para d < 4 y para varios casos especiales,[4] los límites superiores más conocidos mostraron solamente que los politopos tienen un diámetro sub-exponencial en función de n y d.[5] sin embargo, 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.[6][7][8] el resultado debe ser presentado en la conferencia 100 Years in Seattle: The Mathematics of Klee and Grünbaum. Varias formulaciones equivalentes del problema habían sido dadas, por ejemplo la conjetura d-paso, que indica que el diámetro de cualquier politopo de 2d-caras en un espacio euclidiano d-dimensional no es mayor que d.[2][9] La conjetura de d-paso era conocida como verdadera para d < 6,[9] pero cuando fue encontrado un contraejemplo el caso general también fue refutado, usando un politopo 43-dimensional de 86 caras con un diámetro de más de 43.[6] El contraejemplo anunciado no tendría ninguna consecuencia directa para el análisis del método simplex, pues no eliminaría la posibilidad de un más grande pero todavía lineal o un número polinómico de pasos.