Singular Values Versus Expansion in Directed and Undirected Graphs

Abstract

We relate the nontrivial singular values $\ddot{I}{ƒ}_2,\dots ,\ddot{I}{ƒ}_n$ of the normalized adjacency matrix of an Eulerian directed graph to combinatorial measures of graph expansion: \\ 1. We introduce a new directed analogue of conductance $\ddot{I}{•}_{dir}$, and prove a Cheeger-like inequality showing that $\ddot{I}{•}_{dir}$ is bounded away from 0 iff $\ddot{I}{ƒ}_2$ is bounded away from 1. In undirected graphs, this can be viewed as a unification of the standard Cheeger Inequality and Trevisan's Cheeger Inequality for the smallest eigenvalue.\\ 2. We prove a singular-value analogue of the Higher-Order Cheeger Inequalities, giving a combinatorial characterization of when $\ddot{I}{ƒ}_k$ is bounded away from 1. \\ 3. We tighten the relationship between $\ddot{I}{ƒ}_2$ and vertex expansion, proving that if a $d$-regular graph $G$ with the property that all sets $S$ of size at most $n/2$ have at least $(1+\hat{I}´)\cdot |S|$ out-neighbors, then $1-\ddot{I}{ƒ}_2=\hat{I}\text{c◯}(\hat{I}{´}^2/d)$. This bound is tight and saves a factor of $d$ over the previously known relationship.