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…)

Representation theory course

The Spring semester at ETH is starting next week, and I will be teaching an introductory course on representation theory (for third-year and later students). I am looking forward to it, since this is the first time I teach a class identified as “algebra” (except for linear algebra, of course).

My lecture notes will be available as I prepare them (the first chapter will be ready soon, at least in draft form) and it will be seen that (partly because of my own bias) I think of a representation of a group as a homomorphism G\rightarrow \mathrm{GL}(E), and not as modules over the group algebra. I certainly intend to mention the latter approach at some point (indeed, I have in preparation a long “Variants” chapter, where I mention also, e.g., topological representations, unitary representations, permutation representations, projective representations, Lie algebra representations, etc, with basic examples), but I find it useful to go through the elementary theory of representations completely “by hand”, for a course at this level. In some sense, this is because this is what I can do best, with my own knowledge; but also, going through these basic facts purely with the tools and language of representations-as-homomorphisms does provide excellent opportunities to start seeing various ways of using representation theory (I will for instance prove Burnside’s irreducibility criterion and the linear independence of matrix coefficients using my understanding of Burnside’s original arguments). And I do intend to use this course to introduce some functorial language to the students, and I feel that abstract nonsense will be quite appealing after trying to make sense of the confusion that may arise from proving the transitivity formula for induction strictly using the “subset of functions on the group” model for induced representations…

Here’s a question about the module-over-the-group-algebra approach: what is the first (or simplest, or most fundamental) argument where it is better? The one I can think of for the moment — after going through the first chapter of my notes — is that it seems to give the simplest way to argue that a semisimple representation always contains an irreducible subrepresentation. (And of course this is only relevant for infinite-dimensional representations, since otherwise one can argue using dimension.)

[Update (23.2.2011): the first chapters are now online.]