Recap: Edge and Vertex Expansion

In the edge expansion lecture, we saw a proof that for a d-regular graph G,

(d - λ₁)/2 ≤ h_G ≤ sqrt(2d(d - λ₁))
(See Manoj's post below for definitions.) As a consequence, we see that our two definitions of an expander family are equivalent.

In the vertex expansion lecture, we saw that vertex expansion is also related to the spectral gap. Analogously to edge expansion, define the vertex expansion h'_G as

h'_G = min_|S|≤n/2 |N(S)|/|S|
where the minimization is over all subsets S of at most half the vertices of G, and where N(S) = { v : there exists u in S with uv an edge }.

Let λ^* be max {| λ_i|}. For any d-regular graph G,

2/((λ^*/d)² + 1) ≤ h'_G ≤ sqrt(2d(d - λ₁)) + 1
Note that λ^* appears in the lower bound and λ₁ appears in the upper bound. The upper bound follows from the relatively simple observation that h'_G ≤ h_G + 1.

Solving the second inequality for λ₁, we obtain an upper bound

λ₁ ≤ d - (h'_G - 1)²/2d
Finally, we note that, when d is large, better bounds on λ₁ are known. A result of Noga Alon (1986) shows that

λ₁ ≤ d - (h'_G - 1)²/(4 + 2(h'_G - 1)²)