Skip to main content
Springer Nature Link
Log in

Recent progress on the combinatorial diameter of polytopes and simplicial complexes

  • Invited Paper
  • Published:
TOP Aims and scope Submit manuscript

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).

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4

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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • Barnette D (1974) An upper bound for the diameter of a polytope. Discrete Math 10:9–13

    Article  Google Scholar 

  • Betke U (2004) Relaxation, new combinatorial and polynomial algorithms for the linear feasibility problem. Discrete Comput Geom 32(3):317–338

    Article  Google Scholar 

  • 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

    Google Scholar 

  • 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

    Article  Google Scholar 

  • Bremner D, Schewe L (2011) Edge-graph diameter bounds for convex polytopes with few facets. Exp Math 20(3):229–237

    Article  Google Scholar 

  • Chubanov S (2012) A strongly polynomial algorithm for linear systems having a binary solution. Math Program 134(2):533–570

    Article  Google Scholar 

  • 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

    Google Scholar 

  • Dantzig GB (1963) Linear programming and extensions. Princeton University Press, Princeton

    Google Scholar 

  • 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

    Google Scholar 

  • De Loera JA, Klee S (2012) Transportation problems and simplicial polytopes that are not weakly vertex-decomposable. Math Oper Res 37(4):670–674

    Article  Google Scholar 

  • De Loera JA, Rambau J, Santos F (2010) Triangulations: structures for algorithms and applications. Algorithms and computation in mathematics, vol 25. Springer, Berlin

    Google Scholar 

  • Deza A, Terlaky T, Zinchenko Y (2008) Polytopes and arrangements: diameter and curvature. Oper Res Lett 36(2):215–222

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • Deza A, Terlaky T, Zinchenko Y (2009b) A continuous d-step conjecture for polytopes. Discrete Comput Geom 41:318–327

    Article  Google Scholar 

  • Dongarra J, Sullivan F (2000) Guest editors’ introduction: the top 10 algorithms. Comput Sci Eng 2(22):2 pages

    Google Scholar 

  • 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

    Article  Google Scholar 

  • Dunagan J, Vempala S (2008) A simple polynomial-time rescaling algorithm for solving linear programs. Math Program, Ser A 114(1):101–114

    Article  Google Scholar 

  • Dyer M, Frieze A (1994) Random walks, totally unimodular matrices, and a randomised dual simplex algorithm. Math Program 64:1–16

    Article  Google Scholar 

  • Eisenbrand F, Hähnle N, Razborov A, RothvoßT (2010) Diameter of polyhedra: limits of abstraction. Math Oper Res 35(4):786–794

    Article  Google Scholar 

  • 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

    Google Scholar 

  • 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

    Google Scholar 

  • Goodey PR (1972) Some upper bounds for the diameters of convex polytopes. Isr J Math 11:380–385

    Article  Google Scholar 

  • Gromov M (1987) Hyperbolic groups. In: Essays in group theory. Math sci res inst publ, vol 8. Springer, New York, pp 75–263

    Chapter  Google Scholar 

  • 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

    Book  Google Scholar 

  • Izmestiev I, Joswig M (2003) Branched coverings, triangulations, and 3-manifolds. Adv Geom 3(2):191–225

    Article  Google Scholar 

  • Kalai G (1992) Upper bounds for the diameter and height of graphs of convex polyhedra. Discrete Comput Geom 8(4):363–372

    Article  Google Scholar 

  • Kalai G (coordinator) (2010) Polymath 3: polynomial Hirsch Conjecture. http://gilkalai.wordpress.com/2010/09/29/polymath-3-polynomial-hirsch-conjecture

    Google Scholar 

  • Kalai G, Kleitman DJ (1992) A quasi-polynomial bound for the diameter of graphs of polyhedra. Bull Am Math Soc 26:315–316

    Article  Google Scholar 

  • Karmarkar N (1984) A new polynomial-time algorithm for linear programming. Combinatorica 4:373–395

    Article  Google Scholar 

  • Khaachiyan LG (1979) A polynomial algorithm in linear programming. Dokl Akad Nauk SSSR 244:1093–1096

    Google Scholar 

  • 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

    Article  Google Scholar 

  • Klee V (1964) Diameters of polyhedral graphs. Can J Math 16:602–614

    Article  Google Scholar 

  • Klee V (1966) Paths on polyhedra II. Pac J Math 17(2):249–262

    Article  Google Scholar 

  • Klee V, Kleinschmidt P (1987) The d-step conjecture and its relatives. Math Oper Res 12(4):718–755

    Article  Google Scholar 

  • 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

    Google Scholar 

  • Klee V, Walkup DW (1967) The d-step conjecture for polyhedra of dimension d<6. Acta Math 133:53–78

    Article  Google Scholar 

  • Kleinschmidt P, Onn S (1992) On the diameter of convex polytopes. Discrete Math 102(1):75–77

    Article  Google Scholar 

  • Larman DG (1970) Paths on polytopes. Proc Lond Math Soc 20(3):161–178

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • Nash JC (2000) The (Dantzig) simplex method for linear programming. Comput Sci Eng 2(29):3 pages

    Google Scholar 

  • Provan JS, Billera LJ (1980) Decompositions of simplicial complexes related to diameters of convex polyhedra. Math Oper Res 5(4):576–594

    Article  Google Scholar 

  • Santos F (2012) A counter-example to the Hirsch Conjecture. Ann Math (2) 176:383–412

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • Smale S (2000) Mathematical problems for the next century. In: Mathematics: frontiers and perspectives. Am Math Soc, Providence, pp 271–294

    Google Scholar 

  • Todd MJ (1980) The monotonic bounded Hirsch Conjecture is false for dimension at least 4. Math Oper Res 5(4):599–601

    Article  Google Scholar 

  • Vershynin R (2009) Beyond Hirsch Conjecture: walks on random polytopes and smoothed complexity of the simplex method. SIAM J Comput 39(2):646–678

    Article  Google Scholar 

  • Ziegler GM (1995) Lectures on polytopes. Graduate texts in mathematics, vol 152. Springer, Berlin

    Book  Google Scholar 

  • Ziegler GM (2012) Who solved the Hirsch Conjecture? Doc Math. Extra volume: Optimization stories, 75–85

Download references

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

  1. Departamento de Matemáticas, Estadística y Computación, Universidad de Cantabria, E-39005, Santander, Spain

    Francisco Santos

Authors
  1. Francisco Santos
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Francisco Santos.

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

Reprints 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

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11750-013-0295-7

Keywords

Mathematics Subject Classification (2000)

Search

Navigation