On Cayley Graphs on the Symmetric Group Generated by Tranpositions

Joel Friedman^{∗} Department of Mathematics University of British Columbia Vancouver, BC V6T 1Z2 CANADA jf@math.ubc.ca

May 10, 2000

Abstract

Given a connected graph, X, we denote by λ_{2} = λ_{2}(X) its smallest non-zero Laplacian eigenvalue.

In this paper we show that among all sets of n − 1 transpositions which generate the symmetric group, S_{n}, the set whose associated Cayley graph has the highest λ_{2} is the set {(1, n), (2, n), …, (n − 1, n)} (or the same with n and i exchanged for any i < n). For this set we have λ_{2} = 1.

This result follows easily from the following result. For any set of transpositions, T, we can form a graph on n vertices, G_{P}, by forming an edge {i, j} in G_{P} for each transposition (i, j) ∈ T. We prove that if G_{P} is bipartite, then λ_{2} of the Cayley graph associated to T is at most λ_{2}(G_{P}); left open is the compelling conjecture that the two λ_{2}’s are always equal. We discuss this and other generalizations of Bacher’s work, which dealt with the case T = {(1, 2), (2, 3), …, (n − 1, n)}.

1 Introduction

Let X = (V, E) be a finite graph on n = |V | vertices, possibly with self-loops and multiple edges. The Laplacian associated with X is the n × n matrix Δ = D − A, where A is the usual adjacency matrix and D is the diagonal matrix whose i, i entry is d_{i}, the degree of i. We have that Δ is symmetric and positive-semidefinite, and has real eigenvalues 0 = λ_{1} ≤ λ_{2} ≤ ⋯ ≤ λ_{n}; λ_{2} = λ_{2}(X) is non-zero iff X is connected. λ_{2} upper and lower bounds certain expansion coefficients in X (see [Tan84, AM85, Dod84, Alo86, Lub94]), and so λ_{2} can be viewed as a measure of expansion.

∗The author also wishes to thank the NSERC for supporting this research in part.

By Spec(X) we mean the multiset of eigenvalues of Δ = Δ(X). We will sometimes denote λ_{n} by λ_{max}. By a function on X or V we mean a real-valued function on V; by an eigenfunction we mean one with respect to Δ. If X is a graph, V (X) denotes X’s vertex set.

If G is a group and T a subset of G, the Cayley graph of G with respect to T is the directed graph X(G, T) with vertex set G and an edge (g, gt) for each g ∈ G and t ∈ T. If T is closed under taking inverses (i.e. for all T we have t ∈ T iff t^{−1} ∈ T), then X(G, T) can be viewed as a graph (i.e. an undirected graph).

If X is d-regular, i.e. d_{v} = d for all v, then A’s eigenvalues are precisely d minus Δ’s eigenvalues. Thus the study of the spectrum of the adjacency matrix is essentially the same as that of the Laplacian for regular graphs. This holds for Cayley graphs, since they are d-regular for d = |T |.

Let S_{n} be the symmetric group on n elements, which we take to be {1, …, n}. In this article we study λ_{2} of certain Cayley graphs on S_{n}, especially those generated by a minimal number of transpositions. In [Bac94], Bacher shows that the Cayley graph on S_{n} with respect to the generators T_{1} = {(1, 2), (2, 3), …, (n − 1, n)} has λ_{2} = 2 − 2 cos(π/n). In [FOW85, FH98, FH99], it was observed that with respect to the generators T_{2} = {(1, n), (2, n), …, (n − 1, n)} we have λ_{2} = 1. So in a sense the Cayley graph with respect to T_{2} is a much better expander than that with respect to T_{1}. One of the main goals of this paper is to prove that with respect to a set of n − 1 transpositions, the highest λ_{2} which can be achieved is 1.

Theorem 1.1 Let T be a set of n−1 transpositions from S_{n}. Then the Cayley graph on S_{n} with respect to T has λ_{2} ≤ 1, with equality iff for some i we have T = {(i, j)|j ≠ i}.

Theorem 1.1 is an easy consequence of the following interesting fact. To any set, T, of transpositions on S_{n}, we associate a primitive graph, G_{P}, with vertex set {1, …, n} and with an edge {i, j} for each (i, j) ∈ T.

Theorem 1.2 Let T be a set of transpositions in S_{n} whose primitive graph, G_{P}, is bipartite. Then λ_{2}(G_{P}) occurs as an eigenvalue in X(S_{n}, T) with multiplicity at least n − 1 times its multiplicity in G_{P}.

The above proposition is a more or less straightforward consequence of the methods of Bacher in [Bac94], where he proved the above for T = (1, 2), (2, 3), …, (n − 1, n).

The multiplicity statement in theorem 1.2 follows from standard representation theory (see [Dia88]). Namely, the eigenvalues of a Cayley graph X(G, T) (for any G and T) are those of the natural matrix associated with T acting on each irreducible; each eigenvalue of an irreducible gives rise to f eigenvalues in X, where f is the dimension of the irreducible. One irreducible representation on S_{n} is the standard representation (see [Ser82]), which can be viewed as the functions on {1, …, n} whose sum of values is zero (with S_{n} acting in the obvious way). It follows that the eigenvalues of X = X(S_{n}, T) corresponding to this representation are just λ_{2}, …, λ_{n} of G_{P}. Hence each λ_{i}(G_{P}), i ≥ 2, contributes an n−1 multiplicity of the same eigenvalue in X(S_{n}, T). (It also follows, by taking the k-th exterior power of the standard representation, that each sum of k distinct eigenvalues, λ_{i}(G_{P}), with i ≥ 2, contributes an \binom{n−1}{k} multiplicity of the same eigenvalue in X.) The same remark holds for any Cayley graph on S_{n}, with G_{P} replaced by X[1], where X[1] is defined below in section 2.

