Ramanujan Graphs & Spectral Gap
Optimal expanders: λ₂ ≤ 2√(d-1). Eigenvalue distribution, random walk mixing, adjacency spectrum.
Graph type:
Ramanujan (LPS)
Random d-regular
Complete K_n
Cycle C_n
Petersen (k=3)
n vertices:
20
40
80
Degree d:
3
4
5
6
Generate
Relayout
Vertices n:
-
Degree d:
-
λ₁ (max):
-
λ₂:
-
Ramanujan bound 2√(d-1):
-
Is Ramanujan?:
-
Mixing time est:
-