Singular Values Versus Expansion in Directed and Undirected Graphs

Jake Ruotolo, Salil Vadhan

We relate the nontrivial singular values ${\sigma }_2,\dots ,{\sigma }_n$ of the normalized adjacency matrix of an Eulerian directed graph to combinatorial measures of graph expansion: \\ 1. We in…