Conjectura de Hirsch

En optimisació i en combinatoria polièdrica, la conjectura de Hirsch afirma que "si un poliedre està definit per n desigualtats llineals en d variables sempre ha de ser possible viajar de qualsevol vèrtiç a qualsevol atre vèrtiç recorrent com molt n-d arestes". En térmens una miqueta més tècnics, afirma que el grafo d'arestes-vèrtiços d'un politopo de n-cares en un espai euclidiano d-dimensional té un diàmetro no major que n − d. És dir, que qualsevol de dos vèrtiços del politopo deuen estar conectats l'un en l'atre per una trayectòria de llongitut n − d com a màxim. La conjectura va ser presentada primer en 1957 en una carta de Warren M. Hirsch a George B. Dantzig i és motivada per l'anàlisis del método simplex en programació llineal, a mida que el diàmetro d'un politopo proporciona un llímit més baix en el número de passos necessaris pel método simplex.

La conjectura de Hirsch va ser provada per a d < 4 i per a varis casos especials, els llímits superiors més coneguts varen mostrar solament que els politopos tenen un diàmetro sub-exponencial en funció de n i d. no obstant, despuix de més de cinquanta anys, un contraeixemple va ser anunciat en maig de 2010 per Francisco Sants Leal, de l'Universitat de Cantàbria. el resultat deu ser presentat en la conferència 100 Years in Seattle: The Mathematics of Klee and Grünbaum. Vàries formulació equivalents del problema havien segut donades, per eixemple la conjectura d-passe, que indica que el diàmetro de qualsevol politopo de 2d-cares en un espai euclidiano d-dimensional no és major que d. La conjectura de d-passe era coneguda com a verdadera per a d < 6, pero quan va ser trobat un contraeixemple el cas general també va ser refutado, usant un politopo 43-dimensional de 86 cares en un diàmetro de més de 43. El contraeixemple anunciat no tindria cap conseqüència directa per a l'anàlisis del método simplex, puix no eliminaria la possibilitat d'un més gran pero encara llineal o un número polinòmic de passos.

Referències

• .
• «Francisco Sants Disproves the Hirsch Conjecture». Consultat el 11 de maig de 2010.
• .
• .

• .
• .
• .

Vore també

• Warren M. Hirsch
• Método simplex
• Programació llineal
• Gil Kalai
• Francisco Sants Leal