Trevisan’s L^1-style Cheeger inequality

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 k-regular graph \Gamma, the inequalities state that
\frac{2}{k}\lambda_1(\Gamma)\leq h(\Gamma)\leq k\sqrt{2\lambda_1(\Gamma)},
where:

  • \lambda_1(\Gamma) is the smallest non-zero eigenvalue of the normalized Laplace operator \Delta, i.e., the operator acting on functions on the vertex set by
    \Delta\varphi(x)=\varphi(x)-\frac{1}{k}\sum_{y\text{ adjacent to x}}{\varphi(y)}.
  • h(\Gamma) is the expansion ratio of \Gamma, given by h(\Gamma)=\min_{1\leq |W|\leq |\Gamma|/2}\frac{|E(W)|}{|W|}, the set E(W) in the numerator being the set of edges in \Gamma with one extremity in W and one outside.

The left-hand inequality is rather simple, once one knows (or notices) the variational characterization
\lambda_1(\Gamma)=\min_{\varphi\perp 1}\frac{\langle \Delta\varphi,\varphi\rangle}{\|\varphi\|^2}
of the spectral gap: basically, for a characteristic function \varphi of a set W of vertices, the right-hand side of this expression reduces (almost) to the corresponding ratio |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 h(\Gamma) of the form
W_t=\{x\in V_{\Gamma}\,\mid\, \varphi(x)\leq t\},
for a suitable real-valued function \varphi on the group. The only minor difference is that, in order to motivate the distribution of a random “threshold” 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 [\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
h(\Gamma)\leq \frac{A}{B}
where, for any non-constant real-valued function \varphi with minimum a, maximum b and median t_0, we have
A=\frac{1}{2}\sum_{x,y\in V}{a(x,y)|\varphi(x)-\varphi(y)|},
(where a(x,y) is the number of edges between x and y) and
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 \Gamma_n which are the Cayley graphs of \mathfrak{S}_n with respect to the generating set
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
\lambda_1(\Gamma_n)\asymp \frac{1}{n^3},
and Cheeger’s inequality leads to
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 \sigma^{-1}(1) and \sigma^{-1}(2), satisfies
\frac{A}{B}\ll \frac{1}{n^2},
and therefore we get a better upper-bound
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.)

Action graphs

The beginning of my lecture notes on expander graphs is now available. These first sections are really elementary. If it were not grossly insulting to the noble brotherhood (and sisterhood) of bookkeepers, I would say that I deal here mostly with bookkeeping: setting up a rigorous “coding” of the class of graphs I want to consider (which are unoriented graphs where multiple edges are allowed as well as loops), defining maps between such graphs, and setting up the basic examples of Cayley graphs and Schreier graphs.

But still, I managed to trip once on the last point, and my first definition turned out to be rather bad. Of course, it is not that I don’t know what a Schreier graph is supposed to be, but rather that I stumbled when expressing properly this intuition in the specific “category” I am using (where a graph is a triple (V,E,e), with vertex set V, edge set E, and
e\,:\, E\rightarrow \{\text{subsets of } V\text{ with } 1 \text{ or } 2\text{ elements}\}
is the “endpoints” map.)

What I knew about the Schreier graph of a group G with respect to a subgroup H and a (symmetric) generating set S is that it should be |S|-regular, and the combinatorial Laplace operator \Delta should be given by
\Delta\varphi(x)=\varphi(x)-\frac{1}{|S|}\sum_{s\in S}{\varphi(sx)},
for any function \varphi on G/H. This I managed to ensure on the second try, though the definition is a bit more complicated than I would like.

I actually wrote things down for more general “action graphs”, which are pretty much the obvious thing: given an action of the group G on a set X, one takes X as vertices, and moves along edges (set up properly) from x to s\cdot x for s in the given subset S of G. Here is a query concerning this: do these general graphs have a standard name? I have not seem the definition in this generality before, but it seems very natural and should be something well-known, hence named. (Of course, using decomposition in orbits, such a graph is a disjoint union of Schreier graphs modulo stabilizers of certain points of X, but that doesn’t make it less natural.)

In any case, here is an illustration of the action graph for the symmetric group S_5, with generators S=\{(1\ 2), (1\ 2\ 3\ 4\ 5), (1\ 5\ 4\ 3\ 2)\}, acting on X=\{1,2,3,4,5\} by evaluation:

