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.

Notas

  1. ↑ Francisco Santos Leal en De Verdad, año XXX, número 28, julio de 2010, pág. 7.
  2. ↑ a b Ziegler (1994), p. 84.
  3. ↑ Dantzig (1963), pp. 160 and 168.
  4. ↑ E.g. see Naddef (1989) for 0-1 polytopes.
  5. ↑ Kalai y Kleitman (1992).
  6. ↑ a b Santos (2012).
  7. ↑ Kalai (2010).
  8. ↑ http://gaussianos.com/francisco-santos-encuentra-un-contraejemplo-que-refuta-la-conjetura-de-hirsch/
  9. ↑ a b Klee y Walkup (1967).

Referencias

  • Dantzig, George B. (1963), Linear Programming and Extensions, Princeton Univ. Press ..
  • Kalai, Gil (10 de mayo de 2010). «Francisco Santos Disproves the Hirsch Conjecture». Consultado el 11 de mayo de 2010. 
  • Kalai, Gil; Kleitman, Daniel J. (1992), «A quasi-polynomial bound for the diameter of graphs of polyhedra», Bulletin of the American Mathematical Society 26 (2): 315-316, doi:10.1090/S0273-0979-1992-00285-9, arΧiv:math/9204233, MR 1130448 ..
  • Klee, Victor; Walkup, David W. (1967), «The d-step conjecture for polyhedra of dimension d < 6», Acta Mathematica 133: 53-78, doi:10.1007/BF02395040, MR 0206823 ..
  • Naddef, Denis (1989), «The Hirsch conjecture is true for (0,1)-polytopes», Mathematical Programming 45 (1): 109-110, doi:10.1007/BF01589099, MR 1017214 ..
  • Santos, Francisco (2012), «A counter-example to the Hirsch conjecture», Annals of Math. (2) 176: 383-412., doi:10.4007/annals.2012.176.1.7 ..
  • Ziegler, Günter M. (1994), «The Hirsch Conjecture», Lectures on Polytopes, Graduate Texts in Mathematics 152, Springer-Verlag, pp. 83-93 ..

Véase también

Control de autoridades
  • Proyectos Wikimedia
  • Wd Datos: Q2993326
  • Wd Datos: Q2993326