Theorem 1.1 follows from theorem 1.2 from the well known fact that λ_{2} ≤ 1 for any tree, with equality iff the tree has n − 1 leaves and one interior vertex of degree n − 1 (see [Moh91]).

Theorem 1.2 leads to the following fascinating conjecture:

Conjecture 1.3 λ_{2}(X(S_{n}, T)) = λ_{2}(G_{P}) whenever T is a set of transpositions with G_{P} bipartite.

As mentioned before, we know the above conjecture holds for T being T_{1} or T_{2} as above. It is also valid when G_{P} is the complete graph (see [DS81]), and a natural generalization of this conclusion is known to hold also when T is any conjugacy class in S_{n} (see [Roi96]).

The question of the exact multiplicity of λ_{2} in X(S_{n}, T) is interesting. For T = T_{2} as before, its multiplicity is exactly (n − 1)(n − 2) (see [FOW85, FH98, FH99]), which is n − 1 times its multiplicity in G_{P}. In theorem 1.2 we do not generally know when equality holds. When it doesn’t, it means there are some extra representations with the same eigenvalues; it would be interesting to know if this can happen.

The rest of this paper is organized as follows. In section 2 we recall the notion of a Schreier graph, and discuss a natural sequence of Schreier graphs needed here. In section 3 we outline the proof of theorem 1.2. In section 4 we discuss the pseudobipartiteness of the sequence of Schreier graphs; this shows a limitation of Bacher’s method to the case where G_{P} is bipartite. We also discuss some facts about eigenvalues in section 4. The rest of the details of the proof of theorem 1.2 are in section 5. In section 6 we close with some remarks on future directions, and prove that the representation theory eigenfunctions are the same as those constructed in sections 3–5. In appendix A we make some technical and bibliographical remarks on the notion of X[k] of section 2.

The author wishes to thank Jean-Pierre Tillich, Yuval Roichman, and Nick Pippenger for helpful discussions.

2 Some Schreier Graphs

Recall that for a subgroup H of a group G with T a subset of G, the Schreier graph on H\G with respect to T is the graph X = X(G, H, T) with vertex set being the right cosets H\G = {Hg|g ∈ G} and edges (Hg, Hgt) for each coset Hg and each t ∈ T. If T is closed under taking inverses then X can be viewed as a graph. Note that if 1 is the identity in G, we have X(G, {1}, T) = X(G, T), so the notion of a Schreier graph generalizes that of a Cayley graph. If H ⊂ K are subgroups of G, then the natural map H\G → K\G gives rise to a map X(G, H, T) → X(G, K, T) which is a covering map (see [Fri93]); in particular, the eigenvalues of X(G, K, T) are a subset of those of X(G, H, T).

Notice that Schreier graphs are regular, and so studying their Laplacian spectrum is equivalent to studying thier adjacency matrix spectrum.

Let T be a subset of S_{n}. The inclusion of {1, …, n − k} into {1, …, n} for k > 0 gives rise to an inclusion S_{n−k} ⊂ S_{n}, giving rise to a Schreier graph X[k] = X(S_{n}, S_{n−k}, T). The inclusion S_{n−m−1} ⊂ S_{n−m} for m = 0, …, n − 1 yields a sequence of covering maps:

X[n] → X[n − 1] → ⋯ → X[1] → X[0].  (2.1)

(Here we take S_{0} to be the one element group, so X[n] = X[n − 1] = X(S_{n}, T); also X[0] has one vertex.) Note (see [Bac94]) that X[k] can be viewed as the graph (V [k], E[k]), whose vertices are sequences I = (i_{1}, …, i_{k}) of length k of distinct integers of {1, …, n}, with an edge (I, t(I)) ∈ E for each t ∈ T and each I ∈ V, where t(I) = (t(i_{1}), …, t(i_{k})); actually S_{n−k} embeds naturally into S_{n} in \binom{n}{k} different ways, by acting on a subset of size n − k of {1, …, n}, and each embedding gives rise to an isomorphic X[k]; in fact, the I ∈ V [k] simply represent the image with respect to a (an S_{n−k}\S_{n}) coset element of the k elements of {1, …, n} which are not acted upon by S_{n−k}. It follows that the mapping X[m] → X[m − 1] on the vertices is just deletion of the first element.

For later use we mention that S_{k} acts on V [k] in the obvious way, and this action gives rise to one on V [k] functions which commutes with Δ.

3 The Proof of Theorem 1.2

In this section we outline the proof of theorem 1.2 and describe how the technique might generalize further. The details and proofs of certain lemmas are given in sections 4 and 5.

For theorem 1.2 we follow Bacher’s approach. Let T be, for the time being, an arbitrary collection of transpositions in S_{n} and let X[k] be as before. The first lemma is interesting but not hard:

Lemma 3.1 λ_{2}(X[n]) = 2|T | − λ_{max}(X[n − 2]).

It would be interesting to know what is the appropriate generalization for different T. We discuss possible generalizations and a proof of this lemma in section 4.

