Randomized Algorithms (Spring 2010)/Expander graphs and rapid mixing random walks: Difference between revisions
imported>WikiSysop |
imported>WikiSysop |
||
Line 22: | Line 22: | ||
=== Existence === | === Existence === | ||
Suppose that <math>d</math> is even. We can generate a random <math>d</math>-regular graph <math>G(V,E)</math> as follows: | |||
* Let <math>V</math> be the vertex set. Uniformly and independently choose <math>\frac{d}{2}</math> cycles of <math>V</math>. | |||
* For each vertex <math>v</math>, for every cycle, assuming that the two neighbors of <math>v</math> in that cycle is <math>w</math> and <math>u</math>, add two edges <math>wv</math> and <math>uv</math> to <math>E</math>. | |||
The resulting <math>G(V,E)</math> is a multigraph. That is, it may have multiple edges between two vertices. We will show that <math>G(V,E)</math> is an expander graph with high probability. Formally, for some constant <math>d</math> and constant <math>\alpha</math>, | |||
:<math>\Pr[\phi(G)\ge \alpha]=1-o(1)</math>. | |||
=== Construction === | === Construction === |
Revision as of 07:32, 6 May 2010
Mixing Time
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)
|
Expander graphs are [math]\displaystyle{ d }[/math]-regular graphs with constant degree [math]\displaystyle{ d }[/math] and constant expansion ratio.
Existence
Suppose that [math]\displaystyle{ d }[/math] is even. We can generate a random [math]\displaystyle{ d }[/math]-regular graph [math]\displaystyle{ G(V,E) }[/math] as follows:
- Let [math]\displaystyle{ V }[/math] be the vertex set. Uniformly and independently choose [math]\displaystyle{ \frac{d}{2} }[/math] cycles of [math]\displaystyle{ V }[/math].
- For each vertex [math]\displaystyle{ v }[/math], for every cycle, assuming that the two neighbors of [math]\displaystyle{ v }[/math] in that cycle is [math]\displaystyle{ w }[/math] and [math]\displaystyle{ u }[/math], add two edges [math]\displaystyle{ wv }[/math] and [math]\displaystyle{ uv }[/math] to [math]\displaystyle{ E }[/math].
The resulting [math]\displaystyle{ G(V,E) }[/math] is a multigraph. That is, it may have multiple edges between two vertices. We will show that [math]\displaystyle{ G(V,E) }[/math] is an expander graph with high probability. Formally, for some constant [math]\displaystyle{ d }[/math] and constant [math]\displaystyle{ \alpha }[/math],
- [math]\displaystyle{ \Pr[\phi(G)\ge \alpha]=1-o(1) }[/math].