Abstract. The classic Cheeger’s inequality relates the edge conductance [Formula: see text] of a graph and the second smallest eigenvalue [Formula: see text] of the Laplacian matrix. Recently, Olesker-Taylor and Zanetti discovered a Cheeger-type inequality [Formula: see text] connecting the vertex expansion [Formula: see text] of a graph [Formula: see text] and the maximum reweighted second smallest eigenvalue [Formula: see text] of the Laplacian matrix. In this work, we first improve their result to [Formula: see text], where [Formula: see text] is the maximum degree in [Formula: see text], 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 analogue in relating vertex expansions and reweighted eigenvalues. These include the following: (1) An analogue of Trevisan’s result that relates the bipartite vertex expansion [Formula: see text] of a graph and the maximum reweighted lower spectral gap [Formula: see text] of the adjacency matrix. This implies the first approximation algorithm for bipartite vertex expansion. (2) An analogue of higher-order Cheeger’s inequalities that relates the [Formula: see text]-way vertex expansion [Formula: see text] of a graph and the maximum reweighted [Formula: see text]th smallest eigenvalue [Formula: see text] of the Laplacian matrix. This implies the first approximation algorithm for [Formula: see text]-way vertex expansion. (3) An analogue of improved Cheeger’s inequality that relates the vertex expansion [Formula: see text] and the reweighted eigenvalues [Formula: see text] and [Formula: see text]. This provides an improved bound for [Formula: see text] using [Formula: see text], when the [Formula: see text]-way vertex expansion [Formula: see text] is large for a small [Formula: see text]. Finally, inspired by this connection, we present negative evidence to the [Formula: see text]-polytope edge expansion conjecture by Mihail and Vazirani. We construct [Formula: see text]-polytopes whose graphs have very poor vertex expansion. This implies that the fastest mixing time to the uniform distribution on the vertices of these [Formula: see text]-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 [Formula: see text]-polytopes.

We consider a new semidefinite programming relaxation for directed edge expansion, which is obtained by adding triangle inequalities to the reweighted eigenvalue formulation. Applying the matrix multiplicative weight update method on this relaxation, we derive almost linear-time algorithms to achieve O (√log n)- approximation and Cheeger-type guarantee for directed edge expansion, as well as an improved cut-matching game for directed graphs. This provides a primal-dual flow-based framework to obtain the best known algorithms for directed graph partitioning. The same approach also works for vertex expansion and for hypergraphs, providing a simple and unified approach to achieve the best known results for different expansion problems and different algorithmic techniques.

We derive Cheeger inequalities for directed graphs and hypergraphs using the reweighted eigenvalue approach that was recently developed for vertex expansion in undirected graphs. The goal is to develop a new spectral theory for directed graphs and an alternative spectral theory for hypergraphs.

The classical Cheeger’s inequality relates the edge conductance of a graph and the second smallest eigenvalue of the Laplacian matrix. Recently, Olesker-Taylor and Zanetti discovered a Cheeger-type inequality connecting the vertex expansion of a graph and the maximum reweighted second smallest eigenvalue of the Laplacian matrix.In this work, we first improve their result to a logarithmic dependence on the maximum degree in the graph, 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 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.