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 $latex k$-regular graph $latex \Gamma$, the inequalities state that
$latex \frac{2}{k}\lambda_1(\Gamma)\leq h(\Gamma)\leq k\sqrt{2\lambda_1(\Gamma)},$
where:
- $latex \lambda_1(\Gamma)$ is the smallest non-zero eigenvalue of the normalized Laplace operator $latex \Delta$, i.e., the operator acting on functions on the vertex set by
$latex \Delta\varphi(x)=\varphi(x)-\frac{1}{k}\sum_{y\text{ adjacent to x}}{\varphi(y)}$. - $latex h(\Gamma)$ is the expansion ratio of $latex \Gamma$, given by $latex h(\Gamma)=\min_{1\leq |W|\leq |\Gamma|/2}\frac{|E(W)|}{|W|},$ the set $latex E(W)$ in the numerator being the set of edges in $latex \Gamma$ with one extremity in $latex W$ and one outside.
The left-hand inequality is rather simple, once one knows (or notices) the variational characterization
$latex \lambda_1(\Gamma)=\min_{\varphi\perp 1}\frac{\langle \Delta\varphi,\varphi\rangle}{\|\varphi\|^2}$
of the spectral gap: basically, for a characteristic function $latex \varphi$ of a set $latex W$ of vertices, the right-hand side of this expression reduces (almost) to the corresponding ratio $latex |E(W)|/|W|$. 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 $latex h(\Gamma)$ of the form
$latex W_t=\{x\in V_{\Gamma}\,\mid\, \varphi(x)\leq t\},$
for a suitable real-valued function $latex \varphi$ on the group. The only minor difference is that, in order to motivate the distribution of a random “threshold” $latex t$ 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 $latex [\min \varphi,\max\varphi]$, 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
$latex h(\Gamma)\leq \frac{A}{B}$
where, for any non-constant real-valued function $latex \varphi$ with minimum $latex a$, maximum $latex b$ and median $latex t_0$, we have
$latex A=\frac{1}{2}\sum_{x,y\in V}{a(x,y)|\varphi(x)-\varphi(y)|},$
(where $latex a(x,y)$ is the number of edges between $latex x$ and $latex y$) and
$latex B=\sum_{x\in V}{|\varphi(x)-t_0|}.$
The interesting fact is that this can be sharper than Cheeger’s inequality. Indeed, this happens at least for the family of graphs $latex \Gamma_n$ which are the Cayley graphs of $latex \mathfrak{S}_n$ with respect to the generating set
$latex S_n=\{(1\ 2),(1\ 2\ \cdots\ n)^{\pm 1}\}.$
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
$latex \lambda_1(\Gamma_n)\asymp \frac{1}{n^3},$
and Cheeger’s inequality leads to
$latex h(\Gamma_n)\ll n^{-3/2}.$
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 $latex \sigma^{-1}(1)$ and $latex \sigma^{-1}(2)$, satisfies
$latex \frac{A}{B}\ll \frac{1}{n^2},$
and therefore we get a better upper-bound
$latex h(\Gamma)\ll \frac{1}{n^2}$
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.)
