Randomized Algorithms (Spring 2010)/Expander graphs and rapid mixing random walks: Difference between revisions
Jump to navigation
Jump to search
imported>WikiSysop |
imported>WikiSysop |
||
Line 4: | Line 4: | ||
=== Expander graphs === | === Expander graphs === | ||
We say that an undirected graph <math>G(V,E)</math> is an '''<math>(n,d)</math>-graph''' if <math>G</math> is a '''<math>d</math>-regular''' (every vertex has <math>d</math> neighbors) undirected graph defined on <math>n</math> vertices. | |||
Some notations: | |||
* For <math>S,T\subset V</math>, let <math>E(S,T)=\{uv\in E\mid u\in S,v\in T\}</math>. | |||
* The '''Edge Boundary''' of a set <math>S\subset V</math>, denoted <math>\partial S\,</math>, is <math>\partial S = E(S, \bar{S})</math>. | |||
{|border="1" | |||
|'''Definition (Graph expansion)''' | |||
:The '''expansion ratio''' of <math>G</math>, is defined as | |||
::<math> | |||
h(G)=\min_{S:|S|\le\frac{n}{2}}\frac{\partial S}{|S|}. | |||
</math> | |||
|} | |||
=== Existence === | === Existence === |
Revision as of 09:44, 5 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)
|