A counterexample to the Hirsch Conjecture

Abstract

The Hirsch Conjecture (1957) stated that the graph of a $d$-dimensional polytope with $n$ facets cannot have (combinatorial) diameter greater than $n-d$. That is, any two vertices of the polytope can be connected by a path of at most $n-d$ edges.
This paper presents the first counterexample to the conjecture. Our polytope has dimension $43$ and $86$ facets. It is obtained from a $5$-dimensional polytope with $48$ facets that violates a certain generalization of the $d$-step conjecture of Klee and Walkup.

  • [Barnette] Go to document D. Barnette, "$W_{v}$ paths on 3-polytopes," J. Combinatorial Theory, vol. 7, pp. 62-70, 1969.
    @article {Barnette, MRKEY = {0248636},
      AUTHOR = {Barnette, David},
      TITLE = {{$W\sb{v}$} paths on 3-polytopes},
      JOURNAL = {J. Combinatorial Theory},
      VOLUME = {7},
      YEAR = {1969},
      PAGES = {62--70},
      MRCLASS = {52.10},
      MRNUMBER = {0248636},
      MRREVIEWER = {G. D. Chakerian},
      ZBLNUMBER = {0177.26804},
      DOI = {10.1016/S0021-9800(69)80007-4},
     }
  • [Barnette-LBT] Go to document D. Barnette, "A proof of the lower bound conjecture for convex polytopes," Pacific J. Math., vol. 46, pp. 349-354, 1973.
    @article {Barnette-LBT, MRKEY = {0328773},
      AUTHOR = {Barnette, David},
      TITLE = {A proof of the lower bound conjecture for convex polytopes},
      JOURNAL = {Pacific J. Math.},
      FJOURNAL = {Pacific Journal of Mathematics},
      VOLUME = {46},
      YEAR = {1973},
      PAGES = {349--354},
      ISSN = {0030-8730},
      MRCLASS = {52A25},
      MRNUMBER = {0328773},
      MRREVIEWER = {E. Jucovic},
      ZBLNUMBER = {0264.52006},
      URL = {http://projecteuclid.org/euclid.pjm/1102946311},
     }
  • [Barnette2] Go to document D. Barnette, "An upper bound for the diameter of a polytope," Discrete Math., vol. 10, pp. 9-13, 1974.
    @article {Barnette2, MRKEY = {0355826},
      AUTHOR = {Barnette, David},
      TITLE = {An upper bound for the diameter of a polytope},
      JOURNAL = {Discrete Math.},
      FJOURNAL = {Discrete Mathematics},
      VOLUME = {10},
      YEAR = {1974},
      PAGES = {9--13},
      ISSN = {0012-365X},
      MRCLASS = {52A25},
      MRNUMBER = {0355826},
      MRREVIEWER = {P. McMullen},
      ZBLNUMBER = {0294.52007},
      DOI = {10.1016/0012-365X(74)90016-8},
     }
  • [BlindBlind] Go to document G. Blind and R. Blind, "The cubical $d$-polytopes with fewer than $2^{d+1}$ vertices," Discrete Comput. Geom., vol. 13, iss. 3-4, pp. 321-345, 1995.
    @article {BlindBlind, MRKEY = {1318781},
      AUTHOR = {Blind, G. and Blind, R.},
      TITLE = {The cubical {$d$}-polytopes with fewer than {$2\sp {d+1}$} vertices},
      JOURNAL = {Discrete Comput. Geom.},
      FJOURNAL = {Discrete \& Computational Geometry. An International Journal of Mathematics and Computer Science},
      VOLUME = {13},
      YEAR = {1995},
      NUMBER = {3-4},
      PAGES = {321--345},
      ISSN = {0179-5376},
      CODEN = {DCGEER},
      MRCLASS = {52B05},
      MRNUMBER = {1318781},
      MRREVIEWER = {Margaret M. Bayer},
      DOI = {10.1007/BF02574048},
      ZBLNUMBER = {0824.52013},
      }
  • [BCSS] L. Blum, F. Cucker, M. Shub, and S. Smale, Complexity and Real Computation, New York: Springer-Verlag, 1998.
    @book {BCSS, MRKEY = {1479636},
      AUTHOR = {Blum, Lenore and Cucker, Felipe and Shub, Michael and Smale, Steve},
      TITLE = {Complexity and Real Computation},
      PUBLISHER = {Springer-Verlag},
      ADDRESS = {New York},
      YEAR = {1998},
      PAGES = {xvi+453},
      ISBN = {0-387-98281-7},
      MRCLASS = {68Q15 (03D15 13P99 14P99 65Y20 68-02)},
      MRNUMBER = {1479636},
      MRREVIEWER = {Klaus Meer},
      ZBLCOMMENT = {BIBPROC: YEAR doesn't match found ZBLNUMBER},
      ZBLNUMBER = {0948.68068},
      ZBLNUMBER = {0872.68036},
      }
  • [BSS] Go to document L. Blum, M. Shub, and S. Smale, "On a theory of computation and complexity over the real numbers: ${NP}$-completeness, recursive functions and universal machines," Bull. Amer. Math. Soc., vol. 21, iss. 1, pp. 1-46, 1989.
    @article {BSS, MRKEY = {0974426},
      AUTHOR = {Blum, Lenore and Shub, Mike and Smale, Steve},
      TITLE = {On a theory of computation and complexity over the real numbers: ${NP}$-completeness, recursive functions and universal machines},
      JOURNAL = {Bull. Amer. Math. Soc.},
      FJOURNAL = {American Mathematical Society. Bulletin. New Series},
      VOLUME = {21},
      YEAR = {1989},
      NUMBER = {1},
      PAGES = {1--46},
      ISSN = {0273-0979},
      CODEN = {BAMOAD},
      MRCLASS = {68Q10 (03D15 03D75 03D80 03F60 68Q15 68Q25)},
      MRNUMBER = {0974426},
      MRREVIEWER = {John Michael Robson},
      DOI = {10.1090/S0273-0979-1989-15750-9},
      ZBLNUMBER = {0681.03020},
      }
  • [Borgwardt-book] K. Borgwardt, The Simplex Method. A Probabilistic Analysis, New York: Springer-Verlag, 1987, vol. 1.
    @book {Borgwardt-book, MRKEY = {0868467},
      AUTHOR = {Borgwardt, Karl-Heinz},
      TITLE = {The Simplex Method. A Probabilistic Analysis},
      SERIES = {Algorithms and Combin.},
      VOLUME = {1},
      PUBLISHER = {Springer-Verlag},
      ADDRESS = {New York},
      YEAR = {1987},
      PAGES = {xii+268},
      ISBN = {3-540-17096-0},
      MRCLASS = {90C05},
      MRNUMBER = {0868467},
      MRREVIEWER = {J{ü}rgen K{ö}hler},
      ZBLNUMBER = {0604.90092},
      }
  • [Bremner:MoreBounds] Go to document D. Bremner, A. Deza, W. Hua, and L. Schewe, More bounds on the diameter of convex polytopes, 2009.
    @misc {Bremner:MoreBounds,
      author={Bremner, David and Deza, A. and Hua, W. and Schewe, L.},
      TITLE={More bounds on the diameter of convex polytopes},
      NOTE={{\it Optimization Methods and Software},
      to appear},
      DOI={10.1080/10556788.2012.668906},
      ARXIV={0911.4982},
      YEAR={2009},
      }
  • [Bremner:DiameterFewFacets] Go to document D. Bremner and L. Schewe, "Edge-graph diameter bounds for convex polytopes with few facets," Exp. Math., vol. 20, iss. 3, pp. 229-237, 2011.
    @article {Bremner:DiameterFewFacets, MRKEY = {2836249},
      AUTHOR = {Bremner, David and Schewe, Lars},
      TITLE = {Edge-graph diameter bounds for convex polytopes with few facets},
      JOURNAL = {Exp. Math.},
      FJOURNAL = {Experimental Mathematics},
      VOLUME = {20},
      YEAR = {2011},
      NUMBER = {3},
      PAGES = {229--237},
      ISSN = {1058-6458},
      MRCLASS = {52B05 (05B35 52B40)},
      MRNUMBER = {2836249},
      DOI = {10.1080/10586458.2011.564965},
      }
  • [Dantzig-simplex] G. B. Dantzig, "Maximization of a linear function of variables subject to linear inequalities," in Activity Analysis of Production and Allocation, New York, N. Y.: John Wiley & Sons, 1951, vol. 13, pp. 339-347.
    @incollection {Dantzig-simplex, MRKEY = {0056260},
      AUTHOR = {Dantzig, George B.},
      TITLE = {Maximization of a linear function of variables subject to linear inequalities},
      BOOKTITLE = {Activity {A}nalysis of {P}roduction and {A}llocation},
      SERIES = {Cowles Commission Monogr.},
      VOLUME={13},
      PAGES = {339--347},
      PUBLISHER = {John Wiley \& Sons},
      ADDRESS = {New York, N. Y.},
      YEAR = {1951},
      MRCLASS = {90.0X},
      MRNUMBER = {0056260},
      MRREVIEWER = {H. W. Kuhn},
      ZBLNUMBER = {0045.09802},
      }
  • [Dantzig-book] G. B. Dantzig, Linear Programming and Extensions, Princeton, NJ: Princeton Univ. Press, 1998.
    @book {Dantzig-book, MRKEY = {1658673},
      AUTHOR = {Dantzig, George B.},
      TITLE = {Linear Programming and Extensions},
      SERIES = {Princeton Landmarks in Math.},
      PUBLISHER = {Princeton Univ. Press},
      ADDRESS = {Princeton, NJ},
      YEAR = {1998},
      PAGES = {xviii+627},
      ISBN = {0-691-05913-6},
      MRCLASS = {90-01 (90-02 90C05)},
      MRNUMBER = {1658673},
      ZBLNUMBER = {0997.90504},
      }
  • [triang-book] J. A. De Loera, J. Rambau, and F. Santos, Triangulations: Structures for Algorithms and Applications, New York: Springer-Verlag, 2010, vol. 25.
    @book {triang-book, MRKEY = {2743368},
      AUTHOR = {De Loera, Jes{ú}s A. and Rambau, J{ö}rg and Santos, Francisco},
      TITLE = {Triangulations: Structures for Algorithms and Applications},
      SERIES = {Algorithms Comput. Math.},
      VOLUME = {25},
      PUBLISHER = {Springer-Verlag},
      ADDRESS = {New York},
      YEAR = {2010},
      PAGES = {xiv+535},
      ISBN = {978-3-642-12970-4},
      MRCLASS = {52B55 (05C10 52B05 57Q15 68U05)},
      MRNUMBER = {2743368},
      ZBLNUMBER = {1207.52002},
      }
  • [Dongarra-Sullivan-topten] Go to document J. Dongarra and F. Sullivan, "Guest Editors’ Introduction: The Top 10 Algorithms," Comput. Sci. Eng., vol. 2, pp. 22-23, 2000.
    @article{Dongarra-Sullivan-topten,
      author={Dongarra, J. and Sullivan, F.},
      TITLE={Guest Editors' Introduction: {T}he Top 10 Algorithms},
      JOURNAL={Comput.~Sci.~Eng.},
      VOLUME={2},
      YEAR={2000},
      PAGES={22--23},
      DOI = {10.1109/MCISE.2000.814652},
     }
  • [Eisenbrand:limits-of-abstraction] Go to document F. Eisenbrand, N. Hähnle, A. Razborov, and T. Rothvoß, "Diameter of polyhedra: limits of abstraction," Math. Oper. Res., vol. 35, iss. 4, pp. 786-794, 2010.
    @article {Eisenbrand:limits-of-abstraction, MRKEY = {2777514},
      AUTHOR = {Eisenbrand, Friedrich and H{ä}hnle, Nicolai and Razborov, Alexander and Rothvoß,
      Thomas},
      TITLE = {Diameter of polyhedra: limits of abstraction},
      JOURNAL = {Math. Oper. Res.},
      FJOURNAL = {Mathematics of Operations Research},
      VOLUME = {35},
      YEAR = {2010},
      NUMBER = {4},
      PAGES = {786--794},
      ISSN = {0364-765X},
      MRCLASS = {52B05 (05B40 05C12 05C90)},
      MRNUMBER = {2777514},
      MRREVIEWER = {Ren Ding},
      DOI = {10.1287/moor.1100.0470},
      ZBLNUMBER = {1226.52004},
      }
  • [Fogel-Halperin-Weibel] Go to document E. Fogel, D. Halperin, and C. Weibel, "On the exact maximum complexity of Minkowski sums of polytopes," Discrete Comput. Geom., vol. 42, iss. 4, pp. 654-669, 2009.
    @article {Fogel-Halperin-Weibel, MRKEY = {2556461},
      AUTHOR = {Fogel, Efi and Halperin, Dan and Weibel, Christophe},
      TITLE = {On the exact maximum complexity of {M}inkowski sums of polytopes},
      JOURNAL = {Discrete Comput. Geom.},
      FJOURNAL = {Discrete \& Computational Geometry. An International Journal of Mathematics and Computer Science},
      VOLUME = {42},
      YEAR = {2009},
      NUMBER = {4},
      PAGES = {654--669},
      ISSN = {0179-5376},
      CODEN = {DCGEER},
      MRCLASS = {52C45},
      MRNUMBER = {2556461},
      MRREVIEWER = {M{á}rton Nasz{ó}di},
      DOI = {10.1007/s00454-009-9159-1},
      ZBLNUMBER = {1207.52012},
      }
  • [Friedman] Go to document O. Friedmann, "A subexponential lower bound for Zadeh’s pivoting rule for solving linear programs and games," in Integer Programming and Combinatorial Optimization, 15th International Conference, New York, 2011, pp. 192-206.
    @inproceedings{Friedman,
      author={Friedmann, O.},
      TITLE={A subexponential lower bound for {Z}adeh's pivoting rule for solving linear programs and games},
      BOOKTITLE={Integer Programming and Combinatorial Optimization, 15th International Conference},
      VENUE={IPCO 2011, New York, NY},
      SERIES={Lect. Notes Comp. Sci.},
      VOLUME={6655},
      PUBLISHER={Springer-Verlag},
      ADDRESS={New York},
      YEAR={2011},
      PAGES={192--206},
      DOI = {10.1007/978-3-642-20807-2_16},
     }
  • [Friedman-Hansen-Zwick] Go to document O. Friedmann, T. Hansen, and U. Zwick, "Subexponential lower bounds for randomized pivoting rules for the simplex algorithm," in STOC ’11:Proceedings of the 43rd Annual ACM Symposium on Theory of Computing, New York, 2011, pp. 283-292.
    @inproceedings{Friedman-Hansen-Zwick,
      author={Friedmann, O. and Hansen, T. and Zwick, U.},
      TITLE={Subexponential lower bounds for randomized pivoting rules for the simplex algorithm},
      BOOKTITLE={STOC '11:Proceedings of the 43rd Annual ACM Symposium on Theory of Computing},
      VENUE={San Jose, California},
      PUBLISHER={ACM},
      ADDRESS={New York},
      YEAR={2011},
      PAGES={283--292},
      DOI = {10.1145/1993636.1993675},
     }
  • [polymake] E. Gawrilow and M. Joswig, "Polymake: a framework for analyzing convex polytopes," in Polytopes—Combinatorics and Computation, Basel: Birkhäuser, 2000, vol. 29, pp. 43-73.
    @incollection {polymake, MRKEY = {1785292},
      AUTHOR = {Gawrilow, Ewgenij and Joswig, Michael},
      TITLE = {Polymake: a framework for analyzing convex polytopes},
      BOOKTITLE = {Polytopes---Combinatorics and Computation},
      VENUE={{O}berwolfach, 1997},
      SERIES = {DMV Sem.},
      VOLUME = {29},
      PAGES = {43--73},
      PUBLISHER = {Birkhäuser},
      ADDRESS = {Basel},
      YEAR = {2000},
      MRCLASS = {52B55 (68U05)},
      MRNUMBER = {1785292},
      ZBLNUMBER = {0960.68182},
      }
  • [GritzmannKlee] P. Gritzmann and V. Klee, "Mathematical programming and convex geometry," in Handbook of Convex Geometry, Vol. A, B, Amsterdam: North-Holland, 1993, pp. 627-674.
    @incollection {GritzmannKlee, MRKEY = {1242992},
      AUTHOR = {Gritzmann, Peter and Klee, Victor},
      TITLE = {Mathematical programming and convex geometry},
      BOOKTITLE = {Handbook of Convex Geometry, {V}ol. {A},
      {B}},
      PAGES = {627--674},
      PUBLISHER = {North-Holland},
      ADDRESS = {Amsterdam},
      YEAR = {1993},
      MRCLASS = {52A41 (90C05 90C25)},
      MRNUMBER = {1242992},
      MRREVIEWER = {Mark E. Hartmann},
      ZBLNUMBER = {0806.90098},
      }
  • [Grunbaum-book] B. Grünbaum, Convex Polytopes, Second ed., New York: Springer-Verlag, 2003, vol. 221.
    @book {Grunbaum-book, MRKEY = {1976856},
      AUTHOR = {Gr{ü}nbaum, Branko},
      TITLE = {Convex Polytopes},
      SERIES = {Grad. Texts in Math.},
      VOLUME = {221},
      EDITION = {Second},
      NOTE = {prepared and with a preface by Volker Kaibel, Victor Klee and G{ü}nter M. Ziegler},
      PUBLISHER = {Springer-Verlag},
      ADDRESS = {New York},
      YEAR = {2003},
      PAGES = {xvi+468},
      ISBN = {0-387-00424-6; 0-387-40409-0},
      MRCLASS = {52-01 (52Bxx)},
      MRNUMBER = {1976856},
      MRREVIEWER = {Alexander Zvonkin},
      ZBLNUMBER = {1024.52001},
     }
  • [Khachiyan] L. G. Havcijan, "A polynomial algorithm in linear programming," Dokl. Akad. Nauk SSSR, vol. 244, iss. 5, pp. 1093-1096, 1979.
    @article {Khachiyan, MRKEY = {0522052},
      AUTHOR = {Ha{\v{c}}ijan, L. G.},
      TITLE = {A polynomial algorithm in linear programming},
      JOURNAL = {Dokl. Akad. Nauk SSSR},
      FJOURNAL = {Doklady Akademii Nauk SSSR},
      VOLUME = {244},
      YEAR = {1979},
      NUMBER = {5},
      PAGES = {1093--1096},
      ISSN = {0002-3264},
      MRCLASS = {90C05},
      MRNUMBER = {0522052},
      MRREVIEWER = {M. Stef{\u{a}}nescu},
      ZBLNUMBER = {0414.90086},
     }
  • [Hahnle:polymath3] Go to document N. Hähnle, Post in G.~Kalai, Polymath 3: Polynomial Hirsch Conjecture, 2010.
    @misc{Hahnle:polymath3,
      author={Hähnle, N.},
      TITLE={post in {G}.~{K}alai, \textit{{P}olymath} {\bf 3}: {P}olynomial {H}irsch {C}onjecture},
      YEAR={2010},
      URL = {http://gilkalai.wordpress.com/2010/09/29/polymath-3-polynomial-hirsch-conjecture/},
     }
  • [Holt:Many-polytopes] Go to document F. B. Holt and V. Klee, "Many polytopes meeting the conjectured Hirsch bound," Discrete Comput. Geom., vol. 20, iss. 1, pp. 1-17, 1998.
    @article {Holt:Many-polytopes, MRKEY = {1626691},
      AUTHOR = {Holt, F. B. and Klee, V.},
      TITLE = {Many polytopes meeting the conjectured {H}irsch bound},
      JOURNAL = {Discrete Comput. Geom.},
      FJOURNAL = {Discrete \& Computational Geometry. An International Journal of Mathematics and Computer Science},
      VOLUME = {20},
      YEAR = {1998},
      NUMBER = {1},
      PAGES = {1--17},
      ISSN = {0179-5376},
      CODEN = {DCGEER},
      MRCLASS = {52B05 (52B11)},
      MRNUMBER = {1626691},
      MRREVIEWER = {P. R. Goodey},
      DOI = {10.1007/PL00009372},
      ZBLNUMBER = {0926.52013},
      }
  • [JoswigZiegler] Go to document M. Joswig and G. M. Ziegler, "Neighborly cubical polytopes," Discrete Comput. Geom., vol. 24, iss. 2-3, pp. 325-344, 2000.
    @article {JoswigZiegler, MRKEY = {1758054},
      AUTHOR = {Joswig, M. and Ziegler, G. M.},
      TITLE = {Neighborly cubical polytopes},
      JOURNAL = {Discrete Comput. Geom.},
      FJOURNAL = {Discrete \& Computational Geometry. An International Journal of Mathematics and Computer Science},
      VOLUME = {24},
      YEAR = {2000},
      NUMBER = {2-3},
      PAGES = {325--344},
      ISSN = {0179-5376},
      CODEN = {DCGEER},
      MRCLASS = {52B05 (52B40)},
      MRNUMBER = {1758054},
      DOI = {10.1007/s004540010039},
      ZBLNUMBER = {1066.52012},
      }
  • [Kalai:Quasi-polynomial] Go to document G. Kalai and D. J. Kleitman, "A quasi-polynomial bound for the diameter of graphs of polyhedra," Bull. Amer. Math. Soc., vol. 26, iss. 2, pp. 315-316, 1992.
    @article {Kalai:Quasi-polynomial, MRKEY = {1130448},
      AUTHOR = {Kalai, Gil and Kleitman, Daniel J.},
      TITLE = {A quasi-polynomial bound for the diameter of graphs of polyhedra},
      JOURNAL = {Bull. Amer. Math. Soc.},
      FJOURNAL = {American Mathematical Society. Bulletin. New Series},
      VOLUME = {26},
      YEAR = {1992},
      NUMBER = {2},
      PAGES = {315--316},
      ISSN = {0273-0979},
      CODEN = {BAMOAD},
      MRCLASS = {52B55},
      MRNUMBER = {1130448},
      MRREVIEWER = {W. J. Firey},
      DOI = {10.1090/S0273-0979-1992-00285-9},
      ZBLNUMBER = {0751.52006},
      }
  • [Karmarkar] Go to document N. Karmarkar, "A new polynomial-time algorithm for linear programming," Combinatorica, vol. 4, iss. 4, pp. 373-395, 1984.
    @article {Karmarkar, MRKEY = {0779900},
      AUTHOR = {Karmarkar, N.},
      TITLE = {A new polynomial-time algorithm for linear programming},
      JOURNAL = {Combinatorica},
      FJOURNAL = {Combinatorica. An International Journal of the János Bolyai Mathematical Society},
      VOLUME = {4},
      YEAR = {1984},
      NUMBER = {4},
      PAGES = {373--395},
      ISSN = {0209-9683},
      CODEN = {COMBDI},
      MRCLASS = {90C05},
      MRNUMBER = {0779900},
      MRREVIEWER = {K. G. Murty},
      DOI = {10.1007/BF02579150},
      ZBLNUMBER = {0557.90065},
      }
  • [Kim-Santos-update] Go to document E. D. Kim and F. Santos, "An update on the Hirsch conjecture," Jahresber. Dtsch. Math.-Ver., vol. 112, iss. 2, pp. 73-98, 2010.
    @article {Kim-Santos-update, MRKEY = {2681516},
      AUTHOR = {Kim, Edward D. and Santos, Francisco},
      TITLE = {An update on the {H}irsch conjecture},
      JOURNAL = {Jahresber. Dtsch. Math.-Ver.},
      FJOURNAL = {Jahresbericht der Deutschen Mathematiker-Vereinigung},
      VOLUME = {112},
      YEAR = {2010},
      NUMBER = {2},
      PAGES = {73--98},
      ISSN = {0012-0456},
      MRCLASS = {52B05 (05C10 05C12 90C08)},
      MRNUMBER = {2681516},
      DOI = {10.1365/s13291-010-0001-8},
      ZBLNUMBER = {05827607},
      }
  • [Kim-Santos-companion] E. D. Kim and F. Santos, Companion to “An update on the Hirsch conjecture".
    @misc {Kim-Santos-companion,
      author = {Kim, Edward D. and Santos, Francisco},
      TITLE = {Companion to ``{A}n update on the {H}irsch conjecture"},
      NOTE={unpublished manuscript, 22 pages, February 2010},
      SORTYEAR={2012},
      ARXIV={0912.4235v2},
      }
  • [Klee:diameters] Go to document V. Klee, "Diameters of polyhedral graphs," Canad. J. Math., vol. 16, pp. 602-614, 1964.
    @article {Klee:diameters, MRKEY = {0165514},
      AUTHOR = {Klee, Victor},
      TITLE = {Diameters of polyhedral graphs},
      JOURNAL = {Canad. J. Math.},
      FJOURNAL = {Canadian Journal of Mathematics. Journal Canadien de Mathématiques},
      VOLUME = {16},
      YEAR = {1964},
      PAGES = {602--614},
      ISSN = {0008-414X},
      MRCLASS = {55.10 (52.10)},
      MRNUMBER = {0165514},
      MRREVIEWER = {W. T. Tutte},
      ZBLNUMBER = {0121.37701},
      DOI = {10.4153/CJM-1964-061-2},
     }
  • [Klee:number-of-vertices] Go to document V. Klee, "On the number of vertices of a convex polytope," Canad. J. Math., vol. 16, pp. 701-720, 1964.
    @article {Klee:number-of-vertices, MRKEY = {0166682},
      AUTHOR = {Klee, Victor},
      TITLE = {On the number of vertices of a convex polytope},
      JOURNAL = {Canad. J. Math.},
      FJOURNAL = {Canadian Journal of Mathematics. Journal Canadien de Mathématiques},
      VOLUME = {16},
      YEAR = {1964},
      PAGES = {701--720},
      ISSN = {0008-414X},
      MRCLASS = {52.10 (52.40)},
      MRNUMBER = {0166682},
      MRREVIEWER = {G. D. Chakerian},
      ZBLNUMBER = {0128.17201},
      DOI = {/10.4153/CJM-1964-067-6}
    }
  • [Klee:PathsII] Go to document V. Klee, "Paths on polyhedra. II," Pacific J. Math., vol. 17, pp. 249-262, 1966.
    @article {Klee:PathsII, MRKEY = {0194982},
      AUTHOR = {Klee, Victor},
      TITLE = {Paths on polyhedra. {II}},
      JOURNAL = {Pacific J. Math.},
      FJOURNAL = {Pacific Journal of Mathematics},
      VOLUME = {17},
      YEAR = {1966},
      PAGES = {249--262},
      ISSN = {0030-8730},
      MRCLASS = {52.10},
      MRNUMBER = {0194982},
      MRREVIEWER = {G. D. Chakerian},
      ZBLNUMBER = {0141.21303},
      URL = {http://projecteuclid.org/euclid.pjm/1102994619},
     }
  • [Klee-grunbaumchapter] V. Klee, Diameters of polytopes, 1967.
    @misc{Klee-grunbaumchapter,
      author={Klee, Victor},
      TITLE={Diameters of polytopes},
      YEAR={1967},
      NOTE={Chapter 16 of~\cite{Grunbaum-book}},
      MRNUMBER = {1976856},
      ZBLNUMBER = {1024.52001},
     }
  • [Klee-Kleinschmidt] Go to document V. Klee and P. Kleinschmidt, "The $d$-step conjecture and its relatives," Math. Oper. Res., vol. 12, iss. 4, pp. 718-755, 1987.
    @article {Klee-Kleinschmidt, MRKEY = {0913867},
      AUTHOR = {Klee, Victor and Kleinschmidt, Peter},
      TITLE = {The {$d$}-step conjecture and its relatives},
      JOURNAL = {Math. Oper. Res.},
      FJOURNAL = {Mathematics of Operations Research},
      VOLUME = {12},
      YEAR = {1987},
      NUMBER = {4},
      PAGES = {718--755},
      ISSN = {0364-765X},
      MRCLASS = {52A25 (52A40 90C10)},
      MRNUMBER = {0913867},
      MRREVIEWER = {G. Ewald},
      DOI = {10.1287/moor.12.4.718},
      ZBLNUMBER = {0632.52007},
      }
  • [Klee:d-step] Go to document V. Klee and D. W. Walkup, "The $d$-step conjecture for polyhedra of dimension $d<6$," Acta Math., vol. 117, pp. 53-78, 1967.
    @article {Klee:d-step, MRKEY = {0206823},
      AUTHOR = {Klee, Victor and Walkup, David W.},
      TITLE = {The {$d$}-step conjecture for polyhedra of dimension {$d<6$}},
      JOURNAL = {Acta Math.},
      FJOURNAL = {Acta Mathematica},
      VOLUME = {117},
      YEAR = {1967},
      PAGES = {53--78},
      ISSN = {0001-5962},
      MRCLASS = {52.40 (52.10)},
      MRNUMBER = {0206823},
      MRREVIEWER = {G. T. Sallee},
      ZBLNUMBER = {0163.16801},
      DOI = {10.1007/BF02395040},
     }
  • [Larman] Go to document D. G. Larman, "Paths of polytopes," Proc. London Math. Soc., vol. 20, pp. 161-178, 1970.
    @article {Larman, MRKEY = {0254735},
      AUTHOR = {Larman, D. G.},
      TITLE = {Paths of polytopes},
      JOURNAL = {Proc. London Math. Soc.},
      FJOURNAL = {Proceedings of the London Mathematical Society. Third Series},
      VOLUME = {20},
      YEAR = {1970},
      PAGES = {161--178},
      ISSN = {0024-6115},
      MRCLASS = {52.10},
      MRNUMBER = {0254735},
      MRREVIEWER = {P. McMullen},
      ZBLNUMBER = {0199.59301},
      DOI = {10.1112/plms/s3-20.1.161},
     }
  • [5prismatoids] B. Matschke, F. Santos, and C. Weibel, The width of 5-prismatoids, 2012.
    @misc{5prismatoids,
      author={Matschke, B. and Santos, F. and Weibel, C.},
      TITLE={The width of 5-prismatoids},
      NOTE={preprint},
      YEAR={2012},
      ARXIV={1202.4701},
      }
  • [Megiddo:SurveyLPComplexity] N. Megiddo, "On the complexity of linear programming," in Advances in Economic Theory, Cambridge: Cambridge Univ. Press, 1989, vol. 12, pp. 225-268.
    @incollection {Megiddo:SurveyLPComplexity, MRKEY = {1117042},
      AUTHOR = {Megiddo, Nimrod},
      TITLE = {On the complexity of linear programming},
      BOOKTITLE = {Advances in Economic Theory},
      VENUE={{C}ambridge, {MA},
      1985},
      SERIES = {Econom. Soc. Monogr.},
      VOLUME = {12},
      PAGES = {225--268},
      PUBLISHER = {Cambridge Univ. Press},
      ADDRESS = {Cambridge},
      YEAR = {1989},
      MRCLASS = {90C05 (90C60)},
      MRNUMBER = {1117042},
      ZBLNUMBER = {0735.90044},
      }
  • [ProvanBillera] Go to document S. J. Provan and L. J. Billera, "Decompositions of simplicial complexes related to diameters of convex polyhedra," Math. Oper. Res., vol. 5, iss. 4, pp. 576-594, 1980.
    @article {ProvanBillera, MRKEY = {0593648},
      AUTHOR = {Provan, J. Scott and Billera, Louis J.},
      TITLE = {Decompositions of simplicial complexes related to diameters of convex polyhedra},
      JOURNAL = {Math. Oper. Res.},
      FJOURNAL = {Mathematics of Operations Research},
      VOLUME = {5},
      YEAR = {1980},
      NUMBER = {4},
      PAGES = {576--594},
      ISSN = {0364-765X},
      MRCLASS = {52A25 (90C05)},
      MRNUMBER = {0593648},
      MRREVIEWER = {J. Parida},
      DOI = {10.1287/moor.5.4.576},
      ZBLNUMBER = {0457.52005},
      }
  • [4prismatoids] Go to document F. Santos, T. Stephen, and H. Thomas, "Embedding a pair of graphs in a surface, and the width of 4-dimensional prismatoids," Discrete Comput. Geom., vol. 47, iss. 3, pp. 569-576, 2012.
    @article {4prismatoids,
      author = {Santos, Francisco and Stephen, Tamon and Thomas, Hugh},
      TITLE = {Embedding a pair of graphs in a surface, and the width of 4-dimensional prismatoids},
      JOURNAL = {Discrete Comput. Geom.},
      FJOURNAL = {Discrete \& Computational Geometry. An International Journal of Mathematics and Computer Science},
      VOLUME = {47},
      YEAR = {2012},
      NUMBER = {3},
      PAGES = {569--576},
      ISSN = {0179-5376},
      CODEN = {DCGEER},
      MRCLASS = {Preliminary Data},
      DOI = {10.1007/s00454-011-9361-9},
      ZBLNUMBER = {06021994},
      }
  • [Smale] S. Smale, "Mathematical problems for the next century," in Mathematics: Frontiers and Perspectives, Providence, RI: Amer. Math. Soc., 2000, pp. 271-294.
    @incollection {Smale, MRKEY = {1754783},
      AUTHOR = {Smale, Steve},
      TITLE = {Mathematical problems for the next century},
      BOOKTITLE = {Mathematics: Frontiers and Perspectives},
      PAGES = {271--294},
      PUBLISHER = {Amer. Math. Soc.},
      ADDRESS = {Providence, RI},
      YEAR = {2000},
      MRCLASS = {00A05 (00-02 01A61 01A67)},
      MRNUMBER = {1754783},
      ZBLNUMBER = {1031.00005},
      }
  • [Spielman:WhySimplexUsually] Go to document D. A. Spielman and S. Teng, "Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time," J. ACM, vol. 51, iss. 3, pp. 385-463, 2004.
    @article {Spielman:WhySimplexUsually, MRKEY = {2145860},
      AUTHOR = {Spielman, Daniel A. and Teng, Shang-Hua},
      TITLE = {Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time},
      JOURNAL = {J. ACM},
      FJOURNAL = {Journal of the ACM},
      VOLUME = {51},
      YEAR = {2004},
      NUMBER = {3},
      PAGES = {385--463},
      ISSN = {0004-5411},
      MRCLASS = {90C05 (68W40 90C60)},
      MRNUMBER = {2145860},
      MRREVIEWER = {Panos M. Pardalos},
      DOI = {10.1145/990308.990310},
      ZBLNUMBER = {1192.90120},
      }
  • [Terlaky-Zhang] Go to document T. Terlaky and S. Z. Zhang, "Pivot rules for linear programming: A survey on recent theoretical developments. Degeneracy in optimization problems," Ann. Oper. Res., vol. 46/47, iss. 1-4, pp. 203-233, 1993.
    @article {Terlaky-Zhang, MRKEY = {1260019},
      AUTHOR = {Terlaky, Tam{á}s and Zhang, Shu Zhong},
      TITLE = {Pivot rules for linear programming: A survey on recent theoretical developments. Degeneracy in optimization problems},
      JOURNAL = {Ann. Oper. Res.},
      FJOURNAL = {Annals of Operations Research},
      VOLUME = {46/47},
      YEAR = {1993},
      NUMBER = {1-4},
      PAGES = {203--233},
      ISSN = {0254-5330},
      MRCLASS = {90C05 (90-02)},
      MRNUMBER = {1260019},
      DOI = {10.1007/BF02096264},
      ZBLNUMBER = {0793.90034},
      }
  • [Todd:MonotonicBoundedHirsch] Go to document M. J. Todd, "The monotonic bounded Hirsch conjecture is false for dimension at least $4$," Math. Oper. Res., vol. 5, iss. 4, pp. 599-601, 1980.
    @article {Todd:MonotonicBoundedHirsch, MRKEY = {0593650},
      AUTHOR = {Todd, Michael J.},
      TITLE = {The monotonic bounded {H}irsch conjecture is false for dimension at least {$4$}},
      JOURNAL = {Math. Oper. Res.},
      FJOURNAL = {Mathematics of Operations Research},
      VOLUME = {5},
      YEAR = {1980},
      NUMBER = {4},
      PAGES = {599--601},
      ISSN = {0364-765X},
      MRCLASS = {52A25 (90C05)},
      MRNUMBER = {0593650},
      MRREVIEWER = {J. Parida},
      DOI = {10.1287/moor.5.4.599},
      ZBLNUMBER = {0457.52006},
      }
  • [Todd:Dantzig] Go to document M. J. Todd, "Book review on “The basic George B. Dantzig” (by Richard W.~Cottle, Stanford University Press, Stanford, California, 2003)," Bull. Amer. Math. Soc., vol. 48, iss. 1, pp. 123-129, 2011.
    @article {Todd:Dantzig, MRKEY = {2731656},
      AUTHOR = {Todd, Michael J.},
      TITLE = {book review on ``{T}he basic {G}eorge {B}. {D}antzig'' (by {R}ichard {W}.~{C}ottle, {S}tanford {U}niversity {P}ress, {S}tanford, {C}alifornia, 2003)},
      JOURNAL = {Bull. Amer. Math. Soc.},
      FJOURNAL = {American Mathematical Society. Bulletin. New Series},
      VOLUME = {48},
      YEAR = {2011},
      NUMBER = {1},
      PAGES = {123--129},
      ISSN = {0273-0979},
      CODEN = {BAMOAD},
      MRCLASS = {00A17},
      MRNUMBER = {2731656},
      DOI = {10.1090/S0273-0979-2010-01303-3},
      }
  • [Ziegler:LecturesPolytopes] G. M. Ziegler, Lectures on Polytopes, New York: Springer-Verlag, 1995, vol. 152.
    @book {Ziegler:LecturesPolytopes, MRKEY = {1311028},
      AUTHOR = {Ziegler, G{ü}nter M.},
      TITLE = {Lectures on Polytopes},
      SERIES = {Grad. Texts in Math.},
      VOLUME = {152},
      PUBLISHER = {Springer-Verlag},
      ADDRESS = {New York},
      YEAR = {1995},
      PAGES = {x+370},
      ISBN = {0-387-94365-X},
      MRCLASS = {52Bxx},
      MRNUMBER = {1311028},
      MRREVIEWER = {Margaret M. Bayer},
      ZBLNUMBER = {0823.52002},
      }

Authors

Francisco Santos

Departamento de Matemáticas
Universidad de Cantabria
Av. de los Castros 48
E-39005 Santander
Spain