We will describe a natural candidate λ_{max}(X[n − 2]), or more generally λ_{max}(X[k]) for arbitrary k. Recall that S_{k} acts on V [k], and its resulting action on V [k] functions commutes with Δ.

Definition 3.2 A function u on V [k] is antisymmetric if for any s ∈ S_{k} and I ∈ V [k] we have u(s(I)) = sign(s)u(I). We denote the space of such functions by A[k].

Since Δ commutes with the S_{k} action, Δ leaves A[k] invariant. The dimension of A[k] is clearly \binom{n}{k}, and so there are \binom{n}{k} independent eigenfuntions in A[k]. The remarkable

fact is that we can exhibit all the \binom{n}{k} antisymmetric eigenfunctions and eigenvalues.

Theorem 3.3 The eigenvalues of Δ in A[k] are precisely

{∑_{i∈I} λ_{i} | I ⊂ {1, …, n}, |I| = k} ,

where {λ_{1}, ⋯, λ_{n}} = Spec(G_{P}) and G_{P} is the primitive graph of T.

We shall outline the proof of this theorem at the end of this section.

So the largest A[n − 2] eigenvalue is ν = λ_{3} + ⋯ + λ_{n}, and taking the trace of Δ shows that ν = 2|T | − λ_{2}. If ν is the largest X[n − 2] eigenvalue, then

λ_{2}(X[n]) = 2|T | − λ_{max}(X[n − 2]) = 2|T | − ν = λ_{2}(G_{P}).

Conversely if ν is not the largest X[n − 2] eigenvalue, then λ_{2}(X[n]) < λ_{2}(G_{P}).

We remark that Bacher essentially showed that ν is the largest X[n − 2] eigenvalue when X[n − 2] is “pseudo-bipartite,” in the sense below.

Definition 3.4 We say that a graph, X, is pseudo-bipartite if X is bipartite when all self-loops are removed. A bipartition of pseudo-bipartite graph, X = (V, E), is a map sign: V → {±1} such that sign(u), sign(v) differ whenever u ≠ v and {u, v} ∈ E.

Unfortunately X[n−2] is pseudo-bipartite only when T is T_{1} as in the introduction. Still, as remarked above, ν = λ_{3}+⋯+λ_{n} is an eigenvalue of X[n−2], and so theorem 1.2 follows. It remains to discuss the proof of theorem 3.3 in more detail.

There is a standard notion of the (Cartesian) product of graphs (see section 5), giving rise to a notion of a power, X^{r}, for any graph X = (V, E) and integer r ≥ 1. We define another notion of antisymmetric, for functions on X^{r}. A σ ∈ S_{r} acts on V (X^{r}) = V^{r} by permuting indices, i.e.

σ(v_{1}, …, v_{r}) = (v_{σ(1)}, …, v_{σ(r)}).

Definition 3.5 A function u on X^{r} is antisymmetric if u(σ(v)) = sign(σ)u(v) for all v ∈ V (X^{r}) and σ ∈ S_{r}.

Again, it is easy to find the dimension of the antisymmetric functions; it is \binom{n}{r} where n = |V (X)|. And again, Δ of X^{r} commutes with the S_{r} action on functions, and hence leaves the antisymmetric functions invariant. It is easy to compute the antisymmetric part of the spectrum:

Lemma 3.6 The eigenvalues corresponding to antisymmetric eigenvalues of Δ on X^{r} are precisely:

{∑_{i∈I} λ_{i} | I ⊂ {1, …, n}, |I| = r}

where {λ_{1}, ⋯, λ_{n}} = Spec(X).

Proof See section 5.

The crux of Bacher’s method is the following remarkable observation, appropriately generalized to our setting:

Theorem 3.7 The antisymmetric spectrum of X[k] equals that of G_{P}^{k}.

Proof There is an obvious map of vertex sets, B: V [k] → V (G_{P}^{k}), namely inclusion. While this map is not a morphism of graphs (i.e. does not preserve edge incidences), remarkably enough B^{∗}, the pullback of G_{P}^{k} functions to X[k] functions, does preserve Δ when restricted to antisymmetric functions (and pulls back antisymmetric functions to antisymmetric functions). See section 5 for the details.

□

Theorem 3.7 and lemma 3.6 yield theorem 3.3. This completes our proof of theorem 1.2 (modulo the details in sections 4 and 5).

4 Eigenvalues and Quotients

In this section we prove lemma 3.1. We prove it from two observations. The first one is clear:

Proposition 4.1 If X is d-regular, bipartite graph, and if sign is a bipartition of X, then the map f ↦ f sign maps eigenfunctions to eigenfunctions, with λ ↦ 2d − λ the corresponding map on eigenvalues.

Since X[n] is |T |-regular and bipartite, we have λ_{N−1} = 2|T | − λ_{2} where N = n!. This holds whenever T is a collection of sign −1 elements of S_{n}. The following proposition requires T to consist entirely of elements of order two:

Proposition 4.2 Let S be a group of order N, and T a set of generators with t^{2} = 1 for all t ∈ T. Then

λ_{N−1}(X(S, T)) = max_{t∈T} λ_{max}(X(S, {1, t}, T)).

