Lecture 12. Properties of Expanders M2 Mitsuru Kusumoto Kyoto University 2013/10/29
Preliminalies G = (V, E) L G : A G : 0 = λ 1 λ 2 λ n : L G ψ 1,..., ψ n : L G µ 1 µ 2 µ n : A G ϕ 1,..., ϕ n : A G (Lecture note µ i α i... )
Preliminalies Expander Expander ε > 0 d- G µ i εd( i 2) G ε-expander
Overview : Expander Expander Expander Expander Vertex Expansion
Expander µ i εd( i 2)? ( ) H G x L H x x L G x( x) x L H x x L G x( x 1)
Expander G H ε- ε- (1 ε)h G (1 + ε)h. G d ε-expander Lemma H = d n K n G H ε-
Expander G d L G = di A G λ i = d µ i ε-expander : µ i εd( i 2) (1 ε)d λ i (1 + ε)d (i 2) Caurant-Fischer x 1 (1 ε)dx x x L G x (1 + ε)dx x
Expander G d L G = di A G λ i = d µ i ε-expander : µ i εd( i 2) (1 ε)d λ i (1 + ε)d (i 2) Caurant-Fischer x 1 (1 ε)dx x x L G x (1 + ε)dx x
Expander K n L Kn = ni 1 1 x 1 x L Kn x = nx x H = d n K n x L H x = dx x (1 ε)dx x x L G x (1 + ε)dx x G H ε-
Expander K n L Kn = ni 1 1 x 1 x L Kn x = nx x H = d n K n x L H x = dx x (1 ε)dx x x L G x (1 + ε)dx x G H ε-
Expander K n L Kn = ni 1 1 x 1 x L Kn x = nx x H = d n K n x L H x = dx x (1 ε)dx x x L G x (1 + ε)dx x G H ε-
Expander (1 ε)h G (1 + ε)h. εx T L H x x (L G L H )x εx T L H x εl H 0 d L G L H εd.
Expander (1 ε)h G (1 + ε)h. εx T L H x x (L G L H )x εx T L H x εl H 0 d L G L H εd.
Quasi-Randomness G H = d n K n ε- E(S, T ) := {(u, v) u S, v T, (u, v) E} Theorem G d ε-expander S V, T V S, T disjoint S = αn, T = βn E(S, T ) αβdn εdn (α α 2 )(β β 2 ). α, β > ε αβdn (S, T disjoint?)
Quasi-Randomness G H = d n K n ε- E(S, T ) := {(u, v) u S, v T, (u, v) E} Theorem G d ε-expander S V, T V S, T disjoint S = αn, T = βn E(S, T ) αβdn εdn (α α 2 )(β β 2 ). α, β > ε αβdn (S, T disjoint?)
Quasi-Randomness G H = d n K n ε- E(S, T ) := {(u, v) u S, v T, (u, v) E} Theorem G d ε-expander S V, T V S, T disjoint S = αn, T = βn E(S, T ) αβdn εdn (α α 2 )(β β 2 ). α, β > ε αβdn (S, T disjoint?)
Quasi-Randomness G H = d n K n ε- E(S, T ) := {(u, v) u S, v T, (u, v) E} Theorem G d ε-expander S V, T V S, T disjoint S = αn, T = βn E(S, T ) αβdn εdn (α α 2 )(β β 2 ). α, β > ε αβdn (S, T disjoint?)
Quasi-Randomness χ S L G χ T = d S T E(S, T ) G H L H χ S L H χ T = χ S (di d n 11T )χ T = d S T αβdn. E(S, T ) αβdn = χ S L G χ T χ S L H χ T.
Quasi-Randomness χ S L G χ T = d S T E(S, T ) G H L H χ S L H χ T = χ S (di d n 11T )χ T = d S T αβdn. E(S, T ) αβdn = χ S L G χ T χ S L H χ T.
Quasi-Randomness χ S L G χ T = d S T E(S, T ) G H L H χ S L H χ T = χ S (di d n 11T )χ T = d S T αβdn. E(S, T ) αβdn = χ S L G χ T χ S L H χ T.
Quasi-Randomness bound... χ S (L G L H )χ T χ S L G L H χ T αn (εd) βn = εdn αβ.
Quasi-Randomness bound... χ S (L G L H )χ T χ S L G L H χ T αn (εd) βn = εdn αβ.
Quasi-Randomness 1 χ S (L G L H )χ T = (χ S α1) (L G L H )(χ T β1). χ S α1 χ T β1 = n (α α 2 )(β β 2 ). E(S, T ) αβdn εdn (α α 2 )(β β 2 ). S, T disjoint d
Quasi-Randomness 1 χ S (L G L H )χ T = (χ S α1) (L G L H )(χ T β1). χ S α1 χ T β1 = n (α α 2 )(β β 2 ). E(S, T ) αβdn εdn (α α 2 )(β β 2 ). S, T disjoint d
Quasi-Randomness 1 χ S (L G L H )χ T = (χ S α1) (L G L H )(χ T β1). χ S α1 χ T β1 = n (α α 2 )(β β 2 ). E(S, T ) αβdn εdn (α α 2 )(β β 2 ). S, T disjoint d
Quasi-Randomness 1 χ S (L G L H )χ T = (χ S α1) (L G L H )(χ T β1). χ S α1 χ T β1 = n (α α 2 )(β β 2 ). E(S, T ) αβdn εdn (α α 2 )(β β 2 ). S, T disjoint d
Quasi-Randomness S V N(S) S S (closed neighbors) Expander S N(S) Theorem (Tanner 84) S = αn N(S) S ε 2 (1 α) + α.
Quasi-Randomness S V N(S) S S (closed neighbors) Expander S N(S) Theorem (Tanner 84) S = αn N(S) S ε 2 (1 α) + α.
Quasi-Randomness R := N(S), T = V \ R S T 1 T = βn S, T αβdn εdn (α α 2 )(β β 2 ). R = γn γ = 1 β (pdf ) N(S) S (open neighbors)
Quasi-Randomness R := N(S), T = V \ R S T 1 T = βn S, T αβdn εdn (α α 2 )(β β 2 ). R = γn γ = 1 β (pdf ) N(S) S (open neighbors)
Quasi-Randomness R := N(S), T = V \ R S T 1 T = βn S, T αβdn εdn (α α 2 )(β β 2 ). R = γn γ = 1 β (pdf ) N(S) S (open neighbors)
Quasi-Randomness R := N(S), T = V \ R S T 1 T = βn S, T αβdn εdn (α α 2 )(β β 2 ). R = γn γ = 1 β (pdf ) N(S) S (open neighbors)
Good expanders ε Expander ε? : S = v (singleton) d + 1 1 ε 2 (1 1/n) + 1/n ε = Ω(1/ d) ε 2 d 1 d
Good expanders ε Expander ε? : S = v (singleton) d + 1 1 ε 2 (1 1/n) + 1/n ε = Ω(1/ d) ε 2 d 1 d
Good expanders ε Expander ε? : S = v (singleton) d + 1 1 ε 2 (1 1/n) + 1/n ε = Ω(1/ d) ε 2 d 1 d
Good expanders ε Expander ε? : S = v (singleton) d + 1 1 ε 2 (1 1/n) + 1/n ε = Ω(1/ d) ε 2 d 1 d
Good expanders ( Lecture note ε upper-bound... ) (Expander ) Theorem (Nilli 91) G (u 0, u 1 ) (v 0, v 1 ) 2k + 2 { λ 2 d 2 d 1 + 2 d 1 1 k+1 λ n d + 2 d 1 2 d 1 1 k+1 λ 2, λ n bound?
Good expanders ( Lecture note ε upper-bound... ) (Expander ) Theorem (Nilli 91) G (u 0, u 1 ) (v 0, v 1 ) 2k + 2 { λ 2 d 2 d 1 + 2 d 1 1 k+1 λ n d + 2 d 1 2 d 1 1 k+1 λ 2, λ n bound?
Good expanders ( Lecture note ε upper-bound... ) (Expander ) Theorem (Nilli 91) G (u 0, u 1 ) (v 0, v 1 ) 2k + 2 { λ 2 d 2 d 1 + 2 d 1 1 k+1 λ n d + 2 d 1 2 d 1 1 k+1 λ 2, λ n bound?
Good expanders : (λ 2 ) U i (u 0, u 1 ) i (i k) V i (v 0, v 1 ) i (i k) 1/(d 1) i/2 if a U i x(a) = β/(d 1) i/2 if a V i 0 otherwise β x 1 pdf+...
Good expanders : (λ 2 ) U i (u 0, u 1 ) i (i k) V i (v 0, v 1 ) i (i k) 1/(d 1) i/2 if a U i x(a) = β/(d 1) i/2 if a V i 0 otherwise β x 1 pdf+...
Good expanders : (λ 2 ) U i (u 0, u 1 ) i (i k) V i (v 0, v 1 ) i (i k) 1/(d 1) i/2 if a U i x(a) = β/(d 1) i/2 if a V i 0 otherwise β x 1 pdf+...