Document

Additive Combinatorics 輪講
5章 Proof of Szemerédi’s
Regularity Lemma
木下直紀
e-正則


定義5.1.1. e >0,グラフ G=(V,E), U,W⊆V とす
る。任意の S⊆U, T⊆W, |S|≧e|U|, |T|≧e|W| に
ついて |d(S,T)–d(U,W)|≦e を満たすとき、ペア
(U,W) は e-正則であるという。
定義. A,B⊆V について、枝密度 d(A,B) を次で
定義する。
E  A, B 
d  A, B  
,
AB
E  A, B   u, v   E | u  A, v  B
Regularity Lemma



定理5.1.2. e >0, t∈N,
constant k(e,t), ∀G=(V,E) with |V|≧t,
∃partition (V1,V2, …,Vk) with t≦k≦k(e,t),
|V1|=|V2|=…=|Vk-1| ≧|Vk| s.t. 少なくとも
(1-e)kC2 個のペア (Vi,Vj) は e-正則である。
任意のグラフは定数サイズ近似表現を持つ
各区画(Vi)内の枝の状況については述べられ
ていないが、最低区画数 t により区画をまた
ぐ枝の割合を調整できる。
ランダムな分割


命題. ランダムな分割では定理の命題である
e-正則な分割にならない。
例. 大きな二部グラフ (V=A∪B) のランダム分
割 (V1,V2, …,Vk) を考える。どの区画も A,B 両
方の頂点を多く含む。ペア (Vi,Vj) において、
A⊇S⊆Vi, B⊇T⊆Vj → d(S,T)≒d(A,B)>e,
A⊇S⊆Vi, A⊇T⊆Vj → d(S,T)=0
よってほとんどのペアは e-正則ではない。
アルゴリズム [1/2]

e-正則な分割を与えるアルゴリズムを示す。
1. P=(V1,V2, …,Vk) を V の任意の分割とし、
|V1|=|V2|=…=|Vk-1| ≧|Vk|, k=max(1/e,t) とする。
2. P が定理の条件（e-正則）を満たすなら終了。
満たしてなければ、少なくとも e kC2 個のペア
(Vi,Vj) について Sij⊆Vi, Sj⊆Vj が存在して
|Sij|≧e|Vi|, |Sji|≧e|Vj| かつ
|d(Sij,Sji)–d(Vi,Vj)|≧e を満たす。
（続く）
アルゴリズム [2/2]
3. 各 Vi を Sij⊆Vi のなす完全加法族に従って
高々 2k–1 区画にの任意の分割し P' とする。
|P'|≦k2k–1 を満たす。
4. P' の各区画をさらにサイズ n/(k2k–1)2 の区画
（+余り）に分割する。余りをまとめてサイズ
n/(k2k–1)2 の区画（+余り）に分割する。
以上で得た分割を
Si1
P と書き直し、k=|P|
を更新。2.に戻る。
Si2
Si3
ポテンシャル関数を導入


このアルゴリズムが定数ステップで停止する
ことを示す。
ある時点における「正則性」を表すポテンシャ
ル関数 F を定義。分割 P=(V1,V2, …,Vk),
A,B⊆V についての確率変数 X[A,B] を、
v1,v2←RV について v1⊆A, v2⊆B なら
X[A,B]=d(A,B)2, o.w. X[A,B]=0 として、
Vi V j
2
F P    EX Vi ,V j   
d Vi ,V j 
2
1i  j  P
1i  j  P V
ポテンシャル関数の性質



ポテンシャル関数は次の確率変数 Z の分散
であると解釈できる。v1,v2←RV として、v1⊆Vi,
v2⊆Vj なら Z=d(Vi,Vj) また、v1,v2 が同じ区画
に入っていれば Z=0
d(Vi,Vj)≦1 より、任意の分割 P について
F(P)≦1
次に、アルゴリズムにおける P から P' への改
良は常に F(P')≧F(P) となることを示す。
F(P')≧F(P) の証明

区画 Vi を S,Vi＼S の2個に分割する場合を
考えれば十分。
FP  FP   E X S ,Vi \ S 
  EX S ,V j   EX Vi \ S ,V j   EX Vi ,V j 
j i

確率変数 Yj を v←RVi について次で定義
v  S 
d S ,V j 
Yj  
d Vi \ S ,V j  v Vi \ S 
F(P')≧F(P) の証明

確率変数 W について E[W]2≦E[W2] より、
EX Vi ,V j  
Vi V j
2
EY j  
2
Vi V j
V
V
 E X S ,V j   E X Vi \ S ,V j 


2
 
E Yj
2
以上により、P から P' への改良はポテンシャ
ル関数を減少させないことがいえる。
次に、正則でないペア (Vi,Vj) を分割すると F
が大きく増加することを示す。
補足
E X Vi , V j  
Vi V j
V
2
d Vi , V j  , d Vi , V j  
2
S
Vi \ S
E Y j  
d  S , Vi  
d Vi \ S , Vi 
Vi
Vi
S E  S , Vi  Vi \ S E Vi \ S , Vi 


Vi S Vi
Vi
Vi \ S Vi
E  S , Vi   E Vi \ S , Vi  E Vi , V j 


Vi V j
Vi V j
Vi V j
2


 E X Vi , V j  
E
Y
j
2
V
Vi ,V j間のエッジ数
E Vi , V j 
Vi V j
(Vi,Vj)→(S,Vi＼S,T,Vj＼T)

e正則でない Vi,Vj をそれぞれ分割したとき、
FP  FP   E X S , T   EX S ,V j \ T 
 E X Vi \ S , T   EX Vi \ S ,V j \ T   E X Vi ,V j 

確率変数 Y を v1←RVi, v2←RVj について
Y=d(A,B) (A∈(S,Vi＼S), B∈(T,Vj＼T))
とすると、E[Y]=d(Vi,Vj) となり、e2 以上の確率
で Y の値は期待値より e 外れる。よって、
Var[Y]=E[(Y–E[Y])2]≧e2・e2
(Vi,Vj)→(S,Vi＼S,T,Vj＼T)
E X S , T   E X S ,V j \ T 
 E X Vi \ S , T   E Vi \ S , V j \ T 
Vi V j
Vi V j
2
2
4
EY   e 

E Y  
2
2
V
V
Vi V j 4
 E X Vi , V j  
e
2
V

従ってポテンシャル関数は少なくとも
e4|Vi||Vj|/|V|2 増加する。
P→P' ポテンシャル関数の評価
F  P   F  P 




    E X  A, B   E Vi , V j 
1i  j  P  A, BP

Vi ,V j :非正則  AVi , B V j





    E X  A, B   E Vi , V j 
1i  j  P  A S ij ,Vi \ S ij 

Vi ,V j :非正則  BS ji ,V j \ S ji 

Vi V j 4
5
 
e  e 
2
V
1i  j  P
Vi ,V j :非正則
P→P' ポテンシャル関数の評価



アルゴリズムは1回の繰り返しで (e5) ポテン
シャル関数を増加させるので O(1/e5) ステッ
プで停止。分割サイズ |P|=k は毎ステップ
k←(k2k–1)2 で増加するから、最終的に保証さ
れる k(e,t) は高さ O(1/e5) の tower になる。
e の tower は必要[Gow97]
Sij,Sji を効率的に見つける方法は Regularity
Lemma では述べられていないが、Lemma の
保証する分割を見つける多項式アルゴリズ
ムが存在する[ADL+94]。

Download Report