### Abstract

We describe a short and easy to analyze construction of constant-degree expanders. The construction relies on the replacement product, applied by [14] to give an iterative construction of bounded-degree expanders. Here we give a simpler construction, which applies the replacement product (only twice!) to turn the Cayley expanders of [4], whose degree is polylog n, into constant degree expanders. This enables us to prove the required expansion using a new simple combinatorial analysis of the replacement product (instead of the spectral analysis used in [14]).

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

Title of host publication | Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007 |

Publisher | Association for Computing Machinery |

Pages | 454-458 |

Number of pages | 5 |

ISBN (Electronic) | 9780898716245 |

State | Published - Jan 1 2007 |

Externally published | Yes |

Event | 18th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007 - New Orleans, United States Duration: Jan 7 2007 → Jan 9 2007 |

### Publication series

Name | Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms |
---|---|

Volume | 07-09-January-2007 |

### Other

Other | 18th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007 |
---|---|

Country | United States |

City | New Orleans |

Period | 1/7/07 → 1/9/07 |

### All Science Journal Classification (ASJC) codes

- Software
- Mathematics(all)

## Fingerprint Dive into the research topics of 'An elementary construction of constant-degree expanders'. Together they form a unique fingerprint.

## Cite this

Alon, N., Schwartz, O., & Shapira, A. (2007). An elementary construction of constant-degree expanders. In

*Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007*(pp. 454-458). (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; Vol. 07-09-January-2007). Association for Computing Machinery.