Spectral properties of Cayley graphs - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-20T13:20:00Z http://mathoverflow.net/feeds/question/18212 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/18212/spectral-properties-of-cayley-graphs Spectral properties of Cayley graphs Marcin Kotowski 2010-03-14T22:01:42Z 2012-12-27T10:12:48Z <p>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?</p> <p>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?</p> http://mathoverflow.net/questions/18212/spectral-properties-of-cayley-graphs/18216#18216 Answer by Qiaochu Yuan for Spectral properties of Cayley graphs Qiaochu Yuan 2010-03-14T22:30:12Z 2010-03-14T22:30:12Z <p>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$. </p> <p>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 <a href="http://qchu.wordpress.com/2010/03/07/walks-on-graphs-and-tensor-products/" rel="nofollow">in this blog post</a>.</p> <p>Finally, if $G$ is abelian, all of the finite-dimensional irreducible representations are one-dimensional. They can be identified with the <a href="http://en.wikipedia.org/wiki/Pontryagin_duality" rel="nofollow">Pontryagin dual</a> $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 <strong>dual</strong> group.</p> http://mathoverflow.net/questions/18212/spectral-properties-of-cayley-graphs/18218#18218 Answer by Mariano Suárez-Alvarez for Spectral properties of Cayley graphs Mariano Suárez-Alvarez 2010-03-14T22:52:40Z 2010-03-14T22:52:40Z <p>Just to keep the references close to the question, here are two computations of the spectra of a Cayley graph:</p> <ul> <li><p>Lovász, L. Spectra of graphs with transitive groups. Period. Math. Hungar. 6 (1975), no. 2, 191--195. <a href="http://www.ams.org/mathscinet-getitem?mr=MR0398886" rel="nofollow">MR0398886</a></p></li> <li><p>Babai, L. Spectra of Cayley graphs. J. Combin. Theory Ser. B 27 (1979), no. 2, 180--189. <a href="http://www.ams.org/mathscinet-getitem?mr=MR0546860" rel="nofollow">MR0546860</a></p></li> </ul> <p>(The prevalence of people named <em>László</em> 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!)</p> http://mathoverflow.net/questions/18212/spectral-properties-of-cayley-graphs/19746#19746 Answer by HenrikRüping for Spectral properties of Cayley graphs HenrikRüping 2010-03-29T18:08:18Z 2010-03-29T18:08:18Z <p>There is <a href="http://www.springerlink.com/content/qr2vqvk3m858m6wh/" rel="nofollow">this paper</a> 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.</p> http://mathoverflow.net/questions/18212/spectral-properties-of-cayley-graphs/20376#20376 Answer by Jean Lecureux for Spectral properties of Cayley graphs Jean Lecureux 2010-04-05T09:43:39Z 2010-04-05T09:43:39Z <p><a href="http://www.springerlink.com/content/bvl3421x255653k8/" rel="nofollow">This paper</a>, 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.</p> <p>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.</p> http://mathoverflow.net/questions/18212/spectral-properties-of-cayley-graphs/117313#117313 Answer by majid arezoomand for Spectral properties of Cayley graphs majid arezoomand 2012-12-27T10:12:48Z 2012-12-27T10:12:48Z <p>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.</p>