Random cayley graphs and expanders
| Author(s) : | Yuval Roichman Noga Alon, |
| Publisher : | N/A |
| Publication Date : | 1994 |
| ISSN : | N/A |
| Abstract : | For every 1? ffi? 0 there exists a c = c(ffi) ? 0 such that for every group G of order n, and for a set S of c(ffi) log n random elements in the group, the expected value of the second largest eigenvalue of the normalized adjacency matrix of the Cayley graph X(G;S) is at most (1\Gammaffi). This implies that almost every such a graph is an "(ffi)-expander. For Abelian groups this is essentially tight, and explicit constructions can be given in some cases., |