Randomized Algorithms (Spring 2010)/Expander graphs and rapid mixing random walks

Graph Expansion

Expander graphs

We say that an undirected graph [math]\displaystyle{ G(V,E) }[/math] is an [math]\displaystyle{ (n,d) }[/math]-graph if [math]\displaystyle{ G }[/math] is a [math]\displaystyle{ d }[/math]-regular (every vertex has [math]\displaystyle{ d }[/math] neighbors) undirected graph defined on [math]\displaystyle{ n }[/math] vertices.

Some notations:

• For [math]\displaystyle{ S,T\subset V }[/math], let [math]\displaystyle{ E(S,T)=\{uv\in E\mid u\in S,v\in T\} }[/math].
• The Edge Boundary of a set [math]\displaystyle{ S\subset V }[/math], denoted [math]\displaystyle{ \partial S\, }[/math], is [math]\displaystyle{ \partial S = E(S, \bar{S}) }[/math].

Definition (Graph expansion) The expansion ratio of [math]\displaystyle{ G }[/math], is defined as [math]\displaystyle{ \phi(G)=\min_{S:|S|\le\frac{n}{2}}\frac{\partial S}{|S|}. }[/math]

Expander graphs are [math]\displaystyle{ d }[/math]-regular graphs with constant degree [math]\displaystyle{ d }[/math] and constant expansion ratio.