18
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ 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. $\endgroup$
    – Qiaochu Yuan
    Mar 14, 2010 at 22:07
  • $\begingroup$ Qiaochu, the spectrum does depend on the generator set used, surely? $\endgroup$
    – Mariano Suárez-Álvarez
    Mar 14, 2010 at 22:18
  • $\begingroup$ 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. $\endgroup$
    – Qiaochu Yuan
    Mar 14, 2010 at 22:21
  • 10
    $\begingroup$ 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. $\endgroup$
    – Chris Godsil
    Mar 15, 2010 at 0:32

7 Answers 7

Reset to default
9
$\begingroup$

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.

Improve this answer
$\endgroup$
4
$\begingroup$

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

Improve this answer
$\endgroup$
3
$\begingroup$

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.

Improve this answer
$\endgroup$
2
$\begingroup$

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.

Improve this answer
$\endgroup$
2
$\begingroup$

There is the paper Property (T) and Kazhdan constants for discrete groups by Andrzej Żuk, 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.

Improve this answer
$\endgroup$
0
1
$\begingroup$

Just for other reference, we showed that a finite DS group is solvable, and every non-cyclic Sylow subgroup of a finite DS group is of order $4$, $8$, $16$ or $9$. You can find more results in the below link: https://www.worldscientific.com/doi/10.1142/S0219498816501759

In these cases, the DS property of Cayley graphs of a group can say something about its structure.

Improve this answer
$\endgroup$
1
$\begingroup$

The following is a recent survey (preprint) on eigenvalues of Cayley (di)graphs.

Liu and Zhou, Eigenvalues of Cayley graphs (2022), Preprint link: https://arxiv.org/pdf/1809.09829.pdf

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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