For a graph $G = (V,E)$ with $|V|=n$, the Laplacian of $G$,

\[L = L_G = D_G - A_G,\]

is an $n \times n$ matrix where $A_G$ is the adjacency matrix of $G$ and $D_G$ is a diagonal matrix consisting of the degrees of vertices of $G$. $L$ is real, symmetric and positive semi-definite and has $n$ real eigenvalues usually enumerated as

\[ 0 = \lambda_1 \leq \lambda_2 \leq \ldots \leq \lambda_n.\]

The spectrum of $L$, in particular $\lambda_2$, also called the Fiedler value, is related to the connectedness of $G$ and spectral methods are heavily used in heuristics for graph partitioning and its variants. For this reason, $\lambda_2$ has been the focus of much theoretical work.

Most results on $\lambda_2$ were obtained by working with some embedding of a graph onto a surface and exploiting connections between the Fiedler value and geometric embeddings. As such, these techniques were specialized to graphs endowed with some structure which allow one to find an external geometric representation. See, for example, Kelner .

In 2008, Biswal, Lee, and Rao presented a method for bounding $\lambda_2$ using an intrinsic deformation of the graph. This deformation is achieved by assigning weights to vertices and equipping $V$ with a shortest path metric. A parameter associated with the metric (essentially, the average pairwise distance) is used to upper bound the Fiedler value and this parameter is optimized over all weight functions. Interestingly, this optimization problem has a dual formulation in terms of all pairs multi-commodity flows, where the optimal weights on vertices correspond directly to a measure of congestion in the optimal flow. The results are obtained by studying the structure of optimal flows in various classes of graphs.

The paper I will be discussing, ``Higher Eigenvalues of Graphs'' by Kelner, Lee, Price, and Teng, extends the above result to obtain bounds on higher eigenvalues. Additional conditions in the optimization problem lead to restrictions in the dual formulation and the notion of subset multi-commodity flows is introduced. Working under this setup, the authors show that $\lambda_k$ is $O(k/n)$ for planar graphs, $O(g k / n)$ for graphs of genus $g$, and $O(h^2 \log (h) k / n)$ for graphs with excluded $K_h$-minors.