Action graph

Equivalently, this is the Schreier graph of G/H with respect to S, where H is the stabilizer of 1.

As it should be, this graph is 3-regular, and this property would fail if loops and multiple edges were not permitted. It is true that, in that case, the resulting graph (a cycle of length 5) would remain regular after removing loops and multiple edges, but the interested reader will have no problem checking that if S is replaced by
S'=S\cup\{(1\ 2\ 3), (1\ 3\ 2)\},
removing loops and multiple edges from the corresponding action graph leads to a non-regular graph. (The vertex 1 has three neighbors then, namely \{2, 3, 5\}, while the others have only 2.)

(The typesetting of the graph is done using the tkz-graph package already mentioned in my previous post.)

Expanders course

I am teaching a class on expander graphs this semester, and as usual there is a web page about it. For the moment, do not be fooled by the link to “lecture notes”, since I haven’t put up anything yet (I am trying to learn the easiest way to incorporate nice pictures of graphs in LaTeX; tkz-graph and tkz-berge seem to be the best way to do that…)

The course meets only 2 hours per week (and those are ETH hours, which means 1h30 really), so it will necessarily be very restricted in what I can cover. I have decided on the content of the first two parts: a general discussion of elementary material (of course), and then a full account of the combination of the results of Helfgott and Bourgain–Gamburd, which together imply that the family of Cayley graphs of \mathrm{SL}_2(\mathbf{F}_{p}), with respect to the projections modulo primes p of a subset S\subset \mathrm{SL}_2(\mathbf{Z}) which generates a Zariski-dense subgroup of \mathrm{SL}_2, is an expander family.

If there is time after this, which I hope, I haven’t quite decided what to do. One possibility would be an account of the “expander philosophy” discussed at the end of this post, another would be to discuss some applications to theoretical computer science (admittedly, this would be because I would learn about them much more than I know at the current time…)

Update on representation theory notes

After a long hiatus, I have just put up online an updated version of my lecture notes on representation theory. The delay was psychologically interesting: after a long period where I added material more or less in the order I wanted it to appear in the text, I started in June to proceed in much more chaotic (or random?) manner, with an explanation of the Larsen alternative for unitary groups coming before the Peter-Weyl theorem, and so son. Inly in the last few days did the text regain at least some coherence. (In particular, it took me a long time to finally sit up and write an account of the Peter-Weyl theorem that I felt to be at least somewhat motivated.)

There are still things missing before the notes contain all that I’d like, in particular at least a few pages of survey concerning the representation theory of some locally compact, non compact, groups. There are still a few weeks before the beginning of the new semester, however, and hopefully I will have time to do some work on this part in the coming weeks…

As usual, any remarks or corrections will be very appreciated!

Who was Peter?

The fundamental fact about the representation theory of a compact topological group G is the Peter-Weyl Theorem, which can be described as follows: the regular representation of G on L^2(G) (defined using the probability Haar-measure on G) decomposes as an orthogonal Hilbert direct sum of the spaces of matrix coefficients of the finite-dimensional irreducible representations of G. (Books, for instance the one of Knapp on semisimple Lie groups, often include more in what is called Peter-Weyl Theory, but this is the statement that is proved in the original paper.)

As I am currently preparing to write down a proof of the Peter-Weyl theorem for my notes on representation theory, I had a look at this paper. Although I probably won’t follow it quite completely, I found it very interesting — it is quite subtly different from all modern treatments I have seen, in an interesting way, and without being much more complicated than what is found, e.g., in Knapp’s book. (For a short masterful online account, this post of Terry Tao is very good; from a search in the same Göttingen archive web site, it seems that — maybe — the modern treatment dates back to Pontryagin, in 1936.)

In any case, the question for today is: Who was Peter? Only the initial “F.” and the affiliation “in Karlsruhe” identifies this coauthor on the original paper (even the “F.” is misread as “P.” on the PDF cover page…) It seem he was a student of Weyl, but note that there is no Peter on the math genealogy page for Weyl. (A joke here at ETH, is that when the lecture room known as the Hermann Weyl Zimmer is renovated this summer, some unfortunate skeletons will be found in the closets and under the floor, or behind the blackboards…)