Source-linked AI summary
A counterexample to the Hirsch conjecture
Francisco Santos
TL;DR
The paper asks how large the diameter of a polytope can be and develops reductions that produce counterexamples to the Hirsch conjecture. It constructs non-Hirsch polytopes, including a 43-dimensional example with 86 facets and diameter at least 44, while leaving the general linear-bound question open.
Problem
The paper examines whether polytope diameter admits a dimension-independent linear upper bound in the number of facets.
Method
The paper combines classical reductions into a Strong d-step Theorem and applies these techniques to construct non-Hirsch polytopes.
Results
A 43-dimensional polytope with 86 facets has diameter at least 44, and another construction gives a non-Hirsch polytope of dimension 20 with 40 facets and diameter 21.
Takeaways & Limitations
The constructions yield an infinite family in fixed dimension whose diameters exceed (1 + ϵ)n for a positive constant ϵ.
Takeaways & Limitations
The techniques leave the underlying question of how large polytope diameter can be almost as open as before, including whether a dimension-independent constant linear bound exists.
Abstract
from arXiv · showhide
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, that 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 which violates a certain generalization of the $d$-step conjecture of Klee and Walkup.
1 Introduction
The paper disproves the Hirsch conjecture with a 43-dimensional polytope having 86 facets and diameter at least 44, and extends this to infinite families with superlinear diameter.
- Background: The Hirsch conjecture asserts that every d-dimensional polytope with n facets has diameter at most n-d.Combinatorial diameter is the maximum number of edge traversals needed between two vertices.
- Our counterexample: The main counterexample is a non-Hirsch polytope of dimension 43 with 86 facets.Its diameter is at least 44, exceeding the Hirsch bound 86-43 = 43.
- Discussion: The result leaves the general growth rate of polytope diameters unresolved, including whether a dimension-independent linear bound exists.The authors suspect the answer is negative but describe the counterexample as only a small first step.
2 A strong d-step theorem for spindles
The paper reformulates the Hirsch problem using dual facet paths and develops reductions that preserve or increase relevant distances. Its strong d-step theorem transforms a prismatoid of dimension d, n vertices, and width l into one of dimension n −d with width at least l + n −2d.
- Dual formulation: Dual-Hirsch polytopes require at most n −d dual steps between any two facets, making the formulation equivalent to the Hirsch conjecture under polarity.A dual step crosses from one facet to an adjacent facet sharing a ridge.
- Classical reductions: Pushing a vertex preserves dimension and vertex count while inducing a simplicial map from the new dual graph to the original one.Adjacent facets map either to the same facet or to adjacent facets of the original polytope.
- Classical reductions: Every polytope has a simplicial counterpart with the same dimension and number of vertices and with the same or greater dual diameter.This follows from the vertex-pushing reduction.
- Classical reductions: One-point-suspension raises dimension and vertex count by one, while its dual-graph projection contracts selected edges and cannot decrease the distance between corresponding facets.The construction replaces a vertex by two vertices on opposite sides of a hyperplane.
- Strong d-step theorem: A prismatoid is a polytope with two parallel base facets containing all vertices, and its width is the dual-graph distance between those bases.The bases need not be uniquely determined, and disjoint facets can be made parallel projectively without changing combinatorics.
- Strong d-step theorem: For a prismatoid, the strong d-step theorem produces dimension n −d, 2n −2d vertices, and width at least l + n −2d.If the original width satisfies l > d, the resulting prismatoid violates the dual d-step and dual Hirsch conjectures.
3 A 5-prismatoid without the d-step property
The paper constructs a 5-dimensional prismatoid with 48 vertices and width six, thereby exhibiting a prismatoid without the d-step property. Its vertices are organized into two symmetric 24-vertex base facets.
- Definition and context: A prismatoid has the d-step property when its width does not exceed its dimension.The paper notes that this holds for every 3-dimensional prismatoid and remains true, though non-obviously, in dimension four.
- Construction: Theorem 3.1 gives a 5-dimensional prismatoid with 48 vertices and width six.The construction is specified by the 48 rows of the matrices in Table 1 and was independently verified computationally.
- Structure: The first 24 and last 24 vertices span base facets Q+ and Q− in the hyperplanes x5 = +1 and x5 = −1, respectively.These two facets contain all vertices, establishing that Q is a prismatoid.
- Symmetry: The prismatoid is symmetric under a transformation that exchanges Q+ and Q− while matching each vertex labeled i+ with i−.Each base is also invariant under 32 additional orthogonal transformations.
4 First proof of Theorem 3.1
The first proof establishes the facet structure and adjacency graph of Q using symmetry and representative inequalities. The resulting graph shows that six steps are necessary and sufficient between the base facets Q+ and Q−.
- Adjacency graph: The adjacency graph between facet orbits contains exactly the cross-orbit adjacencies shown in Figure 4.Symmetry permits checking representative facets and their induced permutations within each orbit.
- Facet structure: 322 inequalities define the facets of Q, organized into six Σ-orbits: A∪L, B∪K, C∪J, D∪I, E∪H, and F∪G.A and L are the prismatoid bases; the other facets form 32-element Σ+-orbits.
- Facet structure: The facet inequalities include the base facets A and L, cross-signed families for B and C, and corresponding D, E, F, G, H, I, J, and K families.The displayed inequalities encode the symmetry-generated facet families used in the construction.
- Adjacency graph: Six steps are necessary and sufficient to travel in the facet graph from Q+ to Q−, the facets labeled A and L.This establishes the required width statement for the prismatoid.
- Facet structure: Facet verification reduces to representative inequalities: checking selected vertices and rank five shows that the listed sets span affine hyperplanes and define facets.Only vertices with nonnegative x1, x2, x3, and x4 need checking in the stated verification.
- Facet structure: Facets of types D, E, and F are simplices, while type C is an iterated pyramid over a quadrilateral and type B is a pyramid over a triangular prism.The triangular prism in type B follows from three rays meeting at o.
5 Second proof of Theorem 3.1
The second proof translates the prismatoid problem into geodesic maps on a sphere and uses transversality to rule out short paths. The construction is analyzed through Minkowski sums, normal maps, and the combinatorics of Q+ and Q−.
- From prismatoids to geodesic maps: An intermediate hyperplane intersects the prismatoid in a Minkowski sum of its two bases, reducing the five-dimensional analysis to four-dimensional bases.The reduction removes one dimension before passing to normal maps.
- From prismatoids to geodesic maps: The d-step property for a prismatoid is equivalent to the d-step property of its two base polytopes.This reduction uses the dual graph of the Minkowski sum of the bases.
- From prismatoids to geodesic maps: The normal fan of a polytope induces a geodesic map on the sphere, and the common refinement of two maps consists of all intersections of their cells.The maps for Q+ and Q− lie in S^(d−2).
- From prismatoids to geodesic maps: A pair of geodesic maps has the d-step property when its common-refinement 1-skeleton contains a path of length at most d−2 between vertices of the two maps.Theorem 5.5 identifies this condition with the corresponding property for the base polytopes.
- The obstruction: The constructed pair of periodic maps in the plane lacks the d-step property, showing that the four-dimensional positive result is not explained locally.No two-step path connects a black-map vertex to a grey-map vertex in the example.
- The obstruction: Q+ has 32 facets and a transitive symmetry group, while its normal-map vertices lie on a flat torus used to visualize the combinatorics.The torus picture’s crossings are artifacts because the true edges lie in S3 rather than along the torus.
- The obstruction: For a transversal pair, any path of length d−2 forces endpoint incidence relations between the opposite maps’ containing facets.This proposition turns the absence of those incidences into an obstruction to a short path.
6 An infinite family of non-Hirsch polytopes
The section gives product and gluing constructions that turn one non-Hirsch polytope into infinite families, including fixed-dimensional families whose diameter exceeds the Hirsch bound by a fixed fraction.
- A fixed dimension d admits an infinite sequence of non-Hirsch polytopes whose diameters exceed the Hirsch bound by a fixed fraction.
- A k-fold product preserves the relative excess: a polytope with diameter (1 + ϵ)(n − d) yields a kd-polytope with diameter (1 + ϵ)(kn − kd).
- Gluing simple d-polytopes combines facet counts as n1 + n2 − d and gives diameter at least l1 + l2 − 1.
- Repeated gluing produces a polytope with k(n − d) + d facets and diameter at least k(l − 1) + 1, preserving non-Hirschness.
- A linear fixed-dimensional diameter bound H(n, d) ≤ an + b can be sharpened to H(n, d) ≤ a(n − d) + 1.
- The 43-dimensional, 86-facet, diameter-44 counterexample has excess ϵ = 1/43 and yields excess 1/86 in dimension 86, approaching 1/43 in sufficiently high fixed dimensions.
- The construction's resulting excess remains slightly below the original polytope's excess, and no operation is known to increase excess.