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
+
+
+
+