Are edge-vertex graphs of polytopes (decent) expanders?

Question

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!)

Answer 1

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.

Answer 2

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.