Singular Values Versus Expansion in Directed and Undirected Graphs

We relate the nontrivial singular values $σ_2,\ldots,σ_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 $ϕ_{dir}$, and prove a Cheeger-like inequality showing that $ϕ_{dir}$ is bounded away from 0 iff $σ_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 $σ_k$ is bounded away from 1. \\ 3. We tighten the relationship between $σ_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+δ)\cdot |S|$ out-neighbors, then $1-σ_2=Ω(δ^2/d)$. This bound is tight and saves a factor of $d$ over the previously known relationship.