Return to Revisions

To add to Anthony's comment, one can make an explicit connection between the large number of walks between vertices and the spectra of Abelian Cayley graphs. It turns out that constant-degree Abelian Cayley graph are not only bad expanders,but they tend to be disconnected (they have a positive proportion of their eigenvalues close to their valency). See: http://www.math.udel.edu/%7Ecioaba/inpress_version.pdf for a short proof. Alon and Roichman showed earlier that Abelian Cayley graphs have large diameter (power of the order of the graph); the diameter of an expander should be logarithmic in the order of the graph.