Classical groups
Finite groups
Group schemes
Topological groups
Lie groups
Super-Lie groups
Higher groups
Cohomology and Extensions
Related concepts
homotopy theory, (∞,1)-category theory, homotopy type theory
flavors: stable, equivariant, rational, p-adic, proper, geometric, cohesive, directed…
models: topological, simplicial, localic, …
see also algebraic topology
Introductions
Definitions
Paths and cylinders
Homotopy groups
Basic facts
Theorems
Given a finite group with a set of generators , its Cayley graph is, just as any undirected graph, encoded by its adjacency matrix
and the eigenvalues of this matrix are referred to as the spectrum of the Cayley graph.
More generally, any coloring function
namely a function from the underlying set of to the complex numbers (for definiteness), induces the matrix
and the eigenvalues of this matrix are the Cayley graph spectrum for coloring .
For example:
if is the characteristic function of the given set of generators of , then (3) reduces to the adjacency matrix (1).
if is the minimal number of generators needed to express , then (3) is the graph distance-matrix of the Cayley graph – specifically the original Cayley distance matrix if is a symmetric group and its subset of transpositions;
if is the exponentiated graph distance, then (3) is the kernel matrix corresponding to the Cayley graph – specifically the Cayley distance kernel if is a symmetric group and its subset of transpositions.
(character formula for Cayley graph spectra)
If the coloring function (2) is a class function, then the eigenvalues of the color matrix (3) are
indexed by the irreducible characters of ,
given by the formula
appear with multiplicity ;
the corresponding eigenvectors are the complex conjugated component functions
of the complex irreducible representations whose characters are the , regarded for each as unitary matrices .
(Diaconis & Shahshahani 81, Cor. 3, Rockmore, Kostelec, Hordijk & Stadler 02, Thm. 1.1, Foster-Greenwood & Kriloff 16, Thm. 4.3, see also Liu & Zhou 18, Thm. 2.6; in the special case that is an abelian group the result is due to Lovász 1975, Babai 79, Cor. 3.2; a comprehensive account is in Kaski 02, Sec. 2 & 4, Cor. 5.4)
László Lovász, Spectra of graphs with transitive groups, Period. Math. Hungar., 6(2):191–195, 1975 (doi:10.1007/BF02018821, pdf)
László Babai, Spectra of Cayley graphs, Journal of Combinatorial Theory, Series B Volume 27, Issue 2, October 1979, Pages 180-189 (doi:10.1016/0095-8956(79)90079-0)
Persi Diaconis, Mehrdad Shahshahani, Generating a random permutation with random transpositions, Z. Wahrscheinlichkeitstheorie verw. Gebiete 57, 159–179 (1981) (doi:10.1007/BF00535487)
Dan Rockmore, Peter Kostelec, Wim Hordijk, Peter F. Stadler, Fast Fourier Transform for Fitness Landscapes, Applied and Computational Harmonic Analysis Volume 12, Issue 1, January 2002, Pages 57-76 (doi:10.1006/acha.2001.0346)
Petteri Kaski, Eigenvectors and spectra of Cayley graphs, Lecture at T-79.300 Postgraduate Course in Theoretical Computer Science, Helsinki University of Technology, Spring 2002 (pdf, pdf)
Briana Foster-Greenwood, Cathy Kriloff, Spectra of Cayley graphs of complex reflection groups, J. Algebraic Combin., 44(1):33–57, 2016 (arXiv:1502.07392, doi:10.1007/s10801-015-0652-8)
Xiaogang Liu, Sanming Zhou, Eigenvalues of Cayley graphs (arXiv:1809.09829)
Farzaneh Nowroozi, Modjtaba Ghorbani, On the spectrum of Cayley graphs via character table, Journal of Mathematical NanoScience, Volume 4, 1-2 (2014) (doi:10.22061/jmns.2014.477 pdf)
Last revised on April 30, 2021 at 08:52:29. See the history of this page for a list of all contributions to it.