Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Programación lineal, método símplex, yconjetura de Hirsch
Francisco Santoshttp://personales.unican.es/santosf
Departamento de Matemáticas, Estadística y ComputaciónUniversidad de Cantabria, Spain
U Carlos III de Madrid — 24 de Enero de 2017
1
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Poliedros
Están entre los objetos geométricos de más antiguo estudio.
“las cinco figuras del divinoPlatón", Pappus, S. IV a.C.
2
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Poliedros
En dimensión 3 sabemos “casi todo”:Poliedros = descomposiciones celulares regulares de laesfera S2 = grafos planos 3-conexos (Steinitz 1905).Todo poliedro con n vértices tiene O(n) aristas y caras(Euler), y los posibles “f -vectores” (v ,a, c) están biencaracterizados.Hay 2Θ(n) poliedros con n vértices (Tutte ∼ 1960).Etc.
3
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Poliedros
En dimensión 3 sabemos “casi todo”:Poliedros = descomposiciones celulares regulares de laesfera S2 = grafos planos 3-conexos (Steinitz 1905).Todo poliedro con n vértices tiene O(n) aristas y caras(Euler), y los posibles “f -vectores” (v ,a, c) están biencaracterizados.Hay 2Θ(n) poliedros con n vértices (Tutte ∼ 1960).Etc.
3
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Poliedros
En dimensión 3 sabemos “casi todo”:Poliedros = descomposiciones celulares regulares de laesfera S2 = grafos planos 3-conexos (Steinitz 1905).Todo poliedro con n vértices tiene O(n) aristas y caras(Euler), y los posibles “f -vectores” (v ,a, c) están biencaracterizados.Hay 2Θ(n) poliedros con n vértices (Tutte ∼ 1960).Etc.
3
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Poliedros
En dimensión 3 sabemos “casi todo”:Poliedros = descomposiciones celulares regulares de laesfera S2 = grafos planos 3-conexos (Steinitz 1905).Todo poliedro con n vértices tiene O(n) aristas y caras(Euler), y los posibles “f -vectores” (v ,a, c) están biencaracterizados.Hay 2Θ(n) poliedros con n vértices (Tutte ∼ 1960).Etc.
3
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Poliedros
En dimensión 3 sabemos “casi todo”:Poliedros = descomposiciones celulares regulares de laesfera S2 = grafos planos 3-conexos (Steinitz 1905).Todo poliedro con n vértices tiene O(n) aristas y caras(Euler), y los posibles “f -vectores” (v ,a, c) están biencaracterizados.Hay 2Θ(n) poliedros con n vértices (Tutte ∼ 1960).Etc.
3
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Poliedros
En dimensión 4 o superior (politopos):Hay descomposiciones de la esfera Sd−1 en poliedrosgeodésicos que no son “politopales” (Barnette 1970).El número de politopos es 2Θ(n log n) en cualquierdimensión d ≥ 4 (Goodman-Pollack 1986), pero el númerode descomposiciones geodésicas de Sd es cercano a2Θ(nd/2) (Kalai 1988, Dey 1993, Nevo-S.-Wilson 2015+).Hay preguntas tan concretas como: ¿Hay algún 4-politopocon f -vector igual a (12,40,40,12)? (Contestadanegativamente por Brinkmann-Ziegler en Oct. de 2016).
4
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Poliedros
En dimensión 4 o superior (politopos):Hay descomposiciones de la esfera Sd−1 en poliedrosgeodésicos que no son “politopales” (Barnette 1970).El número de politopos es 2Θ(n log n) en cualquierdimensión d ≥ 4 (Goodman-Pollack 1986), pero el númerode descomposiciones geodésicas de Sd es cercano a2Θ(nd/2) (Kalai 1988, Dey 1993, Nevo-S.-Wilson 2015+).Hay preguntas tan concretas como: ¿Hay algún 4-politopocon f -vector igual a (12,40,40,12)? (Contestadanegativamente por Brinkmann-Ziegler en Oct. de 2016).
4
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Poliedros
En dimensión 4 o superior (politopos):Hay descomposiciones de la esfera Sd−1 en poliedrosgeodésicos que no son “politopales” (Barnette 1970).El número de politopos es 2Θ(n log n) en cualquierdimensión d ≥ 4 (Goodman-Pollack 1986), pero el númerode descomposiciones geodésicas de Sd es cercano a2Θ(nd/2) (Kalai 1988, Dey 1993, Nevo-S.-Wilson 2015+).Hay preguntas tan concretas como: ¿Hay algún 4-politopocon f -vector igual a (12,40,40,12)? (Contestadanegativamente por Brinkmann-Ziegler en Oct. de 2016).
4
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Poliedros
En dimensión 4 o superior (politopos):Hay descomposiciones de la esfera Sd−1 en poliedrosgeodésicos que no son “politopales” (Barnette 1970).El número de politopos es 2Θ(n log n) en cualquierdimensión d ≥ 4 (Goodman-Pollack 1986), pero el númerode descomposiciones geodésicas de Sd es cercano a2Θ(nd/2) (Kalai 1988, Dey 1993, Nevo-S.-Wilson 2015+).Hay preguntas tan concretas como: ¿Hay algún 4-politopocon f -vector igual a (12,40,40,12)? (Contestadanegativamente por Brinkmann-Ziegler en Oct. de 2016).
4
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Poliedros
En dimensión 4 o superior (politopos):Hay descomposiciones de la esfera Sd−1 en poliedrosgeodésicos que no son “politopales” (Barnette 1970).El número de politopos es 2Θ(n log n) en cualquierdimensión d ≥ 4 (Goodman-Pollack 1986), pero el númerode descomposiciones geodésicas de Sd es cercano a2Θ(nd/2) (Kalai 1988, Dey 1993, Nevo-S.-Wilson 2015+).Hay preguntas tan concretas como: ¿Hay algún 4-politopocon f -vector igual a (12,40,40,12)? (Contestadanegativamente por Brinkmann-Ziegler en Oct. de 2016).
4
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Poliedros
En dimensión 4 o superior (politopos):Hay descomposiciones de la esfera Sd−1 en poliedrosgeodésicos que no son “politopales” (Barnette 1970).El número de politopos es 2Θ(n log n) en cualquierdimensión d ≥ 4 (Goodman-Pollack 1986), pero el númerode descomposiciones geodésicas de Sd es cercano a2Θ(nd/2) (Kalai 1988, Dey 1993, Nevo-S.-Wilson 2015+).Hay preguntas tan concretas como: ¿Hay algún 4-politopocon f -vector igual a (12,40,40,12)? (Contestadanegativamente por Brinkmann-Ziegler en Oct. de 2016).
4
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Politopos
DefiniciónUn politopo (convexo) P es la envolvente convexa de unconjunto finito de puntos de Rd .
La dimensión de P es la dimensión de su cierre afín.
5
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Politopos
DefiniciónUn politopo (convexo) P es la envolvente convexa de unconjunto finito de puntos de Rd .
La dimensión de P es la dimensión de su cierre afín.
5
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Politopos
DefiniciónUn politopo (convexo) P es la envolvente convexa de unconjunto finito de puntos de Rd .
La dimensión de P es la dimensión de su cierre afín.
5
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Caras de P
Sea P un politopo. Una cara de P es un subconjunto ∂H ∩ P,donde
H = x ∈ Rd : a1x1 + · · · adxd ≤ a0
es un semiespacio afíín con P ⊂ H.
6
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Caras de P
Sea P un politopo. Una cara de P es un subconjunto ∂H ∩ P,donde
H = x ∈ Rd : a1x1 + · · · adxd ≤ a0
es un semiespacio afíín con P ⊂ H.
6
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Caras de P
La “cara vacía” de P.
7
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Caras de P
7
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Caras de P
Las caras de dimensión 0 se llaman vértices.
7
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Caras de P
Las caras de dimensión 1 se llaman aristas.
7
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Caras de P
Las de dimensión d − 1 (codimensión 1) se llaman facetas.
7
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
El grafo de un politopo
Los vértices y aristas de P forman un grafo (finito, no dirigido).
La distancia d(u, v) entre dos vértices u y v es la longitud(número de aristas) del camino más corto de u a v .
Por ejemplo, d(u, v) = 2.
8
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
El grafo de un politopo
Los vértices y aristas de P forman un grafo (finito, no dirigido).
La distancia d(u, v) entre dos vértices u y v es la longitud(número de aristas) del camino más corto de u a v .
Por ejemplo, d(u, v) = 2.
8
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
El grafo de un politopo
Los vértices y aristas de P forman un grafo (finito, no dirigido).
La distancia d(u, v) entre dos vértices u y v es la longitud(número de aristas) del camino más corto de u a v .
Por ejemplo, d(u, v) = 2.
8
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
El grafo de un politopo
Los vértices y aristas de P forman un grafo (finito, no dirigido).
El diámetro de G(P) (o de P) es la máxima distancia entre susvértices:
δ(P) := maxd(u, v) : u, v ∈ V.
8
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Conjetura de Hirsch
Denotemos por δ(P) el diámetro del grafo de un politopo P.
Conjectura: Warren M. Hirsch (1957)Para todo politopo P con n facetas y dimensión d , se tiene que
δ(P) ≤ n − d .
9
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Conjetura de Hirsch
Denotemos por δ(P) el diámetro del grafo de un politopo P.
Conjectura: Warren M. Hirsch (1957)Para todo politopo P con n facetas y dimensión d , se tiene que
δ(P) ≤ n − d .
9
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Conjetura de Hirsch
Denotemos por δ(P) el diámetro del grafo de un politopo P.
Conjectura: Warren M. Hirsch (1957)Para todo politopo P con n facetas y dimensión d , se tiene que
δ(P) ≤ n − d .
9
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Conjetura de Hirsch
Denotemos por δ(P) el diámetro del grafo de un politopo P.
Conjectura: Warren M. Hirsch (1957)Para todo politopo P con n facetas y dimensión d , se tiene que
δ(P) ≤ n − d .
Cincuenta y cinco años después. . .
9
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Conjetura de Hirsch
Denotemos por δ(P) el diámetro del grafo de un politopo P.
Conjectura: Warren M. Hirsch (1957)Para todo politopo P con n facetas y dimensión d , se tiene que
δ(P) ≤ n − d .
Cincuenta y cinco años después. . .
Teorema (S. 2012)Hay un politopo de dimensión 43 con 86 facetas y diámetro≥ 44.
9
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Conjetura de Hirsch
Denotemos por δ(P) el diámetro del grafo de un politopo P.
Conjectura: Warren M. Hirsch (1957)Para todo politopo P con n facetas y dimensión d , se tiene que
δ(P) ≤ n − d .
Cincuenta y cinco años después. . .
Teorema (S. 2012)Hay un politopo de dimensión 43 con 86 facetas y diámetro≥ 44.
CorolarioHay una familia infinita de politopos con diámetro ∼ (1 + ε)n,incluso en dimensión fija (mejor valor hasta ahora: ε = 1/20).
9
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Conjetura de Hirsch
Denotemos por δ(P) el diámetro del grafo de un politopo P.
Conjectura: Warren M. Hirsch (1957)Para todo politopo P con n facetas y dimensión d , se tiene que
δ(P) ≤ n − d .
Cincuenta y cinco años después. . .
Teorema (S. 2012)Hay un politopo de dimensión 43 con 86 facetas y diámetro≥ 44.
9
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Conjetura de Hirsch
Denotemos por δ(P) el diámetro del grafo de un politopo P.
Conjectura: Warren M. Hirsch (1957)Para todo politopo P con n facetas y dimensión d , se tiene que
δ(P) ≤ n − d .
Cincuenta y cinco años después. . .
Teorema (S. 2012)Hay un politopo de dimensión 43 con 86 facetas y diámetro≥ 44.
A día de hoy, no conocemos ninguna cota superior polinómicapara δ(P), en términos de n y d (“Conjetura de HirschPolinómica”)
9
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Una cota casi-polinómica, y una cota lineal endimensión fija
Teorema [Kalai-Kleitman 1992]Para todo d-politopo con n facetas:
δ(P) ≤ nlog2 d+2.
Teorema [Barnette 1967, Larman 1970]Para todo d-politopo con n facetas:
δ(P) ≤ n2d−3.
10
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Una cota casi-polinómica, y una cota lineal endimensión fija
Teorema [Kalai-Kleitman 1992]Para todo d-politopo con n facetas:
δ(P) ≤ nlog2 d+2.
Teorema [Barnette 1967, Larman 1970]Para todo d-politopo con n facetas:
δ(P) ≤ n2d−3.
10
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Una cota casi-polinómica, y una cota lineal endimensión fija
Teorema [Kalai-Kleitman 1992]Para todo d-politopo con n facetas:
δ(P) ≤ nlog2 d+2.
Teorema [Barnette 1967, Larman 1970]Para todo d-politopo con n facetas:
δ(P) ≤ n2d−3.
10
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Motivación: programación lineal
Un programa lineal es el problema de maximizar (o minimizar)una función lineal en una región definida por desigualdadeslineales. Es decir: encontrar maxc · x : x ∈ Rd ,Mx ≤ b paraunos c ∈ Rd ,b ∈ Rn y M ∈ Rd×n dados.
11
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Motivación: programación lineal
Un programa lineal es el problema de maximizar (o minimizar)una función lineal en una región definida por desigualdadeslineales. Es decir: encontrar maxc · x : x ∈ Rd ,Mx ≤ b paraunos c ∈ Rd ,b ∈ Rn y M ∈ Rd×n dados.
11
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Motivación: programación lineal
Un programa lineal es el problema de maximizar (o minimizar)una función lineal en una región definida por desigualdadeslineales. Es decir: encontrar maxc · x : x ∈ Rd ,Mx ≤ b paraunos c ∈ Rd ,b ∈ Rn y M ∈ Rd×n dados.
“If one would take statistics about whichmathematical problem is using up most of thecomputer time in the world, then (not includingdatabase handling problems like sorting and searching) theanswer would probably be linear programming.”
(László Lovász, 1980)
11
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Conexión con la Conjetura de Hirsch
El espacio factible P = x ∈ Rd : Mx ≤ b de un programalineal con n ecuaciones en d variables es un politopo(quizá no acotado) P con (a lo más) n facetas y ddimensiones.La solución óptima (si existe) se alcanza siempre en algúnvértice.El método del símplice [Dantzig 1947] resuelve elproblema comenzando en un vértice cualquiera ymoviéndose a través del grafo del politopo, de maneramonótona, hasta llegar al óptimo.En particular, la Conjetura de Hirsch está relacionada conla complejidad del caso peor del método del símplice.
12
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Conexión con la Conjetura de Hirsch
El espacio factible P = x ∈ Rd : Mx ≤ b de un programalineal con n ecuaciones en d variables es un politopo(quizá no acotado) P con (a lo más) n facetas y ddimensiones.La solución óptima (si existe) se alcanza siempre en algúnvértice.El método del símplice [Dantzig 1947] resuelve elproblema comenzando en un vértice cualquiera ymoviéndose a través del grafo del politopo, de maneramonótona, hasta llegar al óptimo.En particular, la Conjetura de Hirsch está relacionada conla complejidad del caso peor del método del símplice.
12
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Conexión con la Conjetura de Hirsch
El espacio factible P = x ∈ Rd : Mx ≤ b de un programalineal con n ecuaciones en d variables es un politopo(quizá no acotado) P con (a lo más) n facetas y ddimensiones.La solución óptima (si existe) se alcanza siempre en algúnvértice.El método del símplice [Dantzig 1947] resuelve elproblema comenzando en un vértice cualquiera ymoviéndose a través del grafo del politopo, de maneramonótona, hasta llegar al óptimo.En particular, la Conjetura de Hirsch está relacionada conla complejidad del caso peor del método del símplice.
12
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Conexión con la Conjetura de Hirsch
El espacio factible P = x ∈ Rd : Mx ≤ b de un programalineal con n ecuaciones en d variables es un politopo(quizá no acotado) P con (a lo más) n facetas y ddimensiones.La solución óptima (si existe) se alcanza siempre en algúnvértice.El método del símplice [Dantzig 1947] resuelve elproblema comenzando en un vértice cualquiera ymoviéndose a través del grafo del politopo, de maneramonótona, hasta llegar al óptimo.En particular, la Conjetura de Hirsch está relacionada conla complejidad del caso peor del método del símplice.
12
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Conexión con la Conjetura de Hirsch
El espacio factible P = x ∈ Rd : Mx ≤ b de un programalineal con n ecuaciones en d variables es un politopo(quizá no acotado) P con (a lo más) n facetas y ddimensiones.La solución óptima (si existe) se alcanza siempre en algúnvértice.El método del símplice [Dantzig 1947] resuelve elproblema comenzando en un vértice cualquiera ymoviéndose a través del grafo del politopo, de maneramonótona, hasta llegar al óptimo.En particular, la Conjetura de Hirsch está relacionada conla complejidad del caso peor del método del símplice.
12
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Complejidad de la programación lineal
Para casi todas las reglas de pivote diseñadas hasta lafecha se ha encontrado un análogo del cubo de Klee-Minty(1972), que hace que el método necesite un númeroexponencial de pasos:
13
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Complejidad de la programación lineal
Para casi todas las reglas de pivote diseñadas hasta lafecha se ha encontrado un análogo del cubo de Klee-Minty(1972), que hace que el método necesite un númeroexponencial de pasos:
13
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Complejidad de la programación lineal
Para casi todas las reglas de pivote diseñadas hasta lafecha se ha encontrado un análogo del cubo de Klee-Minty(1972), que hace que el método necesite un númeroexponencial de pasos:
13
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Complejidad de la programación lineal
Para casi todas las reglas de pivote diseñadas hasta lafecha se ha encontrado un análogo del cubo de Klee-Minty(1972), que hace que el método necesite un númeroexponencial de pasos:
13
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Complejidad de la programación lineal
Para casi todas las reglas de pivote diseñadas hasta lafecha se ha encontrado un análogo del cubo de Klee-Minty(1972), que hace que el método necesite un númeroexponencial de pasos:
13
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Complejidad de la programación lineal
Para casi todas las reglas de pivote diseñadas hasta lafecha se ha encontrado un análogo del cubo de Klee-Minty(1972), que hace que el método necesite un númeroexponencial de pasos:
13
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Complejidad de la programación lineal
Para casi todas las reglas de pivote diseñadas hasta lafecha se ha encontrado un análogo del cubo de Klee-Minty(1972), que hace que el método necesite un númeroexponencial de pasos:
13
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Complejidad de la programación lineal
Para casi todas las reglas de pivote diseñadas hasta lafecha se ha encontrado un análogo del cubo de Klee-Minty(1972), que hace que el método necesite un númeroexponencial de pasos:
13
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Complejidad de la programación lineal
Para casi todas las reglas de pivote diseñadas hasta lafecha se ha encontrado un análogo del cubo de Klee-Minty(1972), que hace que el método necesite un númeroexponencial de pasos:
13
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Complejidad de la programación lineal
Para casi todas las reglas de pivote diseñadas hasta lafecha se ha encontrado un análogo del cubo de Klee-Minty(1972), que hace que el método necesite un númeroexponencial de pasos:
13
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Complejidad de la programación lineal
Para casi todas las reglas de pivote diseñadas hasta lafecha se ha encontrado un análogo del cubo de Klee-Minty(1972), que hace que el método necesite un númeroexponencial de pasos:
13
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Complejidad de la programación lineal
Para casi todas las reglas de pivote diseñadas hasta lafecha se ha encontrado un análogo del cubo de Klee-Minty(1972), que hace que el método necesite un númeroexponencial de pasos:
13
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Complejidad de la programación lineal
Para casi todas las reglas de pivote diseñadas hasta lafecha se ha encontrado un análogo del cubo de Klee-Minty(1972), que hace que el método necesite un númeroexponencial de pasos:
13
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Complejidad de la programación lineal
Hay métodos de programación lineal más recientes que sí sonpolinómicos: elipsoide (Khachiyan 1979), puntos interiores(Karmarkar 1984). Pero:
14
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Complejidad de la programación lineal
Hay métodos de programación lineal más recientes que sí sonpolinómicos: elipsoide (Khachiyan 1979), puntos interiores(Karmarkar 1984). Pero:
14
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Complejidad de la programación lineal
Hay métodos de programación lineal más recientes que sí sonpolinómicos: elipsoide (Khachiyan 1979), puntos interiores(Karmarkar 1984). Pero:
The number of pivot steps [that the simplex methodtakes] to solve a problem with m equality constraints inn nonnegative variables is almost always at most asmall multiple of m, say 3m.
(M. Todd, 2011)
14
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Complejidad de la programación lineal
Hay métodos de programación lineal más recientes que sí sonpolinómicos: elipsoide (Khachiyan 1979), puntos interiores(Karmarkar 1984). Pero:
The number of pivot steps [that the simplex methodtakes] to solve a problem with m equality constraints inn nonnegative variables is almost always at most asmall multiple of m, say 3m.
The simplex method has remained, if not the methodof choice, a method of choice, usually competitivewith, and on some classes of problems superior to, themore modern approaches.
(M. Todd, 2011)
14
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Complejidad de la programación lineal
Hay métodos de programación lineal más recientes que sí sonpolinómicos: elipsoide (Khachiyan 1979), puntos interiores(Karmarkar 1984). Pero:
el método simplex fue elegido como uno de los “10algoritmos con mayor influencia en e desarrollo y lapráctica de la ciencia y la ingeniería del siglo 20" en lalista confeccionada por la revista Computing inScience and Engineering en el año 2000.
14
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Complejidad de la programación lineal
Además, los algoritmos polinómicos de programación linealque se conocen no son fuertemente polinómicos: Sonpolinómicos en el modelo bit de complejidad (máquina deTuring) pero no en el modelo aritmético o en el de máquinaRAM real (Blum-Shub-Smale 1989).
Encontrar algoritmos fuertemente polinómicos paraprogramación lineal es uno de los “problemas matemáticospara el siglo 21" de la lista de (Smale 2000). Una regla depivote polinómica para el método del símplice resolvería elproblema afirmativamente.
15
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Complejidad de la programación lineal
Además, los algoritmos polinómicos de programación linealque se conocen no son fuertemente polinómicos: Sonpolinómicos en el modelo bit de complejidad (máquina deTuring) pero no en el modelo aritmético o en el de máquinaRAM real (Blum-Shub-Smale 1989).
Encontrar algoritmos fuertemente polinómicos paraprogramación lineal es uno de los “problemas matemáticospara el siglo 21" de la lista de (Smale 2000). Una regla depivote polinómica para el método del símplice resolvería elproblema afirmativamente.
15
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Complejidad de la programación lineal
Además, los algoritmos polinómicos de programación linealque se conocen no son fuertemente polinómicos: Sonpolinómicos en el modelo bit de complejidad (máquina deTuring) pero no en el modelo aritmético o en el de máquinaRAM real (Blum-Shub-Smale 1989).
Encontrar algoritmos fuertemente polinómicos paraprogramación lineal es uno de los “problemas matemáticospara el siglo 21" de la lista de (Smale 2000). Una regla depivote polinómica para el método del símplice resolvería elproblema afirmativamente.
15
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
¿Por qué era n − d una cota “razonable”?
DefiniciónUn d-politopo es simple si en cada vértice confluyenexactamente d facetas (es decir, las facetas están en “posicióngeneral”)
Se sabe desde los 60 que para probar (o refutar) la Conjeturade Hirsch basta con mirar al caso simple. En este caso, cadavez que recorremos una arista del grafo “salimos” de una únicafaceta y “entramos” en una única faceta (las otras d − 1 semantienen).
16
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
¿Por qué era n − d una cota “razonable”?
DefiniciónUn d-politopo es simple si en cada vértice confluyenexactamente d facetas (es decir, las facetas están en “posicióngeneral”)
Se sabe desde los 60 que para probar (o refutar) la Conjeturade Hirsch basta con mirar al caso simple. En este caso, cadavez que recorremos una arista del grafo “salimos” de una únicafaceta y “entramos” en una única faceta (las otras d − 1 semantienen).
16
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
¿Por qué era n − d una cota “razonable”?
DefiniciónUn d-politopo es simple si en cada vértice confluyenexactamente d facetas (es decir, las facetas están en “posicióngeneral”)
Se sabe desde los 60 que para probar (o refutar) la Conjeturade Hirsch basta con mirar al caso simple. En este caso, cadavez que recorremos una arista del grafo “salimos” de una únicafaceta y “entramos” en una única faceta (las otras d − 1 semantienen).
16
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
¿Por qué era n − d una cota “razonable”?
DefiniciónUn d-politopo es simple si en cada vértice confluyenexactamente d facetas (es decir, las facetas están en “posicióngeneral”)
Se sabe desde los 60 que para probar (o refutar) la Conjeturade Hirsch basta con mirar al caso simple. En este caso, cadavez que recorremos una arista del grafo “salimos” de una únicafaceta y “entramos” en una única faceta (las otras d − 1 semantienen).
16
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
¿Por qué era n − d una cota “razonable”?
La Conjetura de Hirsch se puede interpretar como:
Teorema de los d pasos [Klee-Walkup 1967]Hirsch⇔ no revisitación.
17
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
¿Por qué era n − d una cota “razonable”?
La Conjetura de Hirsch se puede interpretar como:
Supongamos que P es simple. Sean u y v dos vértices de P sinfaceta común.
Teorema de los d pasos [Klee-Walkup 1967]Hirsch⇔ no revisitación.
17
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
¿Por qué era n − d una cota “razonable”?
La Conjetura de Hirsch se puede interpretar como:
Supongamos que P es simple. Sean u y v dos vértices de P sinfaceta común.
Conjetura de la no revisitaciónEs posible ir de u a v de modo que en cada paso entramos enuna faceta nueva, una que no hemos visitado antes.
Es obvio que: no revisitación⇒ Hirsch
Teorema de los d pasos [Klee-Walkup 1967]Hirsch⇔ no revisitación.
17
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
¿Por qué era n − d una cota “razonable”?
La Conjetura de Hirsch se puede interpretar como:
Supongamos que P es simple. Sean u y v dos vértices de P sinfaceta común.
Conjetura de la no revisitaciónEs posible ir de u a v de modo que en cada paso entramos enuna faceta nueva, una que no hemos visitado antes.
Es obvio que: no revisitación⇒ Hirsch
Teorema de los d pasos [Klee-Walkup 1967]Hirsch⇔ no revisitación.
17
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
¿Por qué era n − d una cota “razonable”?
La Conjetura de Hirsch se puede interpretar como:
Supongamos que P es simple. Sean u y v dos vértices de P sinfaceta común.
Conjetura de la no revisitaciónEs posible ir de u a v de modo que en cada paso entramos enuna faceta nueva, una que no hemos visitado antes.
Es obvio que: no revisitación⇒ Hirsch
Teorema de los d pasos [Klee-Walkup 1967]Hirsch⇔ no revisitación.
17
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Lema de los d pasos
La demostración del Teorema de los d pasos es inductiva y sebasa en:
Lema de los d pasos
Sea P un politopo de dimensión d , con n > 2d facetas ydiámetro λ. Entonces, hay otro politopo P ′ de dimensión d + 1,con n + 1 facetas y diámetro λ.
Es decir: podemos incrementar la dimensión y número defacetas de un politopo en una unidad, preservando sudiámetro, hasta que n = 2d .
18
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Lema de los d pasos
La demostración del Teorema de los d pasos es inductiva y sebasa en:
Lema de los d pasos
Sea P un politopo de dimensión d , con n > 2d facetas ydiámetro λ. Entonces, hay otro politopo P ′ de dimensión d + 1,con n + 1 facetas y diámetro λ.
Es decir: podemos incrementar la dimensión y número defacetas de un politopo en una unidad, preservando sudiámetro, hasta que n = 2d .
18
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Lema de los d pasos
La demostración del Teorema de los d pasos es inductiva y sebasa en:
Lema de los d pasos
Sea P un politopo de dimensión d , con n > 2d facetas ydiámetro λ. Entonces, hay otro politopo P ′ de dimensión d + 1,con n + 1 facetas y diámetro λ.
Es decir: podemos incrementar la dimensión y número defacetas de un politopo en una unidad, preservando sudiámetro, hasta que n = 2d .
18
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Los contraejemplos
La construción de contraejemplos tiene dos ingredientes:
1 Un Teorema fuerte de los d pasos parahusos/prismatoides.
2 La construcción de prismatoides de dimensión 5 y“anchura” 6.
19
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Los contraejemplos
La construción de contraejemplos tiene dos ingredientes:
1 Un Teorema fuerte de los d pasos parahusos/prismatoides.
2 La construcción de prismatoides de dimensión 5 y“anchura” 6.
19
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Los contraejemplos
La construción de contraejemplos tiene dos ingredientes:
1 Un Teorema fuerte de los d pasos parahusos/prismatoides.
2 La construcción de prismatoides de dimensión 5 y“anchura” 6.
19
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Husos
DefiniciónUn huso es un politopo P con dos vértices distinguidos u y vtales que toda faceta contiene a uno de los dos.
u u
vvDefiniciónLa longitud de unhuso es ladistancia (en elgrafo) entre u y v .
ObservaciónEn dimensión 3todo huso tienelongitud ≤ 3
20
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Husos
DefiniciónUn huso es un politopo P con dos vértices distinguidos u y vtales que toda faceta contiene a uno de los dos.
u u
vvDefiniciónLa longitud de unhuso es ladistancia (en elgrafo) entre u y v .
ObservaciónEn dimensión 3todo huso tienelongitud ≤ 3
20
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Husos
DefiniciónUn huso es un politopo P con dos vértices distinguidos u y vtales que toda faceta contiene a uno de los dos.
u u
vvDefiniciónLa longitud de unhuso es ladistancia (en elgrafo) entre u y v .
ObservaciónEn dimensión 3todo huso tienelongitud ≤ 3
20
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Husos
Teorema (Fuerte de los d pasos, versión husos, S. 2012)
Sea P un huso de dimensión d , con n > 2d facetas, y longitudδ. Entonces, hay otro huso P ′ de dimensión d + 1, con n + 1facetas y longitud δ + 1.
Es decir: podemos aumentar la dimensión, número de facetasy longitud de un huso, las tres en una unidad, hasta quen = 2d .
CorolarioEn particular, si un huso tiene longitud > d entonces hay otrohuso P ′ (de dimensión n − d , con 2n − 2d facetas, y longitud≥ δ + n − 2d > n − d) que viola la Conjetura de Hirsch.
21
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Husos
Teorema (Fuerte de los d pasos, versión husos, S. 2012)
Sea P un huso de dimensión d , con n > 2d facetas, y longitudδ. Entonces, hay otro huso P ′ de dimensión d + 1, con n + 1facetas y longitud δ + 1.
Es decir: podemos aumentar la dimensión, número de facetasy longitud de un huso, las tres en una unidad, hasta quen = 2d .
CorolarioEn particular, si un huso tiene longitud > d entonces hay otrohuso P ′ (de dimensión n − d , con 2n − 2d facetas, y longitud≥ δ + n − 2d > n − d) que viola la Conjetura de Hirsch.
21
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Husos
Teorema (Fuerte de los d pasos, versión husos, S. 2012)
Sea P un huso de dimensión d , con n > 2d facetas, y longitudδ. Entonces, hay otro huso P ′ de dimensión d + 1, con n + 1facetas y longitud δ + 1.
Es decir: podemos aumentar la dimensión, número de facetasy longitud de un huso, las tres en una unidad, hasta quen = 2d .
CorolarioEn particular, si un huso tiene longitud > d entonces hay otrohuso P ′ (de dimensión n − d , con 2n − 2d facetas, y longitud≥ δ + n − 2d > n − d) que viola la Conjetura de Hirsch.
21
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Prismatoides
DefiniciónUn prismatoide es un politopo Q con dos facetas Q+ and Q−
que contienen a todos los vértices.
Q+
Q−
Q
DefiniciónLa anchura de unprismatoide es ladistancia (en elgrafo dual) entreQ+ y Q−.
22
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Prismatoides
DefiniciónUn prismatoide es un politopo Q con dos facetas Q+ and Q−
que contienen a todos los vértices.
Q+
Q−
Q
DefiniciónLa anchura de unprismatoide es ladistancia (en elgrafo dual) entreQ+ y Q−.
22
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Prismatoides
Teorema (Fuerte de los d pasos, versión prismatoides,S. 2012)
Sea Q un prismatoide de dimensión d , con n > 2d vértices, ycon anchura δ. Entonces, existe otro prismatoide Q′ dedimensión d + 1, con n + 1 vértices y con anchura δ + 1.
Es decir: podemos aumentar la dimensión, número de vérticesy anchura de un prismatoide, las tres en una unidad, hasta quen = 2d .
23
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Prismatoides
Teorema (Fuerte de los d pasos, versión prismatoides,S. 2012)
Sea Q un prismatoide de dimensión d , con n > 2d vértices, ycon anchura δ. Entonces, existe otro prismatoide Q′ dedimensión d + 1, con n + 1 vértices y con anchura δ + 1.
Es decir: podemos aumentar la dimensión, número de vérticesy anchura de un prismatoide, las tres en una unidad, hasta quen = 2d .
23
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
El Teorema fuerte de los d pasos
Demostración
Q ⊂ R2
Q+
Q−Q−
Q ⊂ R3
Q+
w
Q− := o.p. s.v(Q−)
Q+
w
o.p. s.v(Q) ⊂ R3
v
u
u
24
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
El Teorema fuerte de los d pasos
CorolarioEn particular, si un prismatoide Q tiene anchura > d entonceshay un politopo P ′ (de dimensión n − d , con 2n − 2d facetas, y longitud≥ δ + n − 2d > n − d) que viola la Conjetura de Hirsch.
Este resultado relaciona la Conjetura de Hirsch con soloanchura y dimensión. Cómo de complicado sea el politopo(número de vértices o facetas) no aparece en el enunciado(salvo para decirnos cmo de complicado es el contraejemplo resultante).
25
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
El Teorema fuerte de los d pasos
CorolarioEn particular, si un prismatoide Q tiene anchura > d entonceshay un politopo P ′ (de dimensión n − d , con 2n − 2d facetas, y longitud≥ δ + n − 2d > n − d) que viola la Conjetura de Hirsch.
Este resultado relaciona la Conjetura de Hirsch con soloanchura y dimensión. Cómo de complicado sea el politopo(número de vértices o facetas) no aparece en el enunciado(salvo para decirnos cmo de complicado es el contraejemplo resultante).
25
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Un 5-pismatoide de anchura seis
Sea Q el prismatoide cuyos vértices son las 48 filas de lassiguientes matrices:
x1 x2 x3 x4 x5±18 0 0 0 1
0 ±18 0 0 10 0 ±45 0 10 0 0 ±45 1
±15 ±15 0 0 10 0 ±30 ±30 10 ±10 ±40 0 1
±10 0 0 ±40 1
x1 x2 x3 x4 x50 0 0 ±18 −10 0 ±18 0 −1
±45 0 0 0 −10 ±45 0 0 −10 0 ±15 ±15 −1
±30 ±30 0 0 −1±40 0 ±10 0 −1
0 ±40 0 ±10 −1
Teorema (S. 2012)
Q tiene anchura seis.
26
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Un 5-pismatoide de anchura seis
Sea Q el prismatoide cuyos vértices son las 48 filas de lassiguientes matrices:
x1 x2 x3 x4 x5±18 0 0 0 1
0 ±18 0 0 10 0 ±45 0 10 0 0 ±45 1
±15 ±15 0 0 10 0 ±30 ±30 10 ±10 ±40 0 1
±10 0 0 ±40 1
x1 x2 x3 x4 x50 0 0 ±18 −10 0 ±18 0 −1
±45 0 0 0 −10 ±45 0 0 −10 0 ±15 ±15 −1
±30 ±30 0 0 −1±40 0 ±10 0 −1
0 ±40 0 ±10 −1
Teorema (S. 2012)
Q tiene anchura seis.
26
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Un 5-pismatoide de anchura seis
Sea Q el prismatoide cuyos vértices son las 48 filas de lassiguientes matrices:
x1 x2 x3 x4 x5±18 0 0 0 1
0 ±18 0 0 10 0 ±45 0 10 0 0 ±45 1
±15 ±15 0 0 10 0 ±30 ±30 10 ±10 ±40 0 1
±10 0 0 ±40 1
x1 x2 x3 x4 x50 0 0 ±18 −10 0 ±18 0 −1
±45 0 0 0 −10 ±45 0 0 −10 0 ±15 ±15 −1
±30 ±30 0 0 −1±40 0 ±10 0 −1
0 ±40 0 ±10 −1
Teorema (S. 2012)
Q tiene anchura seis.
26
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Un 5-pismatoide de anchura seis
Sea Q el prismatoide cuyos vértices son las 48 filas de lassiguientes matrices:
x1 x2 x3 x4 x5±18 0 0 0 1
0 ±18 0 0 10 0 ±45 0 10 0 0 ±45 1
±15 ±15 0 0 10 0 ±30 ±30 10 ±10 ±40 0 1
±10 0 0 ±40 1
x1 x2 x3 x4 x50 0 0 ±18 −10 0 ±18 0 −1
±45 0 0 0 −10 ±45 0 0 −10 0 ±15 ±15 −1
±30 ±30 0 0 −1±40 0 ±10 0 −1
0 ±40 0 ±10 −1
Teorema (S. 2012)
Q tiene anchura seis.
26
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Un 5-pismatoide de anchura seis
CorolarioHay un politopo de dimensión 43 con 86 facetas y diámetro (almenos) 44.
Demostración 1 del TeoremaSe ha verificado con software para el análisis de politopos(polymake, lrs, cdd) que el grafo dual de Q tiene lasiguiente estructura, módulo simetrías:
IC
D
F
E G J
H
BA K L
27
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Un 5-pismatoide de anchura seis
CorolarioHay un politopo de dimensión 43 con 86 facetas y diámetro (almenos) 44.
Demostración 1 del TeoremaSe ha verificado con software para el análisis de politopos(polymake, lrs, cdd) que el grafo dual de Q tiene lasiguiente estructura, módulo simetrías:
IC
D
F
E G J
H
BA K L
27
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Un 5-pismatoide de anchura seis
CorolarioHay un politopo de dimensión 43 con 86 facetas y diámetro (almenos) 44.
Demostración 1 del TeoremaSe ha verificado con software para el análisis de politopos(polymake, lrs, cdd) que el grafo dual de Q tiene lasiguiente estructura, módulo simetrías:
IC
D
F
E G J
H
BA K L
27
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Combinatoria de prismatoides
Demostración 2 del Teorema (idea).Para analizar la combinatoria de un d-prismatoide Q basta conestudiar su intersección con un hiperplano intermedio . . .
Q+
Q−
Q ∩ HH
Q
28
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Combinatoria de prismatoides
Demostración 2 del Teorema (idea).. . . la cual es la suma de Minkowski Q+ + Q− de las dos basesQ+ y Q−. El abanico normal de Q+ + Q− es la “superposición”de los de of Q+ y Q−.
+ 12
12 =
28
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Combinatoria de prismatoides
Demostración 2 del Teorema (idea).. . . la cual es la suma de Minkowski Q+ + Q− de las dos basesQ+ y Q−. El abanico normal de Q+ + Q− es la “superposición”de los de Q+ y Q−.
+ 12
12 =
28
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Combinatoria de prismatoides
Así que: la combinatoria de Q se deduce de la superposiciónde los abanicos normales de Q+ y Q−.
NotaEl abanico normal de un (d − 1)-politopo se puede pensarcomo una descomposición celular (geodésica, poliédrica; un“mapa”) en la (d − 2)-esfera.
Conclusión4-prismatoides⇔ pares de mapas en la 2-esfera.5-prismatoides⇔ pares de mapas en la 3-esfera.
29
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Combinatoria de prismatoides
Así que: la combinatoria de Q se deduce de la superposiciónde los abanicos normales de Q+ y Q−.
NotaEl abanico normal de un (d − 1)-politopo se puede pensarcomo una descomposición celular (geodésica, poliédrica; un“mapa”) en la (d − 2)-esfera.
Conclusión4-prismatoides⇔ pares de mapas en la 2-esfera.5-prismatoides⇔ pares de mapas en la 3-esfera.
29
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Combinatoria de prismatoides
Así que: la combinatoria de Q se deduce de la superposiciónde los abanicos normales de Q+ y Q−.
NotaEl abanico normal de un (d − 1)-politopo se puede pensarcomo una descomposición celular (geodésica, poliédrica; un“mapa”) en la (d − 2)-esfera.
Conclusión4-prismatoides⇔ pares de mapas en la 2-esfera.5-prismatoides⇔ pares de mapas en la 3-esfera.
29
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Ejemplo: (parte de) un 4-prismatoide
30
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Ejemplo: (parte de) un 4-prismatoide
4-prismatoide de anchura > 4m
par de mapas (geodésicos, poliédricos) en S2 tales quedos pasos no bastan para ir de un vértice azul a uno rojo.
30
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Ejemplo: (parte de) un 4-prismatoide
5-prismatoide de anchura > 5m
par de mapas (geodésicos, poliédricos) en S3 tales quetres pasos no bastan para ir de un vértice azul a uno rojo.
30
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Un 4-prismatoide de anchura > 4?
Replicando la siguiente estructura básica obtenemos un mapaperiódico en el plano que es “no Hirsch”:
31
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Un 4-prismatoide de anchura > 4?
Replicando la siguiente estructura básica obtenemos un mapaperiódico en el plano que es “no Hirsch”:
31
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Un 4-prismatoide de anchura > 4?
Replicando la siguiente estructura básica obtenemos un mapaperiódico en el plano que es “no Hirsch”:
31
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Un 4-prismatoide de anchura > 4?
Replicando la siguiente estructura básica obtenemos un mapaperiódico en el plano que es “no Hirsch”:
31
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Un 4-prismatoide de anchura > 4?
Replicando la siguiente estructura básica obtenemos un mapaperiódico en el plano que es “no Hirsch”:
31
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Un 4-prismatoide de anchura > 4?
Replicando la siguiente estructura básica obtenemos un mapaperiódico en el plano que es “no Hirsch”.
31
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Un 4-prismatoide de anchura > 4?
Replicando la siguiente estructura básica obtenemos un mapaperiódico en el plano que es “no Hirsch”.
Si este dibujo estuviera en la 2-esfera, representaría en 4-prismatoide de anchura 5.
31
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Un 4-prismatoide de anchura > 4?
Replicando la siguiente estructura básica obtenemos un mapaperiódico en el plano que es “no Hirsch”.
Si este dibujo estuviera en la 2-esfera, representaría en 4-prismatoide de anchura 5.
Eso no funciona, pero metiendo el dibujo en (dos toros inmersosen) S3 sí que funciona, y da un prismatoide con 48 vértices.
31
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Contraejemplos más pequeños
Hay dos maneras de obtener contraejemplos más pequeños:
Encontrar 5-prismatoides de anchura > 5 más pequeños,oEncontrar un 4-prismatoide de anchura > 4.
Lo segundo es imposible:
Teorema (S.-Stephen-Thomas 2012)Todo prismatoide de dimensión 4 tiene anchura ≤ 4.
32
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Contraejemplos más pequeños
Hay dos maneras de obtener contraejemplos más pequeños:
Encontrar 5-prismatoides de anchura > 5 más pequeños,oEncontrar un 4-prismatoide de anchura > 4.
Lo segundo es imposible:
Teorema (S.-Stephen-Thomas 2012)Todo prismatoide de dimensión 4 tiene anchura ≤ 4.
32
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Contraejemplos más pequeños
Hay dos maneras de obtener contraejemplos más pequeños:
Encontrar 5-prismatoides de anchura > 5 más pequeños,oEncontrar un 4-prismatoide de anchura > 4.
Lo segundo es imposible:
Teorema (S.-Stephen-Thomas 2012)Todo prismatoide de dimensión 4 tiene anchura ≤ 4.
32
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Contraejemplos más pequeños
Hay dos maneras de obtener contraejemplos más pequeños:
Encontrar 5-prismatoides de anchura > 5 más pequeños,oEncontrar un 4-prismatoide de anchura > 4.
Lo segundo es imposible:
Teorema (S.-Stephen-Thomas 2012)Todo prismatoide de dimensión 4 tiene anchura ≤ 4.
32
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Contraejemplos más pequeños
En cambio
Teorema (Matschke-S-Weibel, 2015)Hay un prismatoide de dimensión 5 con 25 vértices y anchura6.
CorolarioHay un 20-politopo con 40 facetas que viola la Conjetura deHirsch.
Este politopo se ha calculado de forma explícita. Tiene 36 442vértices, y diámetro 21.
33
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Contraejemplos más pequeños
En cambio
Teorema (Matschke-S-Weibel, 2015)Hay un prismatoide de dimensión 5 con 25 vértices y anchura6.
CorolarioHay un 20-politopo con 40 facetas que viola la Conjetura deHirsch.
Este politopo se ha calculado de forma explícita. Tiene 36 442vértices, y diámetro 21.
33
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Contraejemplos más pequeños
En cambio
Teorema (Matschke-S-Weibel, 2015)Hay un prismatoide de dimensión 5 con 25 vértices y anchura6.
CorolarioHay un 20-politopo con 40 facetas que viola la Conjetura deHirsch.
Este politopo se ha calculado de forma explícita. Tiene 36 442vértices, y diámetro 21.
33
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Contraejemplos más pequeños
En cambio
Teorema (Matschke-S-Weibel, 2015)Hay un prismatoide de dimensión 5 con 25 vértices y anchura6.
CorolarioHay un 20-politopo con 40 facetas que viola la Conjetura deHirsch.
Este politopo se ha calculado de forma explícita. Tiene 36 442vértices, y diámetro 21.
33
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Contraejemplos más pequeños
34
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Anchura asintótica en dimensión cinco
Teorema (Matschke-S.-Weibel 2015)Hay 5-prismatoides con n vértices y anchura Ω(
√n).
Idea de la demostraciónComenzar con el siguiente par de mapas en el toro.
35
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Anchura asintótica en dimensión cinco
Teorema (Matschke-S.-Weibel 2015)Hay 5-prismatoides con n vértices y anchura Ω(
√n).
Idea de la demostraciónComenzar con el siguiente par de mapas en el toro.
35
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Anchura asintótica en dimensión cinco
36
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Anchura asintótica en dimensión cinco
36
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Anchura asintótica en dimensión cinco
36
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Anchura asintótica en dimensión cinco
36
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Anchura asintótica en dimensión cinco
36
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Anchura asintótica en dimensión cinco
Dibujar los mapas rojo y azul en dos toros paralelos en la3-esfera.
Completar los mapas de los toros a la3-esfera (hace falta un númerocuadrático de celdas para ello).
Entre toro y toro se obtieneesencialmente la superposición delos mapas iniciales del toro plano.
37
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Anchura asintótica en dimensión cinco
Dibujar los mapas rojo y azul en dos toros paralelos en la3-esfera.
Completar los mapas de los toros a la3-esfera (hace falta un númerocuadrático de celdas para ello).
Entre toro y toro se obtieneesencialmente la superposición delos mapas iniciales del toro plano.
37
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Anchura asintótica en dimensión cinco
Dibujar los mapas rojo y azul en dos toros paralelos en la3-esfera.
Completar los mapas de los toros a la3-esfera (hace falta un númerocuadrático de celdas para ello).
Entre toro y toro se obtieneesencialmente la superposición delos mapas iniciales del toro plano.
37
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Anchura asintótica en dimensión fija
Si fijamos la dimensión d , la anchura de los prismatoides eslineal. Por ejemplo:
Teorema (Matschke-S.-Weibel 2015Un 5-prismatoide no puede tener anchura mayor que n/2 + 3.
CorolarioUsando el Teorema fuerte de los d pasos a partir de un5-prismatoide es imposible violar la Conjetura de Hirsch pormás de un 50%.
38
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Anchura asintótica en dimensión fija
Si fijamos la dimensión d , la anchura de los prismatoides eslineal. Por ejemplo:
Teorema (Matschke-S.-Weibel 2015Un 5-prismatoide no puede tener anchura mayor que n/2 + 3.
CorolarioUsando el Teorema fuerte de los d pasos a partir de un5-prismatoide es imposible violar la Conjetura de Hirsch pormás de un 50%.
38
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Anchura asintótica en dimensión fija
Si fijamos la dimensión d , la anchura de los prismatoides eslineal. Por ejemplo:
Teorema (Matschke-S.-Weibel 2015Un 5-prismatoide no puede tener anchura mayor que n/2 + 3.
CorolarioUsando el Teorema fuerte de los d pasos a partir de un5-prismatoide es imposible violar la Conjetura de Hirsch pormás de un 50%.
38
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Conclusión
Mediante productos y pegados, los contraejemplos seconvierten en una familia infinita que viola la conjetura porun 5%.Esto rompe una cierta barrera psicológica, pero para lasaplicaciones resulta absolutamente irrelevante.
Finding a counterexample will be merely a small firststep in the line of investigation related to theconjecture.
(V. Klee and P. Kleinschmidt, 1987)
39
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Conclusión
Mediante productos y pegados, los contraejemplos seconvierten en una familia infinita que viola la conjetura porun 5%.Esto rompe una cierta barrera psicológica, pero para lasaplicaciones resulta absolutamente irrelevante.
Finding a counterexample will be merely a small firststep in the line of investigation related to theconjecture.
(V. Klee and P. Kleinschmidt, 1987)
39
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Conclusión
Mediante productos y pegados, los contraejemplos seconvierten en una familia infinita que viola la conjetura porun 5%.Esto rompe una cierta barrera psicológica, pero para lasaplicaciones resulta absolutamente irrelevante.
Finding a counterexample will be merely a small firststep in the line of investigation related to theconjecture.
(V. Klee and P. Kleinschmidt, 1987)
39
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Otras aproximaciones
40
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Formulación topológica de la Conjetura de Hirsch
En vez de mirar a politopos (simpliciales), ¿por qué no estudiarcomplejos simpliciales más generales?
Complejos simpliciales puros, Hc(n,d)
Pseudo-variedades (con o sin borde).Variedades (con o sin borde). Esferas (o bolas).. . .
En todos los casos se estudia el diámetro (dual); dos simplicesson adyacentes si se interesan en codimensión 1.
LemaEl diámetro máximo es el mismo para complejos purosarbitrarios y para pseudo-variedades con borde.
41
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Formulación topológica de la Conjetura de Hirsch
En vez de mirar a politopos (simpliciales), ¿por qué no estudiarcomplejos simpliciales más generales?
Complejos simpliciales puros, Hc(n,d)
Pseudo-variedades (con o sin borde).Variedades (con o sin borde). Esferas (o bolas).. . .
En todos los casos se estudia el diámetro (dual); dos simplicesson adyacentes si se interesan en codimensión 1.
LemaEl diámetro máximo es el mismo para complejos purosarbitrarios y para pseudo-variedades con borde.
41
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Formulación topológica de la Conjetura de Hirsch
En vez de mirar a politopos (simpliciales), ¿por qué no estudiarcomplejos simpliciales más generales?
Complejos simpliciales puros, Hc(n,d)
Pseudo-variedades (con o sin borde).Variedades (con o sin borde). Esferas (o bolas).. . .
En todos los casos se estudia el diámetro (dual); dos simplicesson adyacentes si se interesan en codimensión 1.
LemaEl diámetro máximo es el mismo para complejos purosarbitrarios y para pseudo-variedades con borde.
41
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Formulación topológica de la Conjetura de Hirsch
En vez de mirar a politopos (simpliciales), ¿por qué no estudiarcomplejos simpliciales más generales?
Complejos simpliciales puros, Hc(n,d)
Pseudo-variedades (con o sin borde).Variedades (con o sin borde). Esferas (o bolas).. . .
En todos los casos se estudia el diámetro (dual); dos simplicesson adyacentes si se interesan en codimensión 1.
LemaEl diámetro máximo es el mismo para complejos purosarbitrarios y para pseudo-variedades con borde.
41
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Formulación topológica de la Conjetura de Hirsch
En vez de mirar a politopos (simpliciales), ¿por qué no estudiarcomplejos simpliciales más generales?
Complejos simpliciales puros, Hc(n,d)
Pseudo-variedades (con o sin borde).Variedades (con o sin borde). Esferas (o bolas).. . .
En todos los casos se estudia el diámetro (dual); dos simplicesson adyacentes si se interesan en codimensión 1.
LemaEl diámetro máximo es el mismo para complejos purosarbitrarios y para pseudo-variedades con borde.
41
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Formulación topológica de la Conjetura de Hirsch
En vez de mirar a politopos (simpliciales), ¿por qué no estudiarcomplejos simpliciales más generales?
Complejos simpliciales puros, Hc(n,d)
Pseudo-variedades (con o sin borde).Variedades (con o sin borde). Esferas (o bolas).. . .
En todos los casos se estudia el diámetro (dual); dos simplicesson adyacentes si se interesan en codimensión 1.
LemaEl diámetro máximo es el mismo para complejos purosarbitrarios y para pseudo-variedades con borde.
41
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Formulación topológica de la Conjetura de Hirsch
En vez de mirar a politopos (simpliciales), ¿por qué no estudiarcomplejos simpliciales más generales?
Complejos simpliciales puros, Hc(n,d)
Pseudo-variedades (con o sin borde).Variedades (con o sin borde). Esferas (o bolas).. . .
En todos los casos se estudia el diámetro (dual); dos simplicesson adyacentes si se interesan en codimensión 1.
LemaEl diámetro máximo es el mismo para complejos purosarbitrarios y para pseudo-variedades con borde.
41
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
El máximo diámetro de complejos simpliciales puros
En dimensión dos:
Theorem (S., 2013)29
(n − 1)2 < Hc(n,3) <14
n2.
En dimensión superior:
Theorem (S., 2013)
Hc(kn, kd) >22k Hc(n,d)k .
Corollary (S., 2013)
Ω(n2d/3) ≤ Hc(n,d) ≤ O(nd ).
42
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
El máximo diámetro de complejos simpliciales puros
En dimensión dos:
Theorem (S., 2013)29
(n − 1)2 < Hc(n,3) <14
n2.
En dimensión superior:
Theorem (S., 2013)
Hc(kn, kd) >22k Hc(n,d)k .
Corollary (S., 2013)
Ω(n2d/3) ≤ Hc(n,d) ≤ O(nd ).
42
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
El máximo diámetro de complejos simpliciales puros
En dimensión dos:
Theorem (S., 2013)29
(n − 1)2 < Hc(n,3) <14
n2.
En dimensión superior:
Theorem (S., 2013)
Hc(kn, kd) >22k Hc(n,d)k .
Corollary (S., 2013)
Ω(n2d/3) ≤ Hc(n,d) ≤ O(nd ).
42
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
El máximo diámetro de complejos simpliciales puros
En dimensión dos:
Theorem (S., 2013)29
(n − 1)2 < Hc(n,3) <14
n2.
En dimensión superior:
Theorem (S., 2013)
Hc(kn, kd) >22k Hc(n,d)k .
Corollary (S., 2013)
Ω(n2d/3) ≤ Hc(n,d) ≤ O(nd ).
42
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Complejos normales
O sea, los complejos puros (incluso pseudo-variedades)pueden tener diámetro exponencial.¿Qué restricción hemos de poner para (tener esperanzas de)conseguir diámetros polinómicos?
El favorito de todo el mundo es:
DefinitionUn complejo simplicial K es normal si para toda cara S ∈ K elsubgrafo inducido por las caras que contienen a S es conexo.(Nota: hay una caracterización topológica que viene a ser que:“todas las singularidades son de codimensión uno”).
Las variedades (con o sin borde) son normales.
43
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Complejos normales
O sea, los complejos puros (incluso pseudo-variedades)pueden tener diámetro exponencial.¿Qué restricción hemos de poner para (tener esperanzas de)conseguir diámetros polinómicos?
El favorito de todo el mundo es:
DefinitionUn complejo simplicial K es normal si para toda cara S ∈ K elsubgrafo inducido por las caras que contienen a S es conexo.(Nota: hay una caracterización topológica que viene a ser que:“todas las singularidades son de codimensión uno”).
Las variedades (con o sin borde) son normales.
43
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Complejos normales
O sea, los complejos puros (incluso pseudo-variedades)pueden tener diámetro exponencial.¿Qué restricción hemos de poner para (tener esperanzas de)conseguir diámetros polinómicos?
El favorito de todo el mundo es:
DefinitionUn complejo simplicial K es normal si para toda cara S ∈ K elsubgrafo inducido por las caras que contienen a S es conexo.(Nota: hay una caracterización topológica que viene a ser que:“todas las singularidades son de codimensión uno”).
Las variedades (con o sin borde) son normales.
43
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Complejos normales
O sea, los complejos puros (incluso pseudo-variedades)pueden tener diámetro exponencial.¿Qué restricción hemos de poner para (tener esperanzas de)conseguir diámetros polinómicos?
El favorito de todo el mundo es:
DefinitionUn complejo simplicial K es normal si para toda cara S ∈ K elsubgrafo inducido por las caras que contienen a S es conexo.(Nota: hay una caracterización topológica que viene a ser que:“todas las singularidades son de codimensión uno”).
Las variedades (con o sin borde) son normales.
43
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Complejos normales
O sea, los complejos puros (incluso pseudo-variedades)pueden tener diámetro exponencial.¿Qué restricción hemos de poner para (tener esperanzas de)conseguir diámetros polinómicos?
El favorito de todo el mundo es:
DefinitionUn complejo simplicial K es normal si para toda cara S ∈ K elsubgrafo inducido por las caras que contienen a S es conexo.(Nota: hay una caracterización topológica que viene a ser que:“todas las singularidades son de codimensión uno”).
Las variedades (con o sin borde) son normales.
43
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
La importancia de ser normal
La normalidad se hereda. Todo “link” de un complejonormal es normal, lo cual permite demostraciones porinducción en la dimensión.Se podría decir que el grafo de adyacencias de uncomplejo solo refleja la proximidad en él si el complejo esnormal.Las cotas de Kalai-Kleitman y de Barnette-Larmanfuncionan (¡con demostraciones incluso más sencillas!) encomplejos normales.
En particular, recientemente se ha “actualizado” la Conjeturade Hirsch a:
Conjetura (Hähnle@polymath3, 2011)El diámetro (dual) de todo complejo simplicial normal (enparticular, el de toda variedad simplicial) de dimensión d con nvértices está acotado por d(n − d).
44
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
La importancia de ser normal
La normalidad se hereda. Todo “link” de un complejonormal es normal, lo cual permite demostraciones porinducción en la dimensión.Se podría decir que el grafo de adyacencias de uncomplejo solo refleja la proximidad en él si el complejo esnormal.Las cotas de Kalai-Kleitman y de Barnette-Larmanfuncionan (¡con demostraciones incluso más sencillas!) encomplejos normales.
En particular, recientemente se ha “actualizado” la Conjeturade Hirsch a:
Conjetura (Hähnle@polymath3, 2011)El diámetro (dual) de todo complejo simplicial normal (enparticular, el de toda variedad simplicial) de dimensión d con nvértices está acotado por d(n − d).
44
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
La importancia de ser normal
La normalidad se hereda. Todo “link” de un complejonormal es normal, lo cual permite demostraciones porinducción en la dimensión.Se podría decir que el grafo de adyacencias de uncomplejo solo refleja la proximidad en él si el complejo esnormal.Las cotas de Kalai-Kleitman y de Barnette-Larmanfuncionan (¡con demostraciones incluso más sencillas!) encomplejos normales.
En particular, recientemente se ha “actualizado” la Conjeturade Hirsch a:
Conjetura (Hähnle@polymath3, 2011)El diámetro (dual) de todo complejo simplicial normal (enparticular, el de toda variedad simplicial) de dimensión d con nvértices está acotado por d(n − d).
44
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
La importancia de ser normal
La normalidad se hereda. Todo “link” de un complejonormal es normal, lo cual permite demostraciones porinducción en la dimensión.Se podría decir que el grafo de adyacencias de uncomplejo solo refleja la proximidad en él si el complejo esnormal.Las cotas de Kalai-Kleitman y de Barnette-Larmanfuncionan (¡con demostraciones incluso más sencillas!) encomplejos normales.
En particular, recientemente se ha “actualizado” la Conjeturade Hirsch a:
Conjetura (Hähnle@polymath3, 2011)El diámetro (dual) de todo complejo simplicial normal (enparticular, el de toda variedad simplicial) de dimensión d con nvértices está acotado por d(n − d).
44
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
La importancia de ser normal
La normalidad se hereda. Todo “link” de un complejonormal es normal, lo cual permite demostraciones porinducción en la dimensión.Se podría decir que el grafo de adyacencias de uncomplejo solo refleja la proximidad en él si el complejo esnormal.Las cotas de Kalai-Kleitman y de Barnette-Larmanfuncionan (¡con demostraciones incluso más sencillas!) encomplejos normales.
En particular, recientemente se ha “actualizado” la Conjeturade Hirsch a:
Conjetura (Hähnle@polymath3, 2011)El diámetro (dual) de todo complejo simplicial normal (enparticular, el de toda variedad simplicial) de dimensión d con nvértices está acotado por d(n − d).
44
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Complejos simpliciales “flag”
DefinitionUn complejo simplicial C se llama flag si coincide con elcomplejo de cliques de un grafo. Es decir, siempre que k > 2vértices formen un grafo completo en el 1-esqueleto de C,forman también una cara (de dimensión k − 1).(Su anillo de Stanley-Reisner está generado en grado dos).
Adiprasito y Benedetti demuestran que
Theorem (Adiprasito-Benedetti, 2014)Todo complejo simplicial normal y “flag” (en particular todopolitopo “flag”) satisface la Conjetura de Hirsch.
Dan dos demostraciones: una más “diferencial” y otra máscombinatoria.
45
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Complejos simpliciales “flag”
DefinitionUn complejo simplicial C se llama flag si coincide con elcomplejo de cliques de un grafo. Es decir, siempre que k > 2vértices formen un grafo completo en el 1-esqueleto de C,forman también una cara (de dimensión k − 1).(Su anillo de Stanley-Reisner está generado en grado dos).
Adiprasito y Benedetti demuestran que
Theorem (Adiprasito-Benedetti, 2014)Todo complejo simplicial normal y “flag” (en particular todopolitopo “flag”) satisface la Conjetura de Hirsch.
Dan dos demostraciones: una más “diferencial” y otra máscombinatoria.
45
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Complejos simpliciales “flag”
DefinitionUn complejo simplicial C se llama flag si coincide con elcomplejo de cliques de un grafo. Es decir, siempre que k > 2vértices formen un grafo completo en el 1-esqueleto de C,forman también una cara (de dimensión k − 1).(Su anillo de Stanley-Reisner está generado en grado dos).
Adiprasito y Benedetti demuestran que
Theorem (Adiprasito-Benedetti, 2014)Todo complejo simplicial normal y “flag” (en particular todopolitopo “flag”) satisface la Conjetura de Hirsch.
Dan dos demostraciones: una más “diferencial” y otra máscombinatoria.
45
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Complejos simpliciales “flag”
DefinitionUn complejo simplicial C se llama flag si coincide con elcomplejo de cliques de un grafo. Es decir, siempre que k > 2vértices formen un grafo completo en el 1-esqueleto de C,forman también una cara (de dimensión k − 1).(Su anillo de Stanley-Reisner está generado en grado dos).
Adiprasito y Benedetti demuestran que
Theorem (Adiprasito-Benedetti, 2014)Todo complejo simplicial normal y “flag” (en particular todopolitopo “flag”) satisface la Conjetura de Hirsch.
Dan dos demostraciones: una más “diferencial” y otra máscombinatoria.
45
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Complejos simpliciales “flag”
La demostración combinatoria construye, en todo complejonormal y flag, ciertos caminos con la propiedad deno-revisitación. Los llaman segmentos combinatorios.Esto sugeriría la posibilidad de que esos mismos segmentoscombinatorios existan en complejos normales más generales ytengan diámetro polinómico. Desafortunadamente no es así:
Theorem (Labbé-Manneville-S.-2015+)En todo complejo normal (en particular en toda variedad)existen “segmentos combinatorios” entre cualesquiera dossímplices.Pero hay d-politopos con n-vértices en los que esossegmentos tienen longitud exponencial (2d−2n,prácticamente la cota superior de Barnette-Larman).
46
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Complejos simpliciales “flag”
La demostración combinatoria construye, en todo complejonormal y flag, ciertos caminos con la propiedad deno-revisitación. Los llaman segmentos combinatorios.Esto sugeriría la posibilidad de que esos mismos segmentoscombinatorios existan en complejos normales más generales ytengan diámetro polinómico. Desafortunadamente no es así:
Theorem (Labbé-Manneville-S.-2015+)En todo complejo normal (en particular en toda variedad)existen “segmentos combinatorios” entre cualesquiera dossímplices.Pero hay d-politopos con n-vértices en los que esossegmentos tienen longitud exponencial (2d−2n,prácticamente la cota superior de Barnette-Larman).
46
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Complejos simpliciales “flag”
La demostración combinatoria construye, en todo complejonormal y flag, ciertos caminos con la propiedad deno-revisitación. Los llaman segmentos combinatorios.Esto sugeriría la posibilidad de que esos mismos segmentoscombinatorios existan en complejos normales más generales ytengan diámetro polinómico. Desafortunadamente no es así:
Theorem (Labbé-Manneville-S.-2015+)En todo complejo normal (en particular en toda variedad)existen “segmentos combinatorios” entre cualesquiera dossímplices.Pero hay d-politopos con n-vértices en los que esossegmentos tienen longitud exponencial (2d−2n,prácticamente la cota superior de Barnette-Larman).
46
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Complejos simpliciales “flag”
La demostración combinatoria construye, en todo complejonormal y flag, ciertos caminos con la propiedad deno-revisitación. Los llaman segmentos combinatorios.Esto sugeriría la posibilidad de que esos mismos segmentoscombinatorios existan en complejos normales más generales ytengan diámetro polinómico. Desafortunadamente no es así:
Theorem (Labbé-Manneville-S.-2015+)En todo complejo normal (en particular en toda variedad)existen “segmentos combinatorios” entre cualesquiera dossímplices.Pero hay d-politopos con n-vértices en los que esossegmentos tienen longitud exponencial (2d−2n,prácticamente la cota superior de Barnette-Larman).
46
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Complejos simpliciales “flag”
La demostración combinatoria construye, en todo complejonormal y flag, ciertos caminos con la propiedad deno-revisitación. Los llaman segmentos combinatorios.Esto sugeriría la posibilidad de que esos mismos segmentoscombinatorios existan en complejos normales más generales ytengan diámetro polinómico. Desafortunadamente no es así:
Theorem (Labbé-Manneville-S.-2015+)En todo complejo normal (en particular en toda variedad)existen “segmentos combinatorios” entre cualesquiera dossímplices.Pero hay d-politopos con n-vértices en los que esossegmentos tienen longitud exponencial (2d−2n,prácticamente la cota superior de Barnette-Larman).
46
Conjetura de Hirsch Programación lineal ¿Por qué n − d? La construcción Mejoras/limitaciones Otras aproximaciones
Fin
G R A C I A S !
47