Proof We begin with two remarks. First, if f is an X(S, T) eigenfunction and s ∈ S, then the function g given by g(u) = f(su) is also an eigenfunction of the same eigenvalue; more generally, Δ commutes with the “left multiplication” action of S on functions. Secondly, if H is a subgroup of S and f is an X(S, T) eigenfunction which is constant on all H\S cosets, then f can be viewed as a function f̃ on X(S, H, T), and f̃ is an eigenfunction with the same eigenvalue as f; more generally, π ∘ Δ_{X(S,T)} = Δ_{X(S,H,T)} ∘ π, where π is the natural map from functions on S constant on right H cosets to functions on H\S.

Let f be an eigenfunction corresponding to λ_{N−1} = λ_{N−1}(X(S, T)). Let v be such that f(v) ≠ 0. Then (λ_{N−1} − |T |)f(v) is − ∑_{t∈T} f(vt), and λ_{N−1} = 2|T | − λ_{2} < 2|T |, so we have that f(v) + f(vt) ≠ 0 for some t. Then the function g_{t} given by g_{t}(u) = f(vu)+f(vtu) gives another eigenfunction with the same eigenvalue as that of f. Also g_{t} does not vanish identically, and is invariant on right {1, t} cosets. Hence g_{t} is an X(S, {1, t}, T) eigenfunction, and thus λ_{N−1} ≤ λ_{max}(X(S, {1, t}, T)), and so

λ_{N−1} ≤ max_{t∈T} λ_{max}(X(S, {1, t}, T)).  (4.1)

We now prove the reverse inequality to equation 4.1. We begin by claiming that for any t we have λ_{max}(X(S, {1, t}, T)) < 2|T |; indeed, X(S, {1, t}, T) is connected (since X(S, T) is), is |T |-regular, and has a self-loop. So if f is an eigenfunction with eigenvalue 2|T |, then it is easy to see that the set where |f| takes its maximum is: (1) nonempty, (2) closed under taking neighbors, and (3) cannot include vertices where Δ has a self-loop. This contradiction shows that λ_{max}(X(S, {1, t}, T)) < 2|T |.

Now notice that Spec(X(S, {1, t}, T)) ⊂ Spec(X(S, T)), and λ_{N}(X(S, T)) = 2|T |. So λ_{max}(X(S, {1, t}, T)) < 2|T | implies that

λ_{max}(X(S, {1, t}, T)) ≤ λ_{N−1}.

Since this holds for all t we conclude, using equation 4.1, the proposition.

□

We finish the proof of lemma 3.1 by noticing that when T is a subset of transpositions of S_{n}, X[n − 2] is isomorphic to X(S_{n}, {1, t}, T) for any t ∈ T.

□

5 More Details of the Proof

We begin by proving lemma 3.6, starting by describing the Cartesian product of two graphs X = (V, E) and Y = (W, F). It is the graph X × Y = (V × W, E), where E consist of two types of edges: for each {v_{1}, v_{2}} ∈ E and each w ∈ W we form an edge {v_{1} × w, v_{2} × w}, and similarly for each F edge and V vertex. We have Δ(X × Y) = Δ(X)⊗I_{W} +I_{V} ⊗Δ(Y), where I_{V} , I_{W} are identity matrices. It follows that if {f_{i}}, {g_{j}} are bases of X, Y eigenfunctions with eigenvalues {λ_{i}}, {ν_{j}}, then {f_{i} ⊗ g_{j}} is a X × Y basis of eigenfunctions with eigenvalues {λ_{i} + ν_{j}} (here f_{i} ⊗ g_{j}(v, w) = f_{i}(v)g_{j}(w)).

The Cartesian product gives a notion of a power of a graph, X^{r}. If F(Y) denotes the functions on a graph, Y, then F(X^{r}) is isomorphic to (F(X))^{⊗r}. Under the S_{r} action described in section 3, we have that the space of antisymmetric functions on X is just ⋀^{r}(F(X)) viewed as a subspace of (F(X))^{⊗r}. It follows that if {f_{i}} is a basis for F(X), then

{f_{i_{1}} ∧ ⋯ ∧ f_{i_{r}} | 1 ≤ i_{1} < ⋯ < i_{r} ≤ n}

is a basis for the antisymmetric functions, where

f_{i_{1}} ∧ ⋯ ∧ f_{i_{r}} = \frac{1}{r!} ∑_{σ∈S_{r}} sign(σ)f_{i_{σ}(1)} ⊗ ⋯ ⊗ f_{i_{σ}(r)}.

If the {f_{i}} are also eigenfunction of eigenvalues {λ_{i}}, then clearly each f_{i_{1}} ∧ ⋯ ∧ f_{i_{r}} is an eigenfunction of eigenvalue λ_{i_{1}} + ⋯ + λ_{i_{r}}. This therefore produces a basis of eigenfunctions, and so proves lemma 3.6.

□

We finish with the heart of Bacher’s method, which is the proof of theorem 3.7. So let G_{P} = (V, E), note V (G_{P}^{k}) = V^{k}, note that V [k] ⊂ V^{k} (since V = {1, …, n}), and let B: V [k] → V^{k} be the inclusion. Consider an antisymmetric eigenfunction, f, of eigenvalue λ on G_{P}^{k}. Fix I = (i_{1}, …, i_{k}) ∈ V [k]; we wish to calculate (Δ(B^{∗}f))(I) and to compare it to (Δ(f))(I). First consider the J ∈ V [k] adjacent to I in X[k]; we will divide them into two types. Let S denote the set of J = (j_{1}, …, j_{k}) ∈ V [k] such that for some a ∈ {1, …, k} we have j_{m} = i_{m} for m ≠ a and (i_{a}, j_{a}) ∈ T and j_{a} is distinct from i_{1}, …, i_{k}. Next let T denote the set of J = (j_{1}, …, j_{k}) ∈ V [k] such that for some a, b ∈ {1, …, k} with a < b we have (i_{a}, i_{b}) ∈ T, j_{m} = i_{m} for m ≠ a, b, j_{a} = i_{b}, and j_{b} = i_{a}. Clearly S and T are disjoint, and clearly their union is precisely the set of J which are ≠ I and adjacent to I in X[k]. Notice also that for each such J, the edge {I, J} in X[k] has multiplicity one. Now for J ∈ T we have that J is obtained from I by switching two coordinates, and so f(J) = −f(I). It follows that

