Editing Cayley graph (section)

== Expansion properties ==

When <math>S = S^{-1}</math>, the Cayley graph <math>\Gamma(G,S)</math> is <math>|S|</math>-regular, so spectral techniques may be used to analyze the [[expander graph|expansion properties]] of the graph. In particular for abelian groups, the eigenvalues of the Cayley graph are more easily computable and given by <math display="inline">\lambda_\chi = \sum_{s\in S} \chi(s)</math> with top eigenvalue equal to <math>|S|</math>, so we may use [[Spectral graph theory#Cheeger inequality|Cheeger's inequality]] to bound the edge expansion ratio using the spectral gap.

Representation theory can be used to construct such expanding Cayley graphs, in the form of [[Kazhdan property (T)]]. The following statement holds:<ref>Proposition 1.12 in {{cite journal|last=Lubotzky|first=Alexander | authorlink=Alexander Lubotzky |title=Expander graphs in pure and applied mathematics | journal=[[Bulletin of the American Mathematical Society]] |year=2012 |volume=49 |pages=113–162  |arxiv=1105.2389| doi=10.1090/S0273-0979-2011-01359-3 |doi-access=free}}</ref> 

{{block indent | em = 1.6 | text = ''If a discrete group <math>G</math> has Kazhdan's property (T), and <math>S</math> is a finite, symmetric generating set of <math>G</math>, then there exists a constant <math>c > 0</math> depending only on <math>G, S</math> such that for any finite quotient <math>Q</math> of <math>G</math> the Cayley graph of <math>Q</math> with respect to the image of <math>S</math> is a <math>c</math>-expander. ''}}

For example the group <math>G = \mathrm{SL}_3(\Z)</math> has property (T) and is generated by [[elementary matrices]] and this gives relatively explicit examples of expander graphs.