<p>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. </p>

<p>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.</p>

CC BY-SA 3.0
2012-12-29T18:22:42.423Z
2012-12-29T18:22:42.423Z
Gil Kalai
<p>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 href="http://arxiv.org/pdf/math.CO/0112146">a paper by Volker Kaibel</a>.</p>

<p>I should note two things.  (1) <a href="http://dx.doi.org/10.1007/BF01589099">For 0/1-polytopes, the Hirsch conjecture is true</a>.  (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.</p>

CC BY-SA 3.0
2011-12-11T03:34:53.223Z
2011-12-11T03:34:53.223Z
Yoshio Okamoto
<p>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. </p>

<p>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. </p>

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

<p><strong>Note</strong>: 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!)</p>

CC BY-SA 3.0
2011-12-11T15:49:40.700Z
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 http://doi.acm.org/10.1145/1993636.1993675
Tyson Williams
<co.combinatorics><linear-programming><expanders>
Are edge-vertex graphs of polytopes (decent) expanders?
Srivatsan Narayanan
# Are edge-vertex graphs of polytopes (decent) expanders?

(Asked by: username_0 on 2011-07-22)

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

**Tags:** co.combinatorics, linear-programming, expanders
> **Comments:**
> **username_1**: 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 http://doi.acm.org/10.1145/1993636.1993675  

---

## 2 answers

### Answer by username_3 on 2011-12-11. Score: 10

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](http://arxiv.org/pdf/math.CO/0112146).

I should note two things. (1) [For 0/1-polytopes, the Hirsch conjecture is true](http://dx.doi.org/10.1007/BF01589099). (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 by username_2 on 2012-12-29. Score: 9

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.


---