(Δ(B^{∗}f))(I) = |S ∪ T |f(I) − ∑_{J∈S∪T} f(J) = |S ∪ T |f(I) − ∑_{J∈S} f(J) − ∑_{J∈T} f(J)

= |S ∪ T |f(I) − ∑_{J∈S} f(J) − |T |(−f(I)) = (|S| + 2|T |)f(I) − ∑_{J∈S} f(J).

Now consider the J ∈ V^{k} adjacent to I in G_{P}^{k}. Clearly if J ∈ S, then J is adjacent to I in G_{P}^{k}. However, J ∈ T are not adjacent to I in G_{P}^{k}; instead, for every a < b such that (i_{a}, i_{b}) ∈ T, we have two G_{P}^{k} edges to I; namely the J such that j_{a} = j_{b} = i_{a} and j_{m} = i_{m} for all m ≠ a, b, and J′ with j′_{a} = j′_{b} = i_{b} and j′_{m} = i_{m} for all m ≠ a, b. Notice that such J, J′ have the same a-th and b-th coordinates, and so f(J) = f(J′) = 0. So if the set of such J, J′ is denoted T′, we have |T′| = 2|T |. Clearly S, T′ give all J which are ≠ I and adjacent to I in G_{P}^{k}, and for each such J the edge {I, J} has multiplicity one in G_{P}^{k}, and so

(Δ(f))(I) = |S ∪ T′|f(I) − ∑_{J∈S∪T′} f(J) = (|S| + 2|T |)f(I) − ∑_{J∈S} f(J).

It follows that (Δ(B^{∗}f))(I) = (Δ(f))(I), and so (Δ(B^{∗}f))(I) = λf(I) for all I ∈ V [k]. Hence B^{∗}f is a X[k] eigenfunction with eigenvalue λ. Since all antisymmetric functions on G_{P}^{k} vanish on the vertices V^{k} − V [k], we have that B^{∗} is an injection on the space of antisymmetric V^{k} functions. Hence the basis of \binom{n}{k} antisymmetric eigenfunctions for V^{k} maps to a family of linearly independent V [k] eigenfunctions under B^{∗}. Furthermore, B^{∗} clearly maps antisymmetric functions to antisymmetric functions. Since the dimension of antisymmetric function on V [k] is also \binom{n}{k}, the antisymmetric eigenvalues of V^{k} are precisely those of V [k].

6 Concluding Remarks

As for future work, especially regarding the question of Lubotzky, perhaps the following approach is the most interesting.

An involution, σ, is an element of S_{n} such that σ^{2} = 1. Such a σ is a product of disjoint transpositions, and we further call σ an odd involution if it has an odd number of transpositions. If T consists entirely of odd involutions of S_{n} then from the propositions at the beginning of section 4 we have:

λ_{2}(X(S_{n}, T)) = 2|T | − max_{t∈T} λ_{max}(X(S, {1, t}, T)).

While the class of odd involution generated Cayley graphs on S_{n} is a very restricted class, and may not yield the best expanders among all possible Cayley graphs on S_{n} (of a fixed degree), it seems that there could be enough “randomness” among such graphs to get a pretty good expander (compared with the best possible). For example, if n ≡ 2 (mod 4), then any perfect matching of {1, …, n} gives an odd involution, and a “random” collection of a small number of such involutions might behave almost as “randomly” (i.e. give expansion as good) as a random Cayley graph of the same degree. Perhaps the above formula could be of use.

Notice that in the above we stick to involutions. It would be nice to have a formula for λ_{N−1}(X(S, T)) in terms of λ_{max} of certain quotients, for (more) general groups S and generators T. Notice that the expression

max_{t∈T} λ_{max}(X(S, ⟨t⟩, T))

is not generally equal to λ_{N−1}(X(S, T)) (here ⟨t⟩ is the subgroup generated by t). (Take S to be a cyclic group of order > 2, and T = {t, t^{−1}} where t is a generator of S.)

Finally we mention the interesting question of the multiplicity of λ_{2} in general Cayley graphs X(S_{n}, T). If the multiplicity of λ_{2} in X(S_{n}, T) is greater than n−1 times that in X[1], it would mean there are some other representations whose corresponding eigenfunctions achieve an eigenvalue of λ_{2}. It would be interesting to know what these representations and eigenfunctions are. Perhaps such T represent borderline cases between those where λ_{2}(X(S_{n}, T)) < λ_{2}(X[1]) and those where they are equal.

As for eigenfunctions, it is interesting to compare the representation theory eigenfunctions with those constructed in Bacher’s approach. We finish this section by showing that the two sets of eigenfunctions constructed span the same space.

