### Abstract

For every 1 > δ > 0 there exists a c = c(δ) > 0 such that for every group G of order n, and for a set S of c(δ) 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 ‐ δ). This implies that almost every such a graph is an ϵ(δ)‐expander. For Abelian groups this is essentially tight, and explicit constructions can be given in some cases. © 1994 John Wiley & Sons, Inc.

Original language | English (US) |
---|---|

Pages (from-to) | 271-284 |

Number of pages | 14 |

Journal | Random Structures & Algorithms |

Volume | 5 |

Issue number | 2 |

DOIs | |

State | Published - Apr 1994 |

Externally published | Yes |

### All Science Journal Classification (ASJC) codes

- Software
- Mathematics(all)
- Computer Graphics and Computer-Aided Design
- Applied Mathematics

## Fingerprint Dive into the research topics of 'Random Cayley graphs and expanders'. Together they form a unique fingerprint.

## Cite this

Alon, N., & Roichman, Y. (1994). Random Cayley graphs and expanders.

*Random Structures & Algorithms*,*5*(2), 271-284. https://doi.org/10.1002/rsa.3240050203