Skip to main content
added 173 characters in body
Source Link

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. A proof (using character sums) that the Abelian Cayley graphs have large 2nd eigenvalue is given by Friedman, Murty and Tillich: http://www.mast.queensu.ca/~murty/f-m-t.pdf

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.

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. A proof (using character sums) that the Abelian Cayley graphs have large 2nd eigenvalue is given by Friedman, Murty and Tillich: http://www.mast.queensu.ca/~murty/f-m-t.pdf

Source Link

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.