The representation theory eigenfunctions arise from how the standard representation lies in the regular representation. To understand this, let G_{P} = (V, E) as before, so that V = {1, …, n}, let C(A) for a set A denote the real-valued functions on A, and let S be those elements of C(V) with sum over all vertices equal zero. Then S_{n} acts on V in the obvious way, which gives the S_{n} action on S, σ(f)(v) = f(σ(v)) for v ∈ V, f ∈ S, and σ ∈ S_{n}. Clearly S is the standard representation.

Recall that V [n] is the set of n-tuples (v_{1}, …, v_{n}) with distinct v_{i} in {1, …, n}, and that V [n] is identified with S_{n} with a σ ∈ S_{n} corresponding to (σ(1), …, σ(n)). Projection onto the j-th coordinate gives a map π_{j}: V [n] → V; this gives rise to an embedding π_{j}^{∗} of S into C(V [n]) ≃ C(S_{n}), and hence to a copy of S in C(S[n]) which we denote S_{j} = π_{j}^{∗}(S). We claim that S_{1}, …, S_{n−1} are independent subspaces of C(S_{n}). This follows immediately from the lemma below:

Lemma 6.1 Let f_{i} ∈ C(V) for i = 1, …, n−1 satisfy π_{1}^{∗}f_{1} +⋯+π_{n−1}^{∗}f_{n−1} = 0. Then each f_{i} is constant on V.

Proof For any distinct v_{1}, …, v_{n} in V we have

f_{1}(v_{1}) + f_{2}(v_{2}) + ⋯ + f_{n−1}(v_{n−1}) = 0 = f_{1}(v_{n}) + f_{2}(v_{2}) + ⋯ + f_{n−1}(v_{n−1}),

and so f_{1}(v_{1}) = f_{1}(v_{n}). It follows that for any distinct v_{1}, v_{n} ∈ V (we can find v_{2}, … so that the v_{i} are distinct and hence) we have f_{1}(v_{1}) = f_{1}(v_{n}). Hence f_{1} is constant on V. Similarly so are the other f_{i}.

□

The above gives us n − 1 independent embeddings of S into C(S_{n}) (and we know this is the maximum possible). So if f_{1}, …, f_{n} are a basis of eigenfunctions for G_{P} corresponding to eigenvalues 0 = λ_{1} ≤ ⋯ ≤ λ_{n}, then f_{ij} = π_{j}^{∗}f_{i}, i.e.

f_{ij}(v_{1}, …, v_{n}) = f_{i}(v_{j}),

gives for i ≥ 2 and j = 1, …, n − 1 independent X(S_{n}, T) eigenfunctions of eigenvalue λ_{i}. These are “the” representation theory eigenfunctions; of course, the particular functions depend on our n − 1 embeddings of S in C(S_{n}); yet their span does not depend on the embeddings.

Of course, π_{1}^{∗} +⋯+π_{n}^{∗} is zero on S, so we cannot add j = n to the above collection of functions. Similarly f_{ij} for i ≥ 2 and j ranging over any n − 1 values of {1, …, n} gives independent eigenfunctions with the same span as above.

Next we show that the eigenfunctions implicitly described in sections 3–5 give a different but equivalent set of eigenfunctions. So for each t ∈ T, t = (j, k), let π_{t}: V [n] → V [n − 2] be the map dropping the j-th and k-th coordinates. For each i ∈ {1, …, n} let

F_{i} = f_{2} ∧ f_{3} ∧ ⋯ ∧ f_{i−1} ∧ f_{i+1} ∧ ⋯ ∧ f_{n}.

Then f̃_{it} = sign · π_{t}^{∗}F_{i} is an eigenfunction of eigenvalue λ_{i}.

Theorem 6.2 The f̃_{it}, for i ≥ 2 and t ∈ T span the same space as the f_{ij}, i ≥ 2 and j ∈ {1, …, n}.

Proof This theorem follows quite easily from the theorem below. For any set A there is a natural inner product on C(A), (f, g) = ∑_{a∈A} f(a)g(a).

Theorem 6.3 Assume that f_{1}, …, f_{n} are orthogonal. Then for each i ≥ 2 and t = (j, k) ∈ T there is a c ≠ 0 such that f̃_{it} = c(f_{ik} − f_{jk}).

Proof Without loss of generality we may assume t = (1, 2). Clearly f̃_{it}(v_{1}, …, v_{n}) is invariant upon exchanging any two of v_{3}, …, v_{n} (since the sign and the π_{t}^{∗}F_{i} each contribute a −1 to such an exchange). Hence f̃_{it}(v_{1}, …, v_{n}) = f̃_{it}(v_{1}, v_{2}) is a function of v_{1} and v_{2}. Also f̃_{it}(v_{2}, v_{1}) = −f̃_{it}(v_{1}, v_{2}), since π_{t}^{∗}F_{i} is invariant upon exchanging the first two variables, and sign gives a −1 upon this exchange. It follows that f̃_{it} ∈ ⋀^{2}(C(V)), and so

f̃_{it}(v_{1}, v_{2}) = ∑_{a<b} c_{ab}f_{a} ∧ f_{b}(v_{1}, v_{2})

for some constants c_{ab}. A standard (and easy) calculation show that since the f_{a} are orthogonal, so are the f_{a} ∧ f_{b} (in the C(V [2]) inner product). So c_{ab} = 0 iff (f̃_{it}, f_{a} ∧ f_{b}) = 0; we now check the latter. Now

