Abstract
The Hirsch Conjecture, posed in 1957, stated that the graph of a d-dimensional polytope or polyhedron with n facets cannot have diameter greater than n−d. The conjecture itself has been disproved, but what we know about the underlying question is quite scarce. Most notably, no polynomial upper bound is known for the diameters that were conjectured to be linear. In contrast, no polyhedron violating the conjecture by more than 25 % is known.
This paper reviews several recent attempts and progress on the question. Some work is in the world of polyhedra or (more often) bounded polytopes, but some try to shed light on the question by generalizing it to simplicial complexes. In particular, we include here our recent and previously unpublished proof that the maximum diameter of arbitrary simplicial complexes is in n Θ(d), and we summarize the main ideas in the polymath 3 project, a web-based collective effort trying to prove an upper bound of type nd for the diameters of polyhedra and of more general objects (including, e.g., simplicial manifolds).
Similar content being viewed by others
References
Adiprasito K, Benedetti B (2013, preprint) The Hirsch bound holds for normal flag complexes. http://arxiv.org/abs/1303.3598
Adler I, Dantzig GB (1974) Maximum diameter of abstract polytopes. Math Program Stud 1:20–40. Pivoting and extensions
Altshuler A, Bokowski J, Steinberg L (1980) The classification of simplicial 3-spheres with nine vertices into polytopes and non-polytopes. Discrete Math 31:115–124
Barnette D (1974) An upper bound for the diameter of a polytope. Discrete Math 10:9–13
Betke U (2004) Relaxation, new combinatorial and polynomial algorithms for the linear feasibility problem. Discrete Comput Geom 32(3):317–338
Bonifas N, Di Summa M, Eisenbrand F, Hähnle N, Niemeier M (2012) On sub-determinants and the diameter of polyhedra. In: Proceedings of the 28th annual ACM symposium on computational geometry, SoCG’12, pp 357–362
Bremner D, Deza A, Hua W, Schewe L (2013) More bounds on the diameter of convex polytopes. Optim Methods Softw 28(3):442–450. Special issue in honour of Professor Kees Roos’70th Birthday
Bremner D, Schewe L (2011) Edge-graph diameter bounds for convex polytopes with few facets. Exp Math 20(3):229–237
Chubanov S (2012) A strongly polynomial algorithm for linear systems having a binary solution. Math Program 134(2):533–570
Dantzig GB (1951) Maximization of a linear function of variables subject to linear inequalities. In: Activity analysis of production and allocation, cowles commission monograph no. 13. Wiley, New York, pp 339–347
Dantzig GB (1963) Linear programming and extensions. Princeton University Press, Princeton
De Loera JA (2011) New insights into the complexity and geometry of linear optimization. In: Optima, mathematical optimization society newsletter, vol 87, pp 1–13
De Loera JA, Klee S (2012) Transportation problems and simplicial polytopes that are not weakly vertex-decomposable. Math Oper Res 37(4):670–674
De Loera JA, Rambau J, Santos F (2010) Triangulations: structures for algorithms and applications. Algorithms and computation in mathematics, vol 25. Springer, Berlin
Deza A, Terlaky T, Zinchenko Y (2008) Polytopes and arrangements: diameter and curvature. Oper Res Lett 36(2):215–222
Deza A, Terlaky T, Zinchenko Y (2009a) Central path curvature and iteration-complexity for redundant Klee–Minty cubes. Adv Appl Math Mech 17:223–256
Deza A, Terlaky T, Zinchenko Y (2009b) A continuous d-step conjecture for polytopes. Discrete Comput Geom 41:318–327
Dongarra J, Sullivan F (2000) Guest editors’ introduction: the top 10 algorithms. Comput Sci Eng 2(22):2 pages
Dunagan J, Spielman DA, Teng S-H (2011) Smoothed analysis of condition numbers and complexity implications for linear programming. Math Program, Ser A 126(2):315–350
Dunagan J, Vempala S (2008) A simple polynomial-time rescaling algorithm for solving linear programs. Math Program, Ser A 114(1):101–114
Dyer M, Frieze A (1994) Random walks, totally unimodular matrices, and a randomised dual simplex algorithm. Math Program 64:1–16
Eisenbrand F, Hähnle N, Razborov A, RothvoßT (2010) Diameter of polyhedra: limits of abstraction. Math Oper Res 35(4):786–794
Friedmann O (2011) A subexponential lower bound for Zadeh’s pivoting rule for solving linear programs and games. In: Proceedings of the 15th conference on Integer Programming and Combinatorial Optimization, IPCO’11, New York, NY, USA
Friedmann O, Hansen T, Zwick U (2011) Subexponential lower bounds for randomized pivoting rules for the simplex algorithm. In: Proceedings of the 43rd ACM symposium on theory of computing, STOC’11, San Jose, CA, USA
Goodey PR (1972) Some upper bounds for the diameters of convex polytopes. Isr J Math 11:380–385
Gromov M (1987) Hyperbolic groups. In: Essays in group theory. Math sci res inst publ, vol 8. Springer, New York, pp 75–263
Hähnle N (2012, preprint) Constructing subset partition graphs with strong adjacency and end-point count properties. arXiv:1203.1525
Hähnle N, Klee S, Pilaud V (2013) Obstructions to weak decomposability for simplicial polytopes. Proc Amer Math Soc. To appear. http://arxiv.org/abs/1206.6143
Holton DA, Sheehan J (1993) The Petersen graph. Australian mathematical society lecture series, vol 7. Cambridge University Press, Cambridge
Izmestiev I, Joswig M (2003) Branched coverings, triangulations, and 3-manifolds. Adv Geom 3(2):191–225
Kalai G (1992) Upper bounds for the diameter and height of graphs of convex polyhedra. Discrete Comput Geom 8(4):363–372
Kalai G (coordinator) (2010) Polymath 3: polynomial Hirsch Conjecture. http://gilkalai.wordpress.com/2010/09/29/polymath-3-polynomial-hirsch-conjecture
Kalai G, Kleitman DJ (1992) A quasi-polynomial bound for the diameter of graphs of polyhedra. Bull Am Math Soc 26:315–316
Karmarkar N (1984) A new polynomial-time algorithm for linear programming. Combinatorica 4:373–395
Khaachiyan LG (1979) A polynomial algorithm in linear programming. Dokl Akad Nauk SSSR 244:1093–1096
Kim ED (2013) Polyhedral graph abstractions and an approach to the Linear Hirsch Conjecture. Math Program, Ser A. To appear. http://arxiv.org/abs/1103.3362v1
Kim ED, Santos F (2009, unpublished manuscript) Companion to “An update on the Hirsch Conjecture”. 22 pages. http://arxiv.org/abs/0912.4235
Kim ED, Santos F (2010) An update on the Hirsch Conjecture. Jahresber Dtsch Math-Ver 112(2):73–98
Klee V (1964) Diameters of polyhedral graphs. Can J Math 16:602–614
Klee V (1966) Paths on polyhedra II. Pac J Math 17(2):249–262
Klee V, Kleinschmidt P (1987) The d-step conjecture and its relatives. Math Oper Res 12(4):718–755
Klee V, Minty GJ (1972) How good is the simplex algorithm? In: Inequalities, III, Proc third sympos, Univ. California, Los Angeles, Calif., 1969 Academic Press, New York, pp 159–175. Dedicated to the memory of Theodore S Motzkin
Klee V, Walkup DW (1967) The d-step conjecture for polyhedra of dimension d<6. Acta Math 133:53–78
Kleinschmidt P, Onn S (1992) On the diameter of convex polytopes. Discrete Math 102(1):75–77
Larman DG (1970) Paths on polytopes. Proc Lond Math Soc 20(3):161–178
Matschke B, Santos F, Weibel C (2012, preprint) The width of 5-prismatoids. 28 pages. http://arxiv.org/abs/1202.4701
Naddef D (1989) The Hirsch conjecture is true for (0,1)-polytopes. Math Program 45:109–110
Nash JC (2000) The (Dantzig) simplex method for linear programming. Comput Sci Eng 2(29):3 pages
Provan JS, Billera LJ (1980) Decompositions of simplicial complexes related to diameters of convex polyhedra. Math Oper Res 5(4):576–594
Santos F (2012) A counter-example to the Hirsch Conjecture. Ann Math (2) 176:383–412
Santos F, Stephen T, Thomas H (2012) Embedding a pair of graphs in a surface, and the width of 4-dimensional prismatoids. Discrete Comput Geom 47(3):569–576
Schewe L (2009) Non-realizable minimal vertex triangulations of surfaces: showing non-realizability using oriented matroids and satisfiability solvers. Discrete Comput Geom 43(2):289–302
Smale S (2000) Mathematical problems for the next century. In: Mathematics: frontiers and perspectives. Am Math Soc, Providence, pp 271–294
Todd MJ (1980) The monotonic bounded Hirsch Conjecture is false for dimension at least 4. Math Oper Res 5(4):599–601
Vershynin R (2009) Beyond Hirsch Conjecture: walks on random polytopes and smoothed complexity of the simplex method. SIAM J Comput 39(2):646–678
Ziegler GM (1995) Lectures on polytopes. Graduate texts in mathematics, vol 152. Springer, Berlin
Ziegler GM (2012) Who solved the Hirsch Conjecture? Doc Math. Extra volume: Optimization stories, 75–85
Acknowledgements
I would very much like to thank the two editors of TOP, Miguel Ángel Goberna and Jesús Artalejo, for the invitation to write this paper. Unfortunately, while the paper was being processed, I received the extremely sad news of the passing away of Jesús. Let me send my warmest condolences to his colleagues, friends, and above all, his family.
I also want to thank Jesús De Loera, Steve Klee, Tamás Terlaky, and Miguel Ángel Goberna (again) for sending me comments and typos on the first version of the paper.
Author information
Authors and Affiliations
Corresponding author
Additional information
Work of F. Santos is supported in part by the Spanish Ministry of Science (MICINN) through grant MTM2011-22792 and by the MICINN-ESF EUROCORES programme EuroGIGA—ComPoSe IP04—Project EUI-EURC-2011-4306.
Rights and permissions
About this article
Cite this article
Santos, F. Recent progress on the combinatorial diameter of polytopes and simplicial complexes. TOP 21, 426–460 (2013). https://doi.org/10.1007/s11750-013-0295-7
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11750-013-0295-7