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
    Commented Mar 14, 2010 at 22:07
  • $\begingroup$ Qiaochu, the spectrum does depend on the generator set used, surely? $\endgroup$
    – Mariano Suárez-Álvarez
    Commented 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
    Commented 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
    Commented 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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .