Improved Expansion of Random Cayley GraphsReportar como inadecuado

Improved Expansion of Random Cayley Graphs - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

1 Churchill College Cambridge 2 Computing and Mathematical Sciences Pasadena

Abstract : In Random Cayley Graphs and Expanders, N. Alon and Y. Roichman proved that for every ε > 0 there is a finite cε such that for any sufficiently large group G, the expected value of the second largest in absolute value eigenvalue of the normalized adjacency matrix of the Cayley graph with respect to cε log |G| random elements is less than ε . We reduce the number of elements to cε log DG for the same c, where DG is the sum of the dimensions of the irreducible representations of G. In sufficiently non-abelian families of groups as measured by these dimensions, log DG is asymptotically 1-2log|G|. As is well known, a small eigenvalue implies large graph expansion and conversely; see Tanner84 and AlonMilman84-2,AlonMilman84-1. For any specified eigenvalue or expansion, therefore, random Cayley graphs of sufficiently non-abelian groups require only half as many edges as was previously known.

Keywords : expander graphs Cayley graphs second eigenvalue logarithmic generators

Autor: Po-Shen Loh - Leonard J. Schulman -



Documentos relacionados