(f̃_{it}, f_{a} ∧ f_{b})_{V [2]} = (n − 2)!( sign · π_{t}^{∗}F_{i}, f_{a} ∧ f_{b} ⊗ 1 ⊗ ⋯ ⊗ 1)_{V [n]}
= (n − 2)!( sign, f_{a} ∧ f_{b} ⊗ F_{i})_{V [n]},

and the right-hand-side clearly vanishes unless a = 1 and b = i. Hence f̃_{it} = c_{1i}f_{1} ∧ f_{i}(v_{1}, v_{2}) = c(f_{i}(v_{2}) − f_{i}(v_{1})) since f_{1} is constant. Thus f̃_{it} = c(f_{ik} − f_{ij}), and clearly c ≠ 0 since f̃_{it} is not identically zero (since F_{i} isn’t).

□

We remark that the above theorem needs the orthogonality condition. For f_{ij}, f_{ik} depend only on f_{i}, while f̃_{it} depends on all f_{m} except m = i, 1. So if f_{i} corresponds to an eigenvalue of multiplicity s > 1, holding f_{m} fixed for m ≠ i, 1 and varying f_{i} keeps f̃_{it} fixed while lets f_{1} ∧ f_{i} vary over an s-dimensional space minus some 1-dimensional subspaces.

Now we finish the proof of theorem 6.2. First assume that the f_{i} are orthogonal. We are reduced to proving the following: let W be a vector space with w_{1}, …, w_{n} ∈ W satisfying w_{1} + ⋯ + w_{n} = 0 but are otherwise independent (i.e. any n − 1 of them are independent). Then the span of the w_{i} equals the span of w_{k} − w_{j} over all (j, k) ∈ T. Clearly the span of the latter lies in that of the former. So let H = (V, F) be a spanning tree of G_{P}, let r ∈ V be an arbitrary vertex (thought of as the root of H), and orient the edges of F “away from r” (so H is now a directed tree). It suffices to show that w̃_{t} = w_{k} − w_{j} over t = (j, k) ∈ F are linearly independent.

First note that ∑ d_{i}w_{i} = 0 and ∑ d_{i} = 0 implies that all the d_{i} are zero. Now assume that ∑_{t∈F} c_{t}w̃_{t} = 0 with c_{t} ≠ 0 for some t. Then ∑ c_{t}w̃_{t} = ∑ d_{i}w_{i} with

d_{i} = ∑_{t=(j,i)∈F} c_{t} − ∑_{t=(i,j)∈F} c_{t}.

So clearly ∑ d_{i} = 0. But if t = (i, j) is an edge of maximal distance from r with c_{t} ≠ 0, the d_{j} = c_{t} ≠ 0, a contradiction

Finally, we consider general f_{2}, …, f_{n} (i.e. not necessarily orthogonal). We have that the span of {f_{i}}_{i≥2} is the orthogonal complement of f_{1}, regardless of the choice of {f_{i}}_{i≥2}. Hence the span of the f_{ij} = π_{j}^{∗}f_{i} is independent of the choice of {f_{i}}_{i≥2}. Similarly the span of F_{i} (with i ≥ 2) is the orthogonal complement of

{f_{1} ∧ w | w ∈ ⋀^{n−3}(F(V))}.

Hence the span of f̃_{it} = π_{t}^{∗}F_{i} is independent of the choice of {f_{i}}_{i≥2}.

□

A Remarks on X[k]

After one paragraph of minor technical remarks on X(G, H, T) we spend the rest of this section making bibliographical remarks about X[k].

Notice that there is some ambiguity in how to make X(G, H, T) into an undirected graph (in the presence of multiple edges or self-loops). But these ambiguities don’t affect Δ (or the adjacency matrix), and are easily resolved by insisting that T come with an involution σ such that t(σ(t)) = 1 for all t. Also, we can weaken the condition that T be closed under taking inverses to T coming with an involution σ such that t(σ(t)) lies in the core^{1} of H in G for all t.

1The core of H in G is ⋂_{g∈G} gHg^{−1}, i.e. the largest normal subgroup of G lying in H.

We now briefly remark on where λ_{2} of the graphs X[k] has been studied elsewhere. First, in the contexts of random graphs, if we take d random elements of S_{n}, take their inverses, we get a set, T, of 2d elements of S_{n} closed under taking inverses. The resulting X[1] is the usual model of a random regular graph studied in [BS87, FKS89, Fri91]; in [Fri91] it is shown that λ_{2} = 2d − 2\sqrt{2d} + O(log d) with high probability as n → ∞; unresolved is the conjecture of Alon (see [Alo86]) that λ_{2} ≥ 2d − 2\sqrt{2d − 1} − ϵ for any ϵ > 0 with high probability, even though numerical evidence indicates that λ_{2} ≥ 2d − 2\sqrt{2d − 1} probably holds in most cases (see [Fri93]). The study of λ_{2} of X[k] becomes important to the “quick k-transitivity” of the graph X[1] (see [FJR^{+}96]), where a question in cryptography can be resolved using the fact that λ_{2} of X[k] is ≥ 2d − 2d(1 + ϵ)d^{−1/(k+1)}(2d − 1)^{1/(2k+2)} with high probability (for any fixed ϵ > 0, with k, d fixed and n → ∞).

