Cheeger Inequalities for Vertex Expansion and Reweighted Eigenvalues

The classical Cheeger's inequality relates the edge conductance φ of a graph and the second smallest eigenvalue λ 2 of the Laplacian matrix. Recently, Olesker-Taylor and Zanetti discovered a Cheeger-type inequality

) and the maximum reweighted second smallest eigenvalue λ * 2 of the Laplacian matrix. In this work, we first improve their result to ψ 2 / log d λ * 2 ψ where d is the maximum degree in G, which is optimal up to a constant factor. 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 that relates the bipartite vertex expansion ψ B of a graph and the maximum reweighted lower spectral gap ζ * of the adjacency matrix. This implies the first approximation algorithm for bipartite vertex expansion.

• An analog of higher-order Cheeger's inequalities that relates the k-way vertex expansion ψ k of a graph and the maximum reweighted k-th smallest eigenvalue λ * k of the Laplacian matrix. This implies the first approximation algorithm for k-way vertex expansion.

• An analog of improved Cheeger's inequality that relates the vertex expansion ψ and the reweighted eigenvalues λ * 2 and λ * k . This provides an improved bound for ψ using λ * 2 , when the k-way vertex expansion ψ k is large for a small k.

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.