Spectral properties of Cayley graphs - MathOverflow

Spectral properties of Cayley graphs

2010-03-14T22:01:42Z

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?

Answer by Qiaochu Yuan for Spectral properties of Cayley graphs

2010-03-14T22:30:12Z

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.

Answer by Mariano Suárez-Alvarez for Spectral properties of Cayley graphs

2010-03-14T22:52:40Z

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

Answer by HenrikRüping for Spectral properties of Cayley graphs

2010-03-29T18:08:18Z

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.

Answer by Jean Lecureux for Spectral properties of Cayley graphs

2010-04-05T09:43:39Z

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.

Answer by majid arezoomand for Spectral properties of Cayley graphs

2012-12-27T10:12:48Z

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.