The Hirsch conjecture holds for normal flag complexes. (English) Zbl 1319.52017
The Bounded Hirsch Conjecture states that the diameter of the facet-ridge graph of any \((d+1)\)-polytope on \(n\) vertices is \(\leq n - (d+1)\). This conjecture was proved to be false in the year 2012 by F. Santos [Ann. Math. (2) 176, No. 1, 383–412 (2012; Zbl 1252.52007)]. An equivalent conjecture, which states that any two facets of a simplicial polytope can be connected by a nonrevisiting path, was also introduced in 1960. In this article, the authors study some particular kinds of complexes wherein the Hirsch Conjecture is true, e.g., it has been proved geometrically and combinatorially that flag normal simplicial complexes satisfy the Hirsch Conjecture; flag polytopes, derived subdivision of any triangulation of a connected manifold also satisfy the Hirsch Conjecture.
Reviewer: Keerti Vardhan (Chandigarh)
MSC:
| 52B05 | Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) |
| 53C21 | Methods of global Riemannian geometry, including PDE methods; curvature restrictions |
| 90C60 | Abstract computational complexity for mathematical programming problems |
| 05C12 | Distance in graphs |
| 05E45 | Combinatorial aspects of simplicial complexes |
| 52B70 | Polyhedral manifolds |
| 90C05 | Linear programming |
| 14M15 | Grassmannians, Schubert varieties, flag manifolds |
Keywords:
dual graph; Hirsch conjecture; simplicial complexes; flag normal complexes; CAT(1) spaces; polytopes; simplex method; graph diameterCitations:
Zbl 1252.52007References:
| [1] | Barnette D (1974) An upper bound for the diameter of a polytope. Discrete Math. 10:9-13. CrossRef · Zbl 0294.52007 |
| [2] | Burago D, Burago Y, Ivanov S (2001) A Course in Metric Geometry, Graduate Studies in Mathematics, Vol. 33 (American Mathematical Society, Providence, RI). CrossRef |
| [3] | Bux K-U, Witzel S (2012) Local convexity in CAT( {\(\kappa\)})-spaces Preprint, arXiv:1211.1871. |
| [4] | Charney R (1996) Metric geometry: Connections with combinatorics. Billera LJ, Greene C, Simion R, Stanley RP, eds. Formal Power Series and Algebraic Combinatorics, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., Vol. 24 (American Mathathematical Society, Providence, RI), 55-69. |
| [5] | Dantzig GB (1963) Linear Programming and Extensions (Princeton University Press, Princeton, NJ). |
| [6] | Davis MW, Moussong G (1999) Notes on nonpositively curved polyhedra. Böröczky K, Neumann WD, Stipsicz A, eds. Low-Dimensional Topology, Bolyai Soc. Math. Stud., Vol. 8 (János Bolyai Math. Soc., Budapest), 11-94. · Zbl 0961.53022 |
| [7] | Eisenbrand F, Hähnle N, Razborov AA, Rothvoß T (2010) Diameter of polyhedra: Limits of abstraction. Math. Oper. Res. 35(4):786-794. Abstract · Zbl 1226.52004 |
| [8] | Gromov M (1987) Hyperbolic groups. Essays in Group Theory, Math. Sci. Res. Inst. Publ., Vol. 8 (Springer, New York), 75-263. CrossRef · Zbl 0634.20015 |
| [9] | Hachimori M, Ziegler GM (2000) Decompositons of simplicial balls and spheres with knots consisting of few edges. Math. Z 235:159-171. CrossRef · Zbl 0965.57022 |
| [10] | Kalai G (1992) Upper bounds for the diameter and height of graphs of convex polyhedra. Discrete Comput. Geom. 8:363-372. CrossRef · Zbl 0764.52003 |
| [11] | Kalai G, Kleitman DJ (1992) A quasi-polynomial bound for the diameter of graphs of polyhedra. Bull. Amer. Math. Soc. (N.S.) 26:315-316. CrossRef · Zbl 0751.52006 |
| [12] | Klee V (1965) Paths on polyhedra. I. J. Soc. Indust. Appl. Math. 13:946-956. CrossRef · Zbl 0141.21303 |
| [13] | Klee V, Kleinschmidt P (1987) The d-step conjecture and its relatives. Math. Oper. Res. 12(4):718-755. Abstract · Zbl 0632.52007 |
| [14] | Klee V, Walkup DW (1967) The d-step conjecture for polyhedra of dimension d < 6. Acta Math. 117:53-78. CrossRef · Zbl 0163.16801 |
| [15] | Larman DG (1970) Paths on polytopes. Proc. London Math. Soc. s3-20:161-178.. CrossRef · Zbl 0199.59301 |
| [16] | Nakajima S (1931) Einige Beiträge über konvexe Kurven und Flächen. Tohoku Math. J. 33:219-230. · Zbl 0001.17003 |
| [17] | Papadopoulos A (2005) Metric Spaces, Convexity and Nonpositive Curvature, IRMA Lectures in Mathematics and Theoretical Physics, Vol. 6 (European Mathematical Society, Zürich). |
| [18] | Provan JS, Billera LJ (1980) Decompositions of simplicial complexes related to diameters of convex polyhedra. Math. Oper. Res. 5(4):576-594. Abstract · Zbl 0457.52005 |
| [19] | Santos F (2012) A counterexample to the Hirsch conjecture. Ann. Math. 176:383-412. CrossRef · Zbl 1252.52007 |
| [20] | Tietze H (1928) Über Konvexheit im kleinen und im großen und über gewisse den Punkten einer Menge zugeordnete Dimensionszahlen. Math. Z 28:697-707. CrossRef · JFM 54.0797.01 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
