ConceptTheory & Algos
Expander graph
A graph is an expander if its second largest eigenvalue is bounded away from one by some constant.
Know first
Named as a prerequisite by the lectures that define this. The number is how many say so. A grey one has no page yet.
Adjacency matrix2Eigenvalue1Graph degree1Graph eigenvalues1Graph theory1Graph theory basics1Spectral gap1Vertex connectivity1
Opens up
Concepts that name this one as a prerequisite.
Lecturers
2Each in their own terms, from the easiest level.
Ryan O'Donnell
Joel Friedman
A sparse graph with good connectivity properties, often characterized by a spectral gap where the second eigenvalue is bounded away from zero.
Lectures that assume it
5Connections
17The lectures that define it or assume it, and the concepts next to it.
Concepts7
- Adjacency matrix
- Eigenvalue
- Bipartite expander
- Degree-Reduce
- Derandomization
- Expander derandomization with random walks