### Abstract

Expander Graphs are low-degree graphs that are highly connected. They have diverse
applications, for example in derandomization and pseudo-randomness, error-correcting codes, as well
as pure mathematical subjects such as metric embeddings. This entry formalizes the concept and
derives main theorems about them such as Cheeger's inequality or tail bounds on distribution of
random walks on them. It includes a strongly explicit construction for every size and spectral gap.
The latter is based on the Margulis-Gabber-Galil graphs and several graph operations
that preserve spectral properties. The proofs are based on the survey papers/monographs
by Hoory et al. and Vadhan, as well as results from Impagliazzo and Kabanets and Murtagh et al.

### License

### Topics

### Session Expander_Graphs

- Constructive_Chernoff_Bound
- Extra_Congruence_Method
- Expander_Graphs_Multiset_Extras
- Expander_Graphs_Definition
- Expander_Graphs_TTS
- Expander_Graphs_Algebra
- Expander_Graphs_Eigenvalues
- Expander_Graphs_Cheeger_Inequality
- Expander_Graphs_MGG
- Expander_Graphs_Walks
- Expander_Graphs_Power_Construction
- Expander_Graphs_Strongly_Explicit