Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

This question is inspired by the polynomial Hirsch conjecture (PHC). Given a $n$-facet polytope $P$ in $\mathbb R^d$, is the spectral gap of its edge-vertex graph (call it $G$) lower bounded by $\Omega(1/\mathrm{poly}(n))$? Note that the cycle graph on $n$ vertices shows that, even for $d=2$, the spectral gap could be as small as $O(1/\mathrm{poly}(n))$; so the conjectured bound--if true--would be almost tight.

A yes answer would imply the PHC. In fact, it would also imply that linear programs can be solved efficiently by just a random walk on the polytope vertices, and this algorithm is not even paying much attention to the objective function! This seems too good to be true.

So, what is the status of this problem: open (like PHC), or false? If false, are there simple counterexamples?

Note: I just realized about the usual complications involved in defining expanders: $G$ need not be regular or bipartite. I hope that both of these technical issues can be overcome using standard ways, and that, in particular, they do not make my question trivial. (Please correct me if I am wrong!)

share|cite|improve this question
Can someone explain how this question is related to the new subexponential lower bounds for randomized pivoting rules for the simplex algorithm? Oliver Friedmann, Thomas Dueholm Hansen, and Uri Zwick. 2011. Subexponential lower bounds for randomized pivoting rules for the simplex algorithm. In Proceedings of the 43rd annual ACM symposium on Theory of computing (STOC '11). ACM, New York, NY, USA, 283-292. DOI=10.1145/1993636.1993675 – Tyson Williams Dec 11 '11 at 15:49

For 0/1-polytopes (all vertex coordinates are 0 or 1), this is not known to be true. There is a conjecture by Mihail and Vazirani that the edge expansion of the graph of a 0/1-polytope is at least one. More information is described in a paper by Volker Kaibel.

I should note two things. (1) For 0/1-polytopes, the Hirsch conjecture is true. (2) When performing a random walk on the vertices of a polytope, we need to take care of possible degeneracy. One vertex can correspond to a lot of bases, and so the walk can stay at the same vertex if we perform a random walk over the bases. If we want to perform a random walk over the vertices, we need to have a procedure that gives a random adjacent vertex.

share|cite|improve this answer

In general it is not true: Consider two dual- to cyclic d-polytopes with n facets each and merge them along a vertex. (This is the dual operation of gluing two polutops). The number of vertices will be like $n^{[d/2]}$ and the spectrual gap will be roughly 1 over this. (You can use d edges to separete the graph into two parts.

I proved 1/poly(n) seperation for "dual-to-neighborly" polytopes. (This was my first shot at the polynomial Hiresch conjecture".) "The diameter of graphs of convex polytopes and f-vector theory" Applied geometry and discrete mathematics, 387–411, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., 4, Amer. Math. Soc., Providence, RI, 1991.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.