Singular values versus expansion in directed and undirected graphs

We relate the nontrivial singular values σ2,…,σ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+δ)⋅|S| out-neighbors, then 1−σ2=Ω(δ2/d). This bound is tight and saves a factor of d over the previously known relationship.