My expander class at ETH continues, and for the moment the course notes are kept updated (and in fact I have some more in the notes than I did in class).
Last week, I presented the inequalities relating the definition of expanders based on the expansion ratio with the “spectral” definition. In fact, I used the random walk definition first, which is only very slightly different for general families of graphs (with bounded valency), and is entirely equivalent for regular graphs. For a connected -regular graph , the inequalities state that
- is the smallest non-zero eigenvalue of the normalized Laplace operator , i.e., the operator acting on functions on the vertex set by
- is the expansion ratio of , given by the set in the numerator being the set of edges in with one extremity in and one outside.
The left-hand inequality is rather simple, once one knows (or notices) the variational characterization
of the spectral gap: basically, for a characteristic function of a set of vertices, the right-hand side of this expression reduces (almost) to the corresponding ratio . The second inequality, which is called the discrete Cheeger inequality, is rather more subtle.
The proof I presented is the one presented by L. Trevisan in his recent lectures on expanders (see, specifically, Lecture 4). Here, the idea is to construct a test set for of the form
for a suitable real-valued function on the group. The only minor difference is that, in order to motivate the distribution of a random “threshold” that Trevisan uses to construct those test sets, I first stated a general lemma where the threshold is picked according to a fairly general probability measure. Then I first showed what happens for a uniform choice in this interval, to motivate the “better” one that leads to Cheeger’s inequality.
As it turns out, I just found an older blog post of Trevisan explaining his proof, where he also discusses first the computations based on the uniform measure supported on , and explains why it is problematic.
But there is some good in this inequality. First, the precise form it takes (which I didn’t find elsewhere, and will therefore name Trevisan’s inequality) is
where, for any non-constant real-valued function with minimum , maximum and median , we have
(where is the number of edges between and ) and
The interesting fact is that this can be sharper than Cheeger’s inequality. Indeed, this happens at least for the family of graphs which are the Cayley graphs of with respect to the generating set
From an analysis of the random walks by Diaconis and Saloff-Coste (see Example 1 in Section 3 of their paper), it is known that
and Cheeger’s inequality leads to
However (unless I completely messed up my computations…), one sees that the test function used by Diaconis and Saloff-Coste, namely the cyclic distance between and , satisfies
and therefore we get a better upper-bound
using Trevisan’s inequality.
(Incidentally, we see here an easy example of a sequence of graphs which forms an esperantist family, but is not an expander.)