Hirsch hypotese

Hirschs formodning er en tilbagevist formodning om diameteren af en polyedergraf.

Ordlyd

For et dimensionelt konveks polyeder med flader har grafen dannet af dens kanter og hjørner højst en diameter . $d$ $n$ $nd$

Det vil sige, at alle to hjørner af et polyeder kan forbindes med hinanden langs en kæde på højst kanter. $nd$

Hypotesen blev formuleret i et brev fra Warren Hirsch til George Danzig i 1957.
- Motivationen kom fra analysen af simpleksmetoden i lineær programmering .
Hirsch beviste formodningen i dimension 3, såvel som i flere særlige tilfælde.
Det er kendt, at den øvre grænse er subeksponentiel i og . $n$ $d$
I maj 2010 præsenterede Francisco Santos Leal et modeksempel - et 43-dimensionelt polyeder med 86 flader og en grafdiameter større end 43.
- Spørgsmålet om eksistensen af et lineært eller polynomielt estimat forbliver åbent.

Dantzig, George B. (1963), Lineær programmering og udvidelser , Princeton Univ. Tryk på . Genoptrykt i serien Princeton Landmarks in Mathematics , Princeton University Press, 1998.
Kalai, Gil Francisco Santos modbeviser Hirsch-formodningen (10. maj 2010). Hentet 11. maj 2010. Arkiveret fra originalen 28. oktober 2019. (ubestemt)
Kalai, Gil & Kleitman, Daniel J. (1992), Et kvasi-polynomium bundet til diameteren af grafer for polyedre , Bulletin of the American Mathematical Society bind 26 (2): 315-316 , DOI 10.1090/S0273-0979- 1992-00285-9 .
Klee, Victor & Walkup, David W. (1967), The d -step conjecture for polyhedra of dimension d < 6 , Acta Mathematica bind 133: 53–78 , DOI 10.1007/BF02395040 .
Miranda, Eva (2012), Hirsch-formodningen er blevet modbevist: Et interview med Francisco Santos , Newsletter of the European Mathematical Society (nr. 86): 31–36 , < http://www.ems-ph.org/journals /newsletter/pdf/2012-12-86.pdf > Arkiveret 20. marts 2014 på Wayback Machine .
Naddef, Denis (1989), Hirsch-formodningen er sand for (0,1)-polytoper , Mathematical Programming bind 45 (1): 109–110 , DOI 10.1007/BF01589099 .
Santos, Francisco (2011), Et modeksempel til Hirsch-formodningen , Annals of Mathematics (Princeton University og Institute for Advanced Study). — T. 176 (1): 383–412 , DOI 10.4007/annals.2012.176.1.7
Ziegler, Günter M. (1994), The Hirsch Conjecture, Lectures on Polytopes , vol. 152, Graduate Texts in Mathematics, Springer-Verlag, s. 83–93 .