Home » Subject » Geometry » Polytopes

Hirsch Conjecture (Solved)

Importance: High ✭✭✭
Author(s): Hirsch, Warren M.
Subject: Geometry
» Polytopes
Keywords: diameter
polytope
Recomm. for undergrads: no
Posted by: Robert Samal
on: May 11th, 2007
Solved by: Francisco Santos
Conjecture   Let $ P $ be a convex $ d $-polytope with $ n $ facets. Then the diameter of the graph of the polytope $ P $ is at most $ n-d $.

(Originally appeared in [D], this discussion appears as [M].)

Many special cases of this conjecture have been verified, and in particular, the case of $ (0,1) $-polytopes was settled by Naddef by an elegant proof in [N], and further generalized in [MT]. However, in the general case, the Hirsch conjecture is known only for $ d \le 3 $. It is even open if there is a polynomial upper bound on the diameter. Kalai and Kleitman [KK] found a quasi-polynomial bound by proving that the diameter is bounded by $ n^{2+\log d} $.

The special case of Hirsch Conjecture, the $ d $-step conjecture, asserts that the diameter is equal to $ d $ if the polytope has precisely $ 2d $ facets. The $ d $-step conjecture has been verified for $ d \le 5 $, and similarly as the Hirsch Conjecture, it is completely open for higher dimensions. This has been the situation for the past 50 years, and there is no evidence for essential progress.

Bibliography

*[D] G. B. Dantzig: Linear Programming and Extensions, Princeton University Press (1963).

[KK] G. Kalai and D. J. Kleitman, A quasi-polynomial bound for the diameter of graphs of polyhedra, Bull. Amer. Math. Soc. (N.S.) 26 (1992), 315-316.

[MT] T. Matsui and S. Tamura, Adjacency on combinatorial polyhedra, Discrete Appl. Math. 56 (1995) 311-321.

[N] D. Naddef, The Hirsch conjecture is true for (0,1)-polytopes, Math. Progr. (Ser. B) 45 (1989) 109-110.

[M] B. Mohar, Problem of the Month


* indicates original appearance(s) of problem.
add new comment

Santos arXiv paper

On June 16th, 2010 Anonymous says:

Here is Santos's arXiv paper with the counterexample: http://arxiv.org/abs/1006.2814. --Joseph O'Rourke

reply

there are someone who's working on it...

On May 27th, 2010 Anonymous says:

http://www.readwriteweb.com/archives/the_hirsch_conjecture_disproved.php

<< Santos, Francisco (University of Cantabria, Spain) A counter-example to the Hirsch conjecture

Victor Klee came to the Department of Mathematics to talk to me. We had a nice conversation during which he asked "Why don't you try to disprove the Hirsch Conjecture?" This talk is the answer to that question.

I will describe the construction of a 43-dimensional polytope with 86 facets and diameter bigger than 43. The proof is based on a generalization of the $ d $-step theorem of Klee and Walkup. >>

copy paste from: https://sites.google.com/a/alaska.edu/kleegrunbaum/home/abstracts#Santos

best regards.

J.R.!

reply

Settled

On May 20th, 2010 Anonymous says:

This conjecture has been settled in the negative by Francisco Santos.

reply

Thats what i thought

On July 9th, 2011 Anonymous says:

Is there a difference from the negative to the positive? renters insurance quotes

reply

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.