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 , with vertex set , edge set , and
is the “endpoints” map.)
What I knew about the Schreier graph of a group with respect to a subgroup and a (symmetric) generating set is that it should be -regular, and the combinatorial Laplace operator should be given by
for any function on . 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 on a set , one takes as vertices, and moves along edges (set up properly) from to for in the given subset of . 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 , but that doesn’t make it less natural.)
In any case, here is an illustration of the action graph for the symmetric group , with generators , acting on by evaluation:
Equivalently, this is the Schreier graph of with respect to , where is the stabilizer of .
As it should be, this graph is -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 ) would remain regular after removing loops and multiple edges, but the interested reader will have no problem checking that if is replaced by
removing loops and multiple edges from the corresponding action graph leads to a non-regular graph. (The vertex 1 has three neighbors then, namely , while the others have only 2.)
(The typesetting of the graph is done using the tkz-graph package already mentioned in my previous post.)