Lecture 12. Properties of Expanders

Similar documents

日本内科学会雑誌第102巻第4号

第90回日本感染症学会学術講演会抄録（I）

第86回日本感染症学会総会学術集会後抄録（I）

日本内科学会雑誌第98巻第4号

日本内科学会雑誌第97巻第7号

研修コーナー

パーキンソン病治療ガイドライン2002

本文／目次（裏白）

N cos s s cos ψ e e e e 3 3 e e 3 e 3 e

1 (Berry,1975) 2-6 p (S πr 2 )p πr 2 p 2πRγ p p = 2γ R (2.5).1-1 : : : : ( ).2 α, β α, β () X S = X X α X β (.1) 1 2

O1-1 O1-2 O1-3 O1-4 O1-5 O1-6

微分積分サンプルページこの本の定価判型などは, 以下の URL からご覧いただけます. このサンプルページの内容は, 初版 1 刷発行時のものです.

expander graph [IZ89] Nii (NII) Lec. 11 October 22, / 16

放射線専門医認定試験（２００９・２０回）／ＨＯＨＳ‐０５（基礎二次）

プログラム

H 0 H = H 0 + V (t), V (t) = gµ B S α qb e e iωt i t Ψ(t) = [H 0 + V (t)]ψ(t) Φ(t) Ψ(t) = e ih0t Φ(t) H 0 e ih0t Φ(t) + ie ih0t t Φ(t) = [

医系の統計入門第 2 版サンプルページこの本の定価判型などは, 以下の URL からご覧いただけます. このサンプルページの内容は, 第 2 版 1 刷発行時のものです.

PowerPoint プレゼンテーション

ｎｓｇ０２－１３／ｋｙ０４５０５９３０１６０００３３２１０

,. Black-Scholes u t t, x c u 0 t, x x u t t, x c u t, x x u t t, x + σ x u t, x + rx ut, x rux, t 0 x x,,.,. Step 3, 7,,, Step 6., Step 4,. Step 5,,.

Basic Math. 1 0 [ N Z Q Q c R C] 1, 2, 3,... natural numbers, N Def.(Definition) N (1) 1 N, (2) n N = n +1 N, (3) N (1), (2), n N n N (element). n/ N.

_TZ_4797-haus-local

I A A441 : April 15, 2013 Version : 1.1 I Kawahira, Tomoki TA (Shigehiro, Yoshida )

ｎｓｇ０４－２８／ｋｙ２０８６８４３５６１０００４３０７７

..3. Ω, Ω F, P Ω, F, P ). ) F a) A, A,..., A i,... F A i F. b) A F A c F c) Ω F. ) A F A P A),. a) 0 P A) b) P Ω) c) [ ] A, A,..., A i,... F i j A i A

液晶の物理１：連続体理論（弾性，粘性）

1. R n Ω ε G ε 0 Ω ε B n 2 Ωε = with Bu = 0 on Ω ε i=1 x 2 i ε +0 B Bu = u (Dirichlet, D Ω ε ), Bu = u ν (Neumann, N Ω ε ), Ω ε G ( ) / 25

.2 ρ dv dt = ρk grad p + 3 η grad (divv) + η 2 v.3 divh = 0, rote + c H t = 0 dive = ρ, H = 0, E = ρ, roth c E t = c ρv E + H c t = 0 H c E t = c ρv T

ｔｎｂｐ５９－２１＿Ｗｅｂ：Ｐ２／ｋｙ１３２３７９５０９６１０００２９４４

1 α X (path) α I = [0, 1] X α(0) = α(1) = p α p (base point) loop α(1) = β(0) X α, β α β : I X (α β)(s) = ( )α β { α(2s) (0 s 1 2 ) β(2s 1) ( 1 2 s 1)

( ) ) ) ) 5) 1 J = σe 2 6) ) 9) 1955 Statistical-Mechanical Theory of Irreversible Processes )

III III 2010 PART I 1 Definition 1.1 (, σ-),,,, Borel( ),, (σ-) (M, F, µ), (R, B(R)), (C, B(C)) Borel Definition 1.2 (µ-a.e.), (in µ), (in L 1 (µ)). T

y = x x R = 0. 9, R = σ $ = y x w = x y x x w = x y α ε = + β + x x x y α ε = + β + γ x + x x x x' = / x y' = y/ x y' =

