  The classical Cheeger's inequality relates the edge conductance $\phi$ of a
graph and the second smallest eigenvalue $\lambda_2$ of the Laplacian matrix.
Recently, Olesker-Taylor and Zanetti discovered a Cheeger-type inequality
$\psi^2 / \log |V| \lesssim \lambda_2^* \lesssim \psi$ connecting the vertex
expansion $\psi$ of a graph $G=(V,E)$ and the maximum reweighted second
smallest eigenvalue $\lambda_2^*$ of the Laplacian matrix.
  In this work, we first improve their result to $\psi^2 / \log d \lesssim
\lambda_2^* \lesssim \psi$ where $d$ is the maximum degree in $G$, which is
optimal assuming the small-set expansion conjecture. Also, the improved result
holds for weighted vertex expansion, answering an open question by
Olesker-Taylor and Zanetti. Building on this connection, we then develop a new
spectral theory for vertex expansion. We discover that several interesting
generalizations of Cheeger inequalities relating edge conductances and
eigenvalues have a close analog in relating vertex expansions and reweighted
eigenvalues. These include an analog of Trevisan's result on bipartiteness, an
analog of higher order Cheeger's inequality, and an analog of improved
Cheeger's inequality.
  Finally, inspired by this connection, we present negative evidence to the
$0/1$-polytope edge expansion conjecture by Mihail and Vazirani. We construct
$0/1$-polytopes whose graphs have very poor vertex expansion. This implies that
the fastest mixing time to the uniform distribution on the vertices of these
$0/1$-polytopes is almost linear in the graph size. This does not provide a
counterexample to the conjecture, but this is in contrast with known positive
results which proved poly-logarithmic mixing time to the uniform distribution
on the vertices of subclasses of $0/1$-polytopes.
