Thomas Voigt
Published 2005-06-23Version 1
In this paper we show that graphs of "neighbourly" cubical complexes -- cubical complexes in which every pair of vertices spans a (unique) cube -- have good expansion properties, using a technique based on multicommodity flows. By showing that graphs of stable set polytopes are graphs of neighbourly cubical complexes we give a new proof that graphs of stable set polytopes have edge expansion 1.
On the Expansion of Graphs of 0/1-Polytopes
Expansion of random $0/1$ polytopes
Edge Expansion and Spectral Gap of Nonnegative Matrices
![QR code for arXiv:math/0506478 [math.CO]](http://oss.arxitics.com/images/favicon.svg)