Second, Lubotzky (see [Lub95]) asks whether there are Cayley graphs on S_{n} which are expanders, in the sense that there should exist a d and ϵ > 0 and sequence X_{n} of d-regular Cayley graphs on S_{n} with λ_{2}(X_{n}) ≥ ϵ. In other words, is there a fixed d and ϵ > 0 such that for any n there is a subset T ⊂ S_{n} of size d with λ_{2}(X(S_{n}, T)) ≥ ϵ. In the language of the previous paragraph, X(S_{n}, T) = X[n], and so the previous question is one about λ_{2}(X[n]) for the optimal T of a certain size. Equation 2.1 gives rise to an inclusion of spectra:

Spec(X[0]) ⊂ Spec(X[1]) ⊂ ⋯ ⊂ Spec(X[n]).  (A.1)

From the previous paragraph we know that for any k there are d and ϵ > 0 such that for any n we have λ_{2}(X[k]) ≥ ϵ for some T of size d. So even if the answer to Lubotzky’s question is negative, we might ask for which functions f(n) is there a d and ϵ > 0 such that for all n we have the same holding with k = f(n); in other words, at which point in equation A.1 do small Laplacian eigenvalues enter in? We can also ask a similar question where d varies with n; this has been studied for T being a conjugacy class by Roichman in [Roi97].

Thirdly, in the context of the main theorems in this paper, we are saying that in equation A.1, between Spec(X[1]) and Spec(X[n]), all new eigenvalues arising are at least as great as λ_{2}(X[1]), in a certain special case. Indeed, if T consists entirely of transpositions, then if we take X[1] and delete all its self-loops (of which there are very very many), we get T ’s primitive graph, G_{P}. So Spec(G_{P}) = Spec(X[1]); and the relationship between theorem 1.2 and the above is clear. It would be quite remarkable if such relations between Spec(X[1]) and Spec(X[n]) held for a large class of T (if it held for most T of fixed size d as n → ∞ then Lubotzky’s question would be true); it might be interesting to ask for which T this holds.

References

[Alo86] Noga Alon. Eigenvalues and expanders. Combinatorica, 6(2):83–96, 1986.

[AM85] N. Alon and V.D. Milman. λ_{1}, isoperimetric inequalities for graphs and superconcentrators. J. Comb. Theory Ser. B, 38:73–88, 1985.

[Bac94] Roland Bacher. Valeur propre minimale du laplacien de Coxeter pour le group symétrique. Journal of Algebra, 167:460–472, 1994.

[BS87] Andrei Broder and Eli Shamir. On the second eigenvalue of random regular graphs. In 28th Annual Symposium on Foundations of Computer Science, pages 286–294, 1987.

[Dia88] Persi Diaconis. Group Representations in Probability and Statistics. Institute of Mathematical Statistics, Hayward, California, 1988.

[Dod84] Jozef Dodziuk. Difference equations, isoperimetric inequality and transcience of certain random walks. Trans. AMS, 284:787–794, 1984.

[DS81] P. Diaconis and M. Shahshahani. Generating a random permutation with random transpositions. Z. Wahrscheinlichkeitstheorie verw. Gebiete, 57:159– 179, 1981.

[FH98] Joel Friedman and Phil Hanlon. On the Betti numbers of chessboard complexes. J. Algebraic Combin., 8(2):193–203, 1998.

[FH99] Joel Friedman and Phil Hanlon. Erratum: “On the Betti numbers of chessboard complexes” [J. Algebraic Combin. 8 (1998), no. 2, 193–203; MR 2000c:05155] by J. Friedman and P. Hanlon. J. Algebraic Combin., 9(1):95+11, 1999.

[FJR^{+}96] J. Friedman, A. Joux, Y. Roichman, J. Stern, and J-P. Tillich. The action of a few random permutations on r-tuples and an application to cryptography. In STACS, pages 375–386, 1996.

[FKS89] J. Friedman, J. Kahn, and E. Szemerédi. On the second eigenvalue of random regular graphs. In 21st Annual ACM Symposium on Theory of Computing, pages 587–598, 1989.

[FOW85] L. Flatto, A.M. Odlyzko, and D.B. Wales. Random shuffles and group representations. Annals of Probability, 13:154–178, 1985.

[Fri91] J. Friedman. On the second eigenvalue and random walks in random dregular graphs. Combinatorica, 11:331–362, 1991.

[Fri93] Joel Friedman. Some geometric aspects of graphs and their eigenfunctions. Duke J. Math, 69:487–525, 1993.

[Lub94] Alexander Lubotzky. Discrete Groups, Expanding Graphs and Invariant Measures. Birkhauser, 1994.

[Lub95] A. Lubotzky. Cayley graphs: Eigenvalues, expanders and random walks. 1994/95. preprint.

[Moh91] B. Mohar. The Laplacian spectrum of graphs. In O.R. Ollermann Y. Alavi, G. Chartrand and A.K. Schwenk, editors, Graph theory, combinatorics and applications, pages 871–898, New York, 1991. Wiley.

[Roi96] Yuval Roichman. Upper bound on the characters of the symmetric groups. Invent. Math., 125(3):451–485, 1996.

[Roi97] Yuval Roichman. Expansion properties of Cayley graphs of the alternating groups. J. Combin. Theory Ser. A, 79(2):281–297, 1997.

[Ser82] Jean-Pierre Serre. Linear representations of finite groups. Springer-Verlag, 1982.

[Tan84] R.M. Tanner. Explicit concentrators from generalized n-gons. SIAM J. Alg. Disc. Methods, 5:287–293, 1984.