Convex and discrete geometry Polytopes and polyhedra Counterexample

Hirsch conjecture

Builds on Convex polytope Facet Distance in a graph Linear programming

Counterexample

For a convex polytope $P$ , the graph of $P$ has the vertices of $P$ as vertices and the edges of $P$ as edges. The diameter of $P$ is the largest distance in this graph between two vertices. The Hirsch conjecture asserted: if $d \ge 2$ and $P$ is a $d$ -dimensional polytope with $n$ facets, then the diameter of $P$ is at most $n - d$ . The conjecture is false: in 2010 Francisco Santos constructed a $43$ -dimensional polytope with $86$ facets whose diameter is at least $44$ , while $n - d = 43$ .

Remarks

Santos's construction first builds a spindle: a polytope with two special vertices whose distance exceeds the dimension. A known reduction, which adds facets and dimensions in step, then turns it into a counterexample. For unbounded polyhedra the analogous statement had already been disproved by Victor Klee and David Walkup in 1967. The bound $n - d$ is attained by the $d$ -cubes, which have $n = 2d$ facets and diameter $d$ .

The question matters for linear programming, since the simplex method walks along edges of the feasible polytope. So the diameter bounds from below the worst number of steps of any edge-following pivot rule. Whether the diameter is bounded by a polynomial in $n$ and $d$ remains open. The best general bound known is quasi-polynomial, of the form $n^{\log_2 d + 2}$ , due to Gil Kalai and Daniel Kleitman.

Reading path

To understand this page from the ground up, read these 5 pages in order. The foundations come first.

Show the path as a graph

Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.

no evidence level

Convex polytope concept
Distance in a graph concept
Facet concept
Linear programming concept
Hirsch conjecture counterexample

Tag	`ZBVJ4B41AX`
URI	`m2://ZBVJ4B41AX`
Kind	counterexample
Writing	W0 stub
MSC	52B05, 90C05, 52B11
Uses	Convex polytope, Facet, Distance in a graph, Linear programming
Same as	Wikidata Q2993326 Wikipedia Hirsch conjecture

Hirsch conjecture

Counterexample

Remarks

Reading path

Further reading

What this page needs for W1

What links here