Hirschin hypoteesi

Hirschin arvelu on kumottu arvelu monitahoisen graafin halkaisijasta.

Sanamuoto

-Dimensionaaliselle kuperalle monitaholle , jossa on kasvot, sen reunojen ja kärkien muodostaman graafin halkaisija on enintään . $d$ $n$ $nd$

Toisin sanoen mitkä tahansa kaksi monitahoisen kärkeä voidaan yhdistää toisiinsa enintään reunan ketjua pitkin. $nd$

Hypoteesi muotoiltiin kirjeessä, jonka Warren Hirsch lähetti George Danzigille vuonna 1957.
- Motivaatio tuli lineaarisen ohjelmoinnin simpleksimenetelmän analyysistä .
Hirsch osoitti olettamuksen ulottuvuudessa 3 sekä useissa erikoistapauksissa.
Tiedetään, että yläraja on subeksponentiaalinen ja . $n$ $d$
Toukokuussa 2010 Francisco Santos Leal esitti vastaesimerkin - 43-ulotteisen monitahoisen, jossa on 86 pintaa ja kaavion halkaisija yli 43.
- Kysymys lineaarisen tai polynomisen estimaatin olemassaolosta jää avoimeksi.

Dantzig, George B. (1963), Linear Programming and Extensions , Princeton Univ. Paina . Uusintapainos sarjassa Princeton Landmarks in Mathematics , Princeton University Press, 1998.
Kalai, Gil Francisco Santos kumoaa Hirsch-oletuksen (10. toukokuuta 2010). Haettu 11. toukokuuta 2010. Arkistoitu alkuperäisestä 28. lokakuuta 2019. (määrätön)
Kalai, Gil & Kleitman, Daniel J. (1992), Kvasipolynomi sidottu polyhedrien graafien halkaisijaan , Bulletin of the American Mathematical Society, osa 26 (2): 315–316 , DOI 10.1090/S0273-0979- 1992-00285-9 .
Klee, Victor & Walkup, David W. (1967), The d -step conjecture for polyhedra dimension d < 6 , Acta Mathematica voi. 133: 53-78 , DOI 10.1007/BF02395040 .
Miranda, Eva (2012), Hirsch-oletus on kumottu: Francisco Santosin haastattelu , European Mathematical Societyn uutiskirje (nro 86): 31–36 , < http://www.ems-ph.org/journals /newsletter/pdf/2012-12-86.pdf > Arkistoitu 20. maaliskuuta 2014 Wayback Machinessa .
Naddef, Denis (1989), Hirsch-oletus pätee (0,1)-polytooppeihin , Mathematical Programming osa 45 (1): 109-110 , DOI 10.1007/BF01589099 .
Santos, Francisco (2011), Vastaesimerkki Hirschin olettamukselle , Annals of Mathematics (Princeton University and 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 , voi. 152, Graduate Texts in Mathematics, Springer-Verlag, s. 83-93 .