Name
Abstract | ||
|---|---|---|
Alon and Roichman (1994) proved that for every epsilon > 0 there is a finite c(epsilon) 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(epsilon) log | G| random elements is less than epsilon. We reduce the number of elements to c(epsilon) logD(G) ( for the same c), where D(G) 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 D(G) is asymptotically (1/2) log |G|. As is well known, a small eigenvalue implies large graph expansion (and conversely); see Tanner ( 1984) and Alon and Milman ( 1984, 1985). 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. |
Year | Venue | Keywords |
|---|---|---|
2004 | DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE | expander graphs, Cayley graphs, second eigenvalue, logarithmic generators |
Field | DocType | Volume |
Adjacency matrix,Discrete mathematics,Random regular graph,Combinatorics,Vertex-transitive graph,Expander graph,Cayley table,Cayley graph,Cayley transform,Cayley's theorem,Mathematics | Journal | 6 |
Issue | ISSN | Citations |
2 | 1462-7264 | 10 |
PageRank | References | Authors |
1.04 | 5 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Po-Shen Loh | 1 | 133 | 18.68 |
| Leonard J. Schulman | 2 | 1328 | 136.88 |