The conjecture:
the edge-vertex graph of an n-facet polytope in d-dimensional Euclidean space has diameter no more than n − d.The result:
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.
The proof will be presented at the 100 Years in Seattle (The mathematics of Klee and Grunbaum) conference in end-July, this year.
Are there any significant results that depend on the conjecture being true that will now have to be reconsidered?
ReplyDeletethe funny thing is, probably not. While the conjecture was famous in polytope theory and was motivated by the simplex, and LP algorithms in general, I don't think it has any kind of domino effect that I'm aware of. Being true didn't automatically imply a combinatorial p-time algorithm for linear programming.
ReplyDeleteTo expand a little - the conjecture is famous simply due to the length of time that the question has remained open and the numerous partial results on the problem, but a counterexample doesn't lead directly to any new results. To quote Klee's paper on the problem, "finding a counterexample will be merely a small first step in the line of investigation related to the conjecture."
ReplyDeleteThe more general question of the polynomial Hirsch conjecture (whether polynomial diameter bounds exist for polytopes) may have more significance for linear programming, since a disproof might eliminate the possibility of polytime combinatorial LP algorithms, and upper bounds could lead to new polytime combinatorial LP algorithms.
Of course, there's still no direct route from the polynomial conjecture to polynomial combinatorial linear programming algorithms either, so we're still several steps away from an answer there too.
Suresh,
ReplyDeleteDumb question:
Donoho and Tanner [1][2] have shown a deep connection between randomly projecting high dimensional polytopes to lower dimension subspaces and compressed sensing. Should we be expecting these computational phase transition results to be affected in any way as a result of this disproven conjecture ? From the previous comments, I would not expect a clear answer. What do you and your other readers think ?
Cheers,
Igor.
[1] http://www.math.utah.edu/~tanner/CFRPP.pdf
[2] http://www.maths.ed.ac.uk/~tanner/DoTa_Finite.pdf
Hi Igor,
ReplyDeleteI'm not seeing any direct connection between the Donoho/Tanner work and the Hirsch conjecture (true or false)
I knew it! I could bet that the conjecture is false.
ReplyDeleteThe next step (which does have implications on simplex) is to find an example with super-polynomial diameter. Even that's probably doable.