Spectral Graph theory has various methods of bounding the Laplacian eigenvalues of a graph G (say by embedding another graph H into G and computing the congestion). Usually we look at the ordered eigenvalues , and usually we simplify things a little by assuming a bounded-degree graph, which gives us for free, where is the maximum vertex degree. So really, it is mostly just interesting to bound from below. When this is done, it is very often used as (when bounding energy of electrical flows in G) or as (when bounding mixing times of random walks on G).

We are interested in a new type of Laplacian bounds. It turns out that L1 bounds of the sort relate directly to how good electrical flow is when used for oblivious routing on G. Note that it is required here that since is the kernel of the Laplacian of any connected graph. This sort of bound is atypical in two ways. First, it is an L1 bound, and second, it is a lower-bound.

It is trivial to see that where is the Laplacian of the n-clique. What we are after is proving that

where H is an expander and and .

This statement holds true in experiments with random bounded-degree expanders, and in particular it has natural interpretations in terms of electrical flow (which I am going to omit here). One can even give a pseudo-proof of this fact by simply observing that .

I am curious if someone has come across similar types of inequalities and/or has an interesting proof idea.

Note that the above conjecture was recently proven and its proof will soon appear in a publication. I will post a link to it here when this happens. At this stage will be happy to hear of applications of this (now) theorem if you come across any.