A = A x x + A y y + A, B = B x x + B y y + B, C = C x x + C y y + C..6 x y A B C = A x x + A y y + A B x B y B C x C y C { B = A x x + A y y + A y B B

( )/2 hara/lectures/lectures-j.html 2, {H} {T } S = {H, T } {(H, H), (H, T )} {(H, T ), (T, T )} {(H, H), (T, T )} {1

I A A441 : April 21, 2014 Version : Kawahira, Tomoki TA (Kondo, Hirotaka ) Google

_0212_68<5A66><4EBA><79D1>_<6821><4E86><FF08><30C8><30F3><30DC><306A><3057><FF09>.pdf

1. 1 A : l l : (1) l m (m 3) (2) m (3) n (n 3) (4) A α, β γ α β + γ = 2 m l lm n nα nα = lm. α = lm n. m lm 2β 2β = lm β = lm 2. γ l 2. 3

２００７年０８月号　０２２４１６／０８１２　会告

日本内科学会雑誌第96巻第7号

Part () () Γ Part ,

磁性物理学 - 遷移金属化合物磁性のスピンゆらぎ理論

03実習2・松井.pptx

Note.tex 2008/09/19( )

SO(3) 7 = = 1 ( r ) + 1 r r r r ( l ) (5.17) l = 1 ( sin θ ) + sin θ θ θ ϕ (5.18) χ(r)ψ(θ, ϕ) l ψ = αψ (5.19) l 1 = i(sin ϕ θ l = i( cos ϕ θ l 3 = i ϕ

80 4 r ˆρ i (r, t) δ(r x i (t)) (4.1) x i (t) ρ i ˆρ i t = 0 i r 0 t(> 0) j r 0 + r < δ(r 0 x i (0))δ(r 0 + r x j (t)) > (4.2) r r 0 G i j (r, t) dr 0

D = [a, b] [c, d] D ij P ij (ξ ij, η ij ) f S(f,, {P ij }) S(f,, {P ij }) = = k m i=1 j=1 m n f(ξ ij, η ij )(x i x i 1 )(y j y j 1 ) = i=1 j

ｓｎｋｐ－１４－２／ｋｙ３４７０８４２２０２０００１９１７５

18 I ( ) (1) I-1,I-2,I-3 (2) (3) I-1 ( ) (100 ) θ ϕ θ ϕ m m l l θ ϕ θ ϕ 2 g (1) (2) 0 (3) θ ϕ (4) (3) θ(t) = A 1 cos(ω 1 t + α 1 ) + A 2 cos(ω 2 t + α

1 a b = max{a, b}, a b = mi{a, b} a 1 a 2 a a 1 a = max{a 1,... a }, a 1 a = mi{a 1,... a }. A sup A, if A A A A A sup A sup A = + A if A = ± y = arct

現代物理化学 1-1(4)16.ppt

LLG-R8.Nisus.pdf

r 1 m A r/m i) t ii) m i) t B(t; m) ( B(t; m) = A 1 + r ) mt m ii) B(t; m) ( B(t; m) = A 1 + r ) mt m { ( = A 1 + r ) m } rt r m n = m r m n B

ax 2 + bx + c = n 8 (n ) a n x n + a n 1 x n a 1 x + a 0 = 0 ( a n, a n 1,, a 1, a 0 a n 0) n n ( ) ( ) ax 3 + bx 2 + cx + d = 0 4

x 3 a (mod p) ( ). a, b, m Z a b m a b (mod m) a b m 2.2 (Z/mZ). a = {x x a (mod m)} a Z m 0, 1... m 1 Z/mZ = {0, 1... m 1} a + b = a +

−g”U›ß™ö‡Æ…X…y…N…g…‰

x () g(x) = f(t) dt f(x), F (x) 3x () g(x) g (x) f(x), F (x) (3) h(x) = x 3x tf(t) dt.9 = {(x, y) ; x, y, x + y } f(x, y) = xy( x y). h (x) f(x), F (x

V(x) m e V 0 cos x π x π V(x) = x < π, x > π V 0 (i) x = 0 (V(x) V 0 (1 x 2 /2)) n n d 2 f dξ 2ξ d f 2 dξ + 2n f = 0 H n (ξ) (ii) H

Transcription:

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+...