Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
    
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-Alvarez 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
8  
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

5 Answers 5

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.

share|improve this answer

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

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.