Expander graph
Δ-regular bipartite expander
.
. .
. .
. .
. .
. .
⋮ ⋮
⋮ ⋮
⋮ ⋮
. .
. .
. .
. .
. .
.
a small subset of vertices |S|
.
. .
. .
. .
. .
. .
(⋮ ⋮
(⋮ ⋮
(⋮ ⋮
. .
. .
. .
. .
. .
.
connects to a large neighborhood
.
. .
. .
. .
. .)
. ⟋ .)
(⋮ ⟋ ⋮)
(⋮ ⋮)
(⋮ ⟍ ⋮)
. ⟍ .)
. .)
. .
. .
. .
.
Expander mixing lemma |E(S,T)| ≤ Δ|S||T|/|V₀| + λ(G)√(|S||T|)
.
. .
. .
. .
. .)
. ⟋ .)
(⋮ ⟋ ⋮)
(⋮ ⋮)
(⋮ ⟍ ⋮)
. ⟍ .)
. .)
. .
. .
. .
.
λ(G) := max{ |λᵢ|, λᵢ ≠ ± Δ }
Ramanujan expander: λ(G) ≤ 2√(Δ - 1)
.
. .
. .)
. / .)
. / .)
. / .)
(⋮ / ⋮)
(⋮ ⋮)
(⋮ \ ⋮)
. \ .)
. \ .)
. \ .)
. .)
. .
.
|E(S,T)| is smallest. i.e. edges are as spread out as can be
can be constructed from the Cayley graph of a group.
expander graphs to make good codes
“Let S,T ⊂ V. Let E(S,T) denote the multiset of edges with one endpoint in S and endpoint in T. Let 𝒢 be a Δ-regular graph on n vertices. Let Δ = λ₁ ≥ λ₂ ≥ ... ≥ λₙ be the eigenvalues of 𝒢’s adjacency matrix.
For n ≥ 3, define λ(𝒢) := max { |λᵢ|, λᵢ ≠ ± Δ }.
The connected graph 𝒢 is called Ramanujan if λ(𝒢) ≤ 2√{Δ-1}.
/-- Lemma 3-/
lemma expander_mixing. For a Δ-regular, non-bipartite, connected graph G and S,T ⊆ G, it holds that
|E(S,T)| ≤ Δ/|V| * |S||T| + λ(G) * √{|S||T|}.
For a Δ-regular, bipartite connected graph G with V = V₀ ∪ V₁ and ny S ⊂ V₀, T ⊂ V₁, it holds that
|E(S,T)| ≤ Δ/|V₀| * |S||T| + λ(G) * √{|S||T|}."
“Let G(V,E) be a bipartite graph. Let |V| = n. Let each vertex have degree d.
(N,M,d,γ,α) expander: every S ⊂ V with |S| ≤ γn has at least dα|S| neighbors.
Ideally we want α close to 1. and γ >> 0. The expansion property holds trivially for γ ≤ 1/n. If 1/n < γ ≤ 1 and α = 1 - ε for constant ε, we say that G is a lossless expander.”
a small subset of vertices has many neighbors.
“Random walks on them mix quickly”
“Eigenvalues of its adjacency matrix”
“G is a good spectral expander if all non-trivial eigenvalues are small.”
“The closer the eigenvalues are to zero the better an expander it is.”
“Consider for example the complete bipartite graph. It’s a good expander. It has eigenvalues d and -d. But if you look at the adjacency matrix you see it’s a rank 2 matrix. So all the other eigenvalues are 0.”
“Finding a good expander like this is easy. The harder problem is finding families that are good expander for a fixed degree and having the number of vertices grow.”
“For a complete bipartite graph the number of vertices is twice the degree.”
“Alon-Boppana bound: Any d-regular graph has second-largest eigenvalue ≥ 2√{d-1}.”
A graph is Ramanujan if all eigenvalues have absolute value ≤ 2√{d-1}.
“Ramanujan graphs are spectrally speaking the best possible expanders.”
They saturate the bound.
“Theorem: Infinite sequences of Ramanujan graphs exist for d = prime + 1”
“Friedman: A random d-regular graph is almost Ramanujan: 2√{d - 1} + ε for any ε > 0.”
“Ramanujan graphs can be constructed quickly”
A good expander bipartite d-regular graph:
Take a vertex subset S in U such that |S| ≤ 0.01 |U|.
Good expander if |N(S)| ≥ ε|S|.