Poster del Coloquio
Póster del Coloquio


Póster de los Coloquios del Centenario

Patrocinadores

Otros enlaces


La conjetura de Hirsch

Francisco Santos, Universidad de Cantabria

Lugar: Aula B5 de la Facultat de Matemàtiques, situada en la planta baja del Edificio Histórico de la Universitat de Barcelona [Gran Via 585, Barcelona]

Hora: 12:10

Resumen: La conjetura de Hirsch, enunciada en 1957, decía que en un poliedro (convexo y acotado) definido por n desigualdades lineales en d variables, es siempre posible viajar de un vértice a cualquier otro recorriendo a lo sumo n-d aristas. Dicho de otro modo, que el diámetro combinatorio de un poliedro con n facetas y dimensión d es a lo sumo n - d. En este coloquio hablaré de la historia y del contexto de la conjetura, así como del contraejemplo a la misma anunciado por mí en Mayo de 2010. Es importante señalar que no se conoce ninguna cota superior polinómica para ese diámetro que se conjeturaba lineal y que, en los contraejemplos existentes, lo sigue siendo.

Cuán grande puede llegar a ser el diámetro de un poliedro en función de los parámetros n y d es, además de una de las preguntas abiertas fundamentales de la combinatoria geométrica, relevante en el contexto del "método del símplice" para programación lineal. El método del símplice encuentra la solución óptima de un programa lineal moviéndose de vértice a vértice de un poliedro a través de sus aristas. Aunque no se conoce ninguna cota polinómica a la complejidad del método del símplice (porque no se conoce ninguna al diámetro combinatorio de un poliedro), experimentalmente se observa que el método normalmente encuentra el óptimo en un número lineal de pasos. De hecho, aunque existen otros métodos de programación lineal que sí que son polinómicos (elipsoide, puntos interiores), el método del símplice sigue siendo uno de los más usados en la práctica. Incluso desde el punto de vista teórico, el saber si el método del símplice puede encontrar el óptimo en un número polinómico de pasos tiene su relevancia: si así fuera, se tendría un algoritmo "fuertemente polinómico" para programación lineal, es decir, un método que es polinómico tanto en el modelo "bit" como en el modelo "máquina real". La existencia o no de un tal algoritmo fuertemente polinómico para programación lineal fue incluida por S. Smale en el año 2000 en su lista de "problemas matemáticos para el siglo XXI".

Transparencias

Fotos


Este coloquio es parte de las actividades que la Real Sociedad Matemática Española (RSME) tiene programadas para el año 2011, en el que se celebra su Centenario, y está organizado conjuntamente por la Facultad de Matemáticas y el IMUB de la Universidad de Barcelona.