Lecture 12. Properties of Expanders
Lecture 12. Properties of Expanders
M2 Mitsuru Kusumoto
Kyoto University
Lecture 12. Properties of Expanders Preliminalies 無向グラフ G = (V, E) に対して LG : ラプラシアン AG : 隣接行列 0 = λ1 ≤ λ2 ≤ · · · ≤ λn : LG の固有値 ψ1, . . . , ψn : LG の固有ベクトル µ1 ≥ µ2 ≥ · · · ≥ µn : AG の固有値 ϕ1, . . . , ϕn : AG の固有ベクトル という表記をします． (Lecture note では µi は αi と記されているっぽいが. . . )
Lecture 12. Properties of Expanders Preliminalies 以下のものを Expander と呼ぶ． Expander の定義 ε > 0 に対して，d-正則グラフ G が |µi| ≤ εd(∀i ≥ 2) を満たすとき，G を ε-Expander と呼ぶ．
Lecture 12. Properties of Expanders Overview 今日の内容 : Expander について Expander がいかにランダムっぽい振る舞いをするかについ て見ていく． Expander は完全グラフへの近似である． Expander は高い Vertex Expansion を持つ． あとなんかマニアックそうな話
Lecture 12. Properties of Expanders Expander |µi| ≤ εd(∀i ≥ 2) ↑この変な条件はなんなのか? 以下の記号を使って解析する． 半正定値性による比較 (復習) H ⪯ G ⇐⇒ x⊤LHx≤ x⊤LGx(∀x) ⇐⇒ x⊤L Hx≤ x⊤LGx(∀x ⊥ 1)
Lecture 12. Properties of Expanders Expander 以下の時 G は H の ε-近似 であると呼ぶ． ε-近似 (1− ε)H ⪯ G ⪯ (1 + ε)H. G は d 正則で，ε-Expander であるとする．次のことを示す． Lemma H = dnKn とすると，G は H の ε-近似である．
Lecture 12. Properties of Expanders Expander とりあえず G は d 正則なので LG = dI− AG であることか ら，λi = d− µi である． ε-Expander の条件: |µi| ≤ εd(∀i ≥ 2) から，(1− ε)d ≤ λi ≤ (1 + ε)d である．(i ≥ 2) なので，Caurant-Fischer から，x⊥ 1 に対して， (1− ε)dx⊤x≤ x⊤LGx≤ (1 + ε)dx⊤x
Lecture 12. Properties of Expanders Expander とりあえず G は d 正則なので LG = dI− AG であることか ら，λi = d− µi である． ε-Expander の条件: |µi| ≤ εd(∀i ≥ 2) から，(1− ε)d ≤ λi ≤ (1 + ε)d である．(i ≥ 2) なので，Caurant-Fischer から，x⊥ 1 に対して， (1− ε)dx⊤x≤ x⊤LGx≤ (1 + ε)dx⊤x
Lecture 12. Properties of Expanders Expander ところで，完全グラフ Kn に対しては，LKn = nI− 1 ⊤1 な ので，x⊥ 1 ならば，x⊤L Knx = nx⊤x である．H = d nKn とすると x⊤LHx = dx⊤x である． 前の結果： (1− ε)dx⊤x≤ x⊤LGx≤ (1 + ε)dx⊤x と照らし合わせると，G は H の ε-近似になっている事が わかる．
Lecture 12. Properties of Expanders Expander ところで，完全グラフ Kn に対しては，LKn = nI− 1 ⊤1 な ので，x⊥ 1 ならば，x⊤L Knx = nx⊤x である．H = d nKn とすると x⊤LHx = dx⊤x である． 前の結果： (1− ε)dx⊤x≤ x⊤LGx≤ (1 + ε)dx⊤x と照らし合わせると，G は H の ε-近似になっている事が わかる．
Lecture 12. Properties of Expanders Expander ところで，完全グラフ Kn に対しては，LKn = nI− 1 ⊤1 な ので，x⊥ 1 ならば，x⊤L Knx = nx⊤x である．H = d nKn とすると x⊤LHx = dx⊤x である． 前の結果： (1− ε)dx⊤x≤ x⊤LGx≤ (1 + ε)dx⊤x と照らし合わせると，G は H の ε-近似になっている事が わかる．
Lecture 12. Properties of Expanders Expander (1− ε)H ⪯ G ⪯ (1 + ε)H. より， −εxTL Hx≤ x⊤(LG− LH)x≤ εxTLHx ここで，εLH の固有値は 0 か d であるので， ∥LG− LH∥ ≤ εd.
Lecture 12. Properties of Expanders Expander (1− ε)H ⪯ G ⪯ (1 + ε)H. より， −εxTL Hx≤ x⊤(LG− LH)x≤ εxTLHx ここで，εLH の固有値は 0 か d であるので， ∥LG− LH∥ ≤ εd.
Lecture 12. Properties of Expanders Quasi-Randomness
G が H = dnKn の ε-近似になっているということが言えた．
今度はもっと具体的なことを示す．
⃗
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 じゃなくても成立するっぽい?)
Lecture 12. Properties of Expanders Quasi-Randomness
G が H = dnKn の ε-近似になっているということが言えた．
今度はもっと具体的なことを示す．
⃗
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 じゃなくても成立するっぽい?)
Lecture 12. Properties of Expanders Quasi-Randomness
G が H = dnKn の ε-近似になっているということが言えた．
今度はもっと具体的なことを示す．
⃗
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 じゃなくても成立するっぽい?)
Lecture 12. Properties of Expanders Quasi-Randomness
G が H = dnKn の ε-近似になっているということが言えた．
今度はもっと具体的なことを示す．
⃗
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 じゃなくても成立するっぽい?)
Lecture 12. Properties of Expanders Quasi-Randomness χ⊤SLGχT = d|S ∩ T | − | ⃗E(S, T )| である．G は H に近いとかあったので LH について見て みる． χ⊤SLHχT = χ⊤S(dI− d n11 T)χ T = d|S ∩ T | − αβdn. よって， || ⃗E(S, T )| − αβdn| = |χ⊤ SLGχT − χ⊤SLHχT|.
Lecture 12. Properties of Expanders Quasi-Randomness χ⊤SLGχT = d|S ∩ T | − | ⃗E(S, T )| である．G は H に近いとかあったので LH について見て みる． χ⊤SLHχT = χ⊤S(dI− d n11 T)χ T = d|S ∩ T | − αβdn. よって， || ⃗E(S, T )| − αβdn| = |χ⊤ SLGχT − χ⊤SLHχT|.
Lecture 12. Properties of Expanders Quasi-Randomness χ⊤SLGχT = d|S ∩ T | − | ⃗E(S, T )| である．G は H に近いとかあったので LH について見て みる． χ⊤SLHχT = χ⊤S(dI− d n11 T)χ T = d|S ∩ T | − αβdn. よって， || ⃗E(S, T )| − αβdn| = |χ⊤ SLGχT − χ⊤SLHχT|.
Lecture 12. Properties of Expanders Quasi-Randomness あとは適当に不等式で bound してやると. . . |χ⊤ S(LG− LH)χT| ≤ ∥χS∥∥LG− LH∥∥χT∥ ≤ √αn· (εd) ·√βn = εdn√αβ. 定理のやや悪い版が得られる．
Lecture 12. Properties of Expanders Quasi-Randomness あとは適当に不等式で bound してやると. . . |χ⊤ S(LG− LH)χT| ≤ ∥χS∥∥LG− LH∥∥χT∥ ≤ √αn· (εd) ·√βn = εdn√αβ. 定理のやや悪い版が得られる．
Lecture 12. Properties of Expanders Quasi-Randomness もうちょっと頑張ると定理の結果が得られる． ラプラシアンは 1 に直行するので， χ⊤S(LG− LH)χT = (χS− α1)⊤(LG− LH)(χT − β1). 一方で， ∥χS− α1∥∥χT − β1∥ = n √ (α− α2)(β− β2). なので，同じようにすれば，所望の結果が得られる． || ⃗E(S, T )| − αβdn| ≤ εdn√(α− α2)(β− β2). ちなみに S, T が disjoint なときは，d 正則じゃなくて重み 付きでも成り立つらしい
Lecture 12. Properties of Expanders Quasi-Randomness もうちょっと頑張ると定理の結果が得られる． ラプラシアンは 1 に直行するので， χ⊤S(LG− LH)χT = (χS− α1)⊤(LG− LH)(χT − β1). 一方で， ∥χS− α1∥∥χT − β1∥ = n √ (α− α2)(β− β2). なので，同じようにすれば，所望の結果が得られる． || ⃗E(S, T )| − αβdn| ≤ εdn√(α− α2)(β− β2). ちなみに S, T が disjoint なときは，d 正則じゃなくて重み 付きでも成り立つらしい
Lecture 12. Properties of Expanders Quasi-Randomness もうちょっと頑張ると定理の結果が得られる． ラプラシアンは 1 に直行するので， χ⊤S(LG− LH)χT = (χS− α1)⊤(LG− LH)(χT − β1). 一方で， ∥χS− α1∥∥χT − β1∥ = n √ (α− α2)(β− β2). なので，同じようにすれば，所望の結果が得られる． || ⃗E(S, T )| − αβdn| ≤ εdn√(α− α2)(β− β2). ちなみに S, T が disjoint なときは，d 正則じゃなくて重み 付きでも成り立つらしい
Lecture 12. Properties of Expanders Quasi-Randomness もうちょっと頑張ると定理の結果が得られる． ラプラシアンは 1 に直行するので， χ⊤S(LG− LH)χT = (χS− α1)⊤(LG− LH)(χT − β1). 一方で， ∥χS− α1∥∥χT − β1∥ = n √ (α− α2)(β− β2). なので，同じようにすれば，所望の結果が得られる． || ⃗E(S, T )| − αβdn| ≤ εdn√(α− α2)(β− β2). ちなみに S, T が disjoint なときは，d 正則じゃなくて重み 付きでも成り立つらしい
Lecture 12. Properties of Expanders Quasi-Randomness 頂点集合 S ⊆ V に対して N(S) を，S に隣り合う頂点と S の和集合とする．(closed neighbors) Expander では|S| にくらべて |N(S)| がとても大きくなる． 以下を示す． Theorem (Tanner’84) |S| = αn とするとき， |N(S)| ≥ |S| ε2(1− α) + α.
Lecture 12. Properties of Expanders Quasi-Randomness 頂点集合 S ⊆ V に対して N(S) を，S に隣り合う頂点と S の和集合とする．(closed neighbors) Expander では|S| にくらべて |N(S)| がとても大きくなる． 以下を示す． Theorem (Tanner’84) |S| = αn とするとき， |N(S)| ≥ |S| ε2(1− α) + α.
Lecture 12. Properties of Expanders 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) を考えた 場合も同じような結果が得られるっぽい
Lecture 12. Properties of Expanders 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) を考えた 場合も同じような結果が得られるっぽい
Lecture 12. Properties of Expanders 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) を考えた 場合も同じような結果が得られるっぽい
Lecture 12. Properties of Expanders 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) を考えた 場合も同じような結果が得られるっぽい
Lecture 12. Properties of Expanders Good expanders ε が小さいほどよい Expander である．ε はどのくらい小さ くできるのか? 単純な解析 : さっきの定理で S = v (singleton) とすると， d + 1≥ 1 ε2(1− 1/n) + 1/n これより，ε = Ω(1/√d) であることがわかる． ラマヌジャングラフとかいうのを使うと ε≤ 2√d−1 d を達成 できるらしい．
Lecture 12. Properties of Expanders Good expanders ε が小さいほどよい Expander である．ε はどのくらい小さ くできるのか? 単純な解析 : さっきの定理で S = v (singleton) とすると， d + 1≥ 1 ε2(1− 1/n) + 1/n これより，ε = Ω(1/√d) であることがわかる． ラマヌジャングラフとかいうのを使うと ε≤ 2√d−1 d を達成 できるらしい．
Lecture 12. Properties of Expanders Good expanders ε が小さいほどよい Expander である．ε はどのくらい小さ くできるのか? 単純な解析 : さっきの定理で S = v (singleton) とすると， d + 1≥ 1 ε2(1− 1/n) + 1/n これより，ε = Ω(1/√d) であることがわかる． ラマヌジャングラフとかいうのを使うと ε≤ 2√d−1 d を達成 できるらしい．
Lecture 12. Properties of Expanders Good expanders ε が小さいほどよい Expander である．ε はどのくらい小さ くできるのか? 単純な解析 : さっきの定理で S = v (singleton) とすると， d + 1≥ 1 ε2(1− 1/n) + 1/n これより，ε = Ω(1/√d) であることがわかる． ラマヌジャングラフとかいうのを使うと ε≤ 2√d−1 d を達成 できるらしい．
Lecture 12. Properties of Expanders Good expanders (ここから Lecture note のストーリーがよくわからない，ε の upper-bound を証明するとかいいつつ下界の議論をして いる. . . ) (Expander のことはちょっと忘れて) 次のことを証明する． Theorem (Nilli’91) G の中に辺 (u0, u1) と (v0, v1) があって，距離が少なくとも 2k + 2 あるとする．すると， { λ2 ≤ d − 2 √ d− 1 + 2√dk+1−1−1 λn≥ d + 2 √ d− 1 − 2√k+1d−1−1 λ2, λn が決まっていた場合にそのグラフの直径を bound で きる?
Lecture 12. Properties of Expanders Good expanders (ここから Lecture note のストーリーがよくわからない，ε の upper-bound を証明するとかいいつつ下界の議論をして いる. . . ) (Expander のことはちょっと忘れて) 次のことを証明する． Theorem (Nilli’91) G の中に辺 (u0, u1) と (v0, v1) があって，距離が少なくとも 2k + 2 あるとする．すると， { λ2 ≤ d − 2 √ d− 1 + 2√dk+1−1−1 λn≥ d + 2 √ d− 1 − 2√k+1d−1−1 λ2, λn が決まっていた場合にそのグラフの直径を bound で きる?
Lecture 12. Properties of Expanders Good expanders (ここから Lecture note のストーリーがよくわからない，ε の upper-bound を証明するとかいいつつ下界の議論をして いる. . . ) (Expander のことはちょっと忘れて) 次のことを証明する． Theorem (Nilli’91) G の中に辺 (u0, u1) と (v0, v1) があって，距離が少なくとも 2k + 2 あるとする．すると， { λ2 ≤ d − 2 √ d− 1 + 2√dk+1−1−1 λn≥ d + 2 √ d− 1 − 2√k+1d−1−1 λ2, λn が決まっていた場合にそのグラフの直径を bound で きる?
Lecture 12. Properties of Expanders Good expanders 証明 : そういうテストベクトルを作る．(λ2 だけ示す．) Ui を (u0, u1) から距離がちょうど i である頂点集合と する．(i≤ k) Vi を (v0, v1) から距離がちょうど i である頂点集合と する．(i≤ k) x(a) = 1/(d− 1)i/2 if a∈ U i −β/(d − 1)i/2 if a∈ V i 0 otherwise β は x⊥ 1 となるようにとる．続きは pdf+板書で. . .
Lecture 12. Properties of Expanders Good expanders 証明 : そういうテストベクトルを作る．(λ2 だけ示す．) Ui を (u0, u1) から距離がちょうど i である頂点集合と する．(i≤ k) Vi を (v0, v1) から距離がちょうど i である頂点集合と する．(i≤ k) x(a) = 1/(d− 1)i/2 if a∈ U i −β/(d − 1)i/2 if a∈ V i 0 otherwise β は x⊥ 1 となるようにとる．続きは pdf+板書で. . .
Lecture 12. Properties of Expanders Good expanders 証明 : そういうテストベクトルを作る．(λ2 だけ示す．) Ui を (u0, u1) から距離がちょうど i である頂点集合と する．(i≤ k) Vi を (v0, v1) から距離がちょうど i である頂点集合と する．(i≤ k) x(a) = 1/(d− 1)i/2 if a∈ U i −β/(d − 1)i/2 if a∈ V i 0 otherwise β は x⊥ 1 となるようにとる．続きは pdf+板書で. . .
![[書評] 佐藤元彦著『脱貧困のための国際開発論』](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACH5BAEAAAAALAAAAAABAAEAAAICRAEAOw==)