# Spectral properties of Cayley graphs

Let $G$ be a finite group. Do eigenvalues of its Cayley graph say anything about the algebraic properties of $G$? The spectrum of Cayley graph may depend on the presentation, so it's not a good invariant, but maybe something interesting can still be said here?

In the case of an infinite group, can Cayley graph be replaced by some suitable infinite-dimensional object (say, linear operator, a generalization of the graph's adjacency matrix) so that the object's spectral properties may carry some algebraic data about the group?

• Asking about the eigenvalues of the Cayley graph is equivalent to asking about the eigenvalues of G in its regular representation, which decomposes in a well-understood way into the irreducible representations of G. – Qiaochu Yuan Mar 14 '10 at 22:07
• Qiaochu, the spectrum does depend on the generator set used, surely? – Mariano Suárez-Álvarez Mar 14 '10 at 22:18
• Ah, right. You're actually asking about the eigenvalues of some sum of elements of G acting on its regular representation. I was a little too bold there; these eigenvalues depend on the eigenvalues of the elements of G themselves if and only if G is abelian, where the whole story is totally straightforward. – Qiaochu Yuan Mar 14 '10 at 22:21
• First, there are graphs which are Cayley graphs for more than one group. Second if $H$ is a subgroup of $G$, then the Cayley relative to the generating set $G\setminus H$ is the complement of $|G:H|$ copies of the complete graph $K_{|H|}$. So in general one can tell almost nothing about the group from the Cayley graph. – Chris Godsil Mar 15 '10 at 0:32

This paper, by A. Valette, is a survey devoted to this question, although he's more interested in infinite groups. In the infinite case, the "adjacency matrix" is a bounded operator on $\ell^2(\Gamma)$, and its spectrum makes sense. Of course, it depends on the generating set.

One of the first results he mentions is a theorem of Kesten : it is possible to recover the fact that $G$ is amenable, or free, by looking at this spectrum.

Just to keep the references close to the question, here are two computations of the spectra of a Cayley graph:

• Lovász, L. Spectra of graphs with transitive groups. Period. Math. Hungar. 6 (1975), no. 2, 191--195. MR0398886

• Babai, L. Spectra of Cayley graphs. J. Combin. Theory Ser. B 27 (1979), no. 2, 180--189. MR0546860

(The prevalence of people named László in this list is interesting. It reminds me of a little story I recently got from Wikipedia while hunting for a reference on the Higman-Sims group: the extraordinary fact that two people named 'Higman' discovered the same sporadic simple group!)

Just to keep the reference close to the question, I think that the manuscript of Petteri Kaski, Eigenvectors and Spectra of Cayley graphs,Helsinki university of technology, Spring Term 2002, is a very good reference.

I know at least one special case where your second question makes sense. If $G$ is a compact group, it has a category $\text{Rep}(G)$ of finite-dimensional unitary representations which break up into direct sums of irreducible representations. Fix a representation $V$ such that every irreducible representation appears in $V^{\otimes n}$ for some $n$. One can construct a graph $\Gamma(V)$ whose vertices are the irreducible representations of $G$ and where the number of edges from $A$ to $B$ is the multiplicity by which $B$ appears in $A \otimes V$. By the assumption, $\Gamma(V)$ is connected, and its combinatorial properties encode information about the behavior of the tensor powers of $V$, hence behavior about $G$.

When $G$ is finite, this graph has the property that its eigenvalues are precisely the character values $\chi_V(g)$ as $g$ runs through all conjugacy classes. But the great thing is that this statement still makes sense even when $G$ is infinite in a sense which is made precise in this blog post.

Finally, if $G$ is abelian, all of the finite-dimensional irreducible representations are one-dimensional. They can be identified with the Pontryagin dual $G^{\vee}$, which is discrete, and $\Gamma(V)$ becomes precisely the Cayley graph of $G^{\vee}$ with respect to the generators that make up $V$! So this is one sense in which the Cayley graph of an infinite group gives you algebraic data, but about its dual group.

There is this paper by Zuk, which gives a sufficient criterion for property (T) in terms of some spectral properties of a graph depending on a group $G$ with a generating set $S$. This graph is not the Cayley graph. But maybe it is still in the spirit of the question.