chap5.1-5.2

Probabilistic method 輪講
第7回
2007年7月4日(水)
岩間研究室
M2 門下雅一
5章 The Local Lemma
– 1節 The Lemma
– 2節 Property B and Multicolored Set of Real
Numbers
– 3節 Lower Bonds for Ramsey Numbers
– 4節 A Geometric Result
– 5節 The Linear Arboricity of Graphs
復習
• 確率を用いた証明論法の典型
– 事象Xの生起確率が正であることを示す。
• 実は確率が大きいということも(証明の中で)得られる
– e. g. 性質Skを持つトーナメント(第1章)
• 完全グラフの枝に向きを付与する。
• 性質Sk : 任意にk個の頂点を選んだとき、それらすべての頂点に
枝が出ている頂点が存在する。
• kに対してnが十分大きくなるとほとんどすべての枝のむき付けに
対して、性質を満たす。
S1を満たす例
独立性・希薄依存性
(independence and rare dependence)
• 逆に、事象の生起確率が正ではあるが非常に小さいことを示す場合もあ
る。
• 特にn個の互いに独立な事象の確率が少なくともp(>0)であるとき
– n個のすべてが同時に起きる事象の確率はpn以上
– 確率は正ではあるが、nに関して指数関数的に小さくなる
• 互いに独立ではないが、ほとんど依存しない事象でも上のような性質と
似た性質があるのではないか?
• これから用いたい論法
– 証明したい性質を持つ事象が、n個の互いに独立ではない事象が同時に起
きると表現される。
– 確率は小さいけれど、正である。よって証明したい性質の存在が証明できる。
Lovasz Local Lemma
• Lemma 5.1.1
– A1, A2 , …,Anを任意の確率空間上の事象とする.n個
の頂点V={1,2,…,n}を持つ有向グラフD=(V,E)で、任意
の i, 1  i  n にたいして事象Aiが事象 A j | i, j  E と互
いに独立であるとき、そのような有向グラフを依存有向
グラフと呼ぶ。いま、上で示した事象上の依存有向グラ
フD=(V,E)と、n個の実数 x1 , x2 ,, xn 0  xi  1 が存在し、
任意の 1  i  n について
Pr  Ai   xi i , j E 1  x j 
を満たすならば n
n
Pr i 1 Ai    1  xi 
i 1
特に、事象Aiがすべて起きない確率が正である。
依存有向グラフD=(V,E)
• 事象の対が互いに独立であるか否かという
情報を保持する
• 対称に有向枝を持つ
互いに独立
Lovasz Local Lemma(再掲)
• Lemma 5.1.1
– A1, A2 , …,Anを任意の確率空間上の事象とする.n個
の頂点V={1,2,…,n}を持つ有向グラフD=(V,E)で、任意
の i, 1  i  n にたいして事象Aiが事象 A j | i, j  E と互
いに独立であるとき、そのような有向グラフを依存有向
グラフと呼ぶ。いま、上で示した事象上の依存有向グラ
フD=(V,E)と、n個の実数 x1 , x2 ,, xn 0  xi  1 が存在し、
任意の 1  i  n について
Pr  Ai   xi i , j E 1  x j 
を満たすならば n
n
Pr i 1 Ai    1  xi 
i 1
特に、事象Aiがすべて起きない確率が正である。
条件付確率の基本
• 基本的事項の復習
– 事象AとBが互いに独立
Pr A  B  Pr A PrB
Pr A | B  Pr A
– 条件付確率
Pr A | B  Pr A  B PrB
Pr A  B | C   PrB | A  C  Pr A | C 
– 余事象の確率

Pr A | B   1  Pr  A | B 
Pr A  1  Pr  A
実数xの役割
• [補題5.1.1の証明]
– はじめに任意の部分集合S⊂{1,2,…,n}, |S|=s<n,
と任意の i  S について(5.1)式


Pr Ai |  A j   xi
jS


を示す。
– 数学的帰納法
• s=0のとき



Pr Ai |  A j   Pr Ai |    Pr  Ai |    Pr  Ai 

jS

Pr  Ai   xi i , j E 1  x j   xi
補題5.1.1の証明[1]


Pr Ai |  A j   xi
jS


• s’<sなるすべてのs’で
が成立すると仮定
する。 S1   j  S : i, j  E, S2  S \ S1 と置く。




 Pr Ai   jS A j
Pr  Ai |  A j  
Pr  jS A j
jS



Pr Ai 

D=(V,E)
  A  Pr  A 
Pr 
A  
A  Pr 
A
Pr A  
A | 
A

Pr 
A |
A



jS1
jS1
i
 
Pr Ai 

jS1
j
jS1
jS1

Aj 
l
lS 2
j
j
 
l
lS 2
lS 2
lS 2
lS 2
2

l
l
2

 Pr  Ai   xi i , j E 1  x j 
Pr  jS Aj | lS Al  i , j  1  x j を示す。
1
i
l
l
A j | lS Al  Pr Ai | lS Al
2
lS 2
ｊ
S1
ｌ
S2
補題5.1.1の証明[2]
S1   j1 , j2 , , jr とする。 r  0のとき分母は 1となる。
otherwise
分母   Pr Aj

 A j2    A jr | lS A j

 1  Pr A j1 | lS
lS 2
2
 
  1  Pr A

 
A  1  Pr A

2
jr
2
j
 i , j E
j2
| A j1 

| A j1  A j2    A jr 1 | lS A j
 
1  x 
 1  x j1 1  x j2  1  x jr
•

 Pr A j1 | lS A j  Pr A j2    A jr | A j1 
1

2
lS 2
Aj


A j 

帰納法の仮定を
使う
j
よって、任意の真部分集合S⊂{1,2,…,n}, |S|=s<n,と任意の i  Sについて(5.1)式


Pr Ai |  A j   xi
jS


補題5.1.1の証明[3]
• 証明のラストも簡単

n
   
n
Pr i 1 Ai  Pr A1  Pr i  2 Ai | A1





Pr Ai |  A j   xiを用いると
jS



 1  Pr  A1   1  Pr A2 | A1 
 
n 1
  1  Pr An | i 1 Ai
 i 1 1  xi 
n
[証明終]

The local lemma ; symmetric case
• 系5.1.2
– A1, A2 , …,Anを任意の確率空間上の事象とする.どの事象Aiも、そ
れと互いに独立でない事象Ajの個数がd個以下であるとする。事象
Aiの起きる確率がp以下であるとする。条件式

epd  1  1
n

を満たすならば Pr i 1 Ai  0
• 系5.1.2の証明
– d=0のときはAi とAiはすべて互いに独立であるので、自明。
– その他の場合、事象上の依存有向グラフで、任意のiについて
 j; i, j  E  d を満たすものが存在する
補題5.1.1で xi  1 d  1 と置くと
d
1 
 1 
Pr  Ai   p  1 d  1 e  
1 
  xi i. j E 1  x j 
1

d
1

d


n 


n
 1 
Pr i 1 Ai  
 0
1

d


性質Bを持つハイパーグラフ
• ハイパーグラフH=(V,E)が性質Bを持つ
– 頂点の２彩色で任意の枝fについてfに含まれる頂点が単一の色で塗られて
いない
V  1,2,3,4,5, E  1,2,3, 4,5, 2,4, 1,2,5
• 定理5.2.1
– ハイパーグラフH=(V,E)はどんな枝もk個以下の頂点を含むとする。Hのどん
な枝も多くともd本の枝と交差(intersect)しているとする。このとき
ならばHは性質Bを持つ。
ed  1  2k 1
• 証明
– 頂点vを無作為に独立に赤・青に塗る。任意の枝fについて、Afを枝fが1色で
塗られているという事象とする。事象Afが起きる確率を計算すると、
Pr A f   2 2  1 2 k 1  p 
f
– f と異なる枝でｆと交差していない枝f’ に関する同様の事象Af’ は事象Af と互
いに独立である。
– よって系5.1.2をそのまま用いることにより、どの枝も単一で塗られていない
確率は正である。[証明終]
定理5.2.1の特殊な場合
• 注意
– k  9 なるk-uniform k-regularハイパーグラフHは
いつも性質Bを持つ。
• どの枝もちょうどk個の頂点部分集合になっている
• どの頂点もちょうどk本の枝に属している
– 枝 f は高々d=k(k-1)本の枝と交差する。
k 1




任意の
k

9
に対して
e
k
k

1

1

2
–
実数のk-彩色
• 定義
– 実数に色{1,2,…,k}のうちひとつを割り当てる
– 実数の部分集合T⊂RでTに割り当てられた色の集合をc(T)と書く。
c(T)={1,2,…k}であるとき、Tは全彩色されたという
• 定理5.2.2
m
 1
emm  1  1k 1    1
– m ,k を正の整数とする。条件式
 k
を満たすとき、m個の実数からなる任意の集合Sにたいして、任意の
置換x+S (x∈R)が全彩色になるような実数のk-彩色が存在する
– 特にm  3 o1k log k のとき、いつも条件式を満たす。
定理5.2.2の証明[1]
• [定理5.2.2の証明]
– はじめに実数の有限集合X⊂Rを固定する。任意の置換
x+S (x∈X)が全彩色になるような実数k-彩色が存在する
ことを示す。
– Y  xX x  Sと置く。
– c : Y  1,2,, kを Yのランダム k  彩色とする。
• y∈Yをランダムに選び、c(y)を{1,2,…,k}の一様分布に従って塗る。
– Axをx+Sは全彩色でないという事象とする。
–
m




Pr
A

k
1

1
k
x
–
x• 高々m(m-1)通り
S   x  S   のとき以外
Axと Axは独立。
– 補題5.1.2のd,pにそれぞれ代入。
定理5.2.2の証明[2]
• 証明したい命題は実数xを制限しないバージョン
– 位相数学のはなし
– コンパクトという概念を使う
• 位相空間Xの部分集合Kにたいして、任意のKの開被覆が、
有限部分被覆を持つとき、Kがコンパクトであるという。
– k個の点上の離散空間はコンパクトであるから、ティコノフ
の定理によりそういう空間の任意の直積もコンパクトであ
る。
– 特に、関数R→{1,2,…,k}全体がなす空間も、通常の直積
位相を用いることによりコンパクトである。
– このような空間では、任意の固定したx∈Rに対して、彩色
の集合Cxで、x+Sが全彩色である集合は閉集合となる。
• 実は開集合でもあり閉集合でもある。なぜならば開集合へ
のある基は、有限個の場所の個数で定められた彩色をす
べて集めた彩色の集合だから。
定理5.2.2の証明[3]
–
集合Cxの有限個の族の共通集合は空集合でない。
•
•
–
コンパクト性より、すべての集合Cxの共通集合C(0)は空集合でない。
1.
2.
–
•
定理5.2.2の証明[1]のスライド
このような性質を有限交叉性と呼ぶ
すべての彩色を集めた集合Cがコンパクト
Cの部分集合の族が有限交叉性を持つ
この共通集合C(0)に含まれる任意の彩色は、定理5.2.2の結論で
述べられている性質を満たす。[証明終]
無限個の事象を補題に適用しても、一般にはうまくいかな
い
加算的に多くの独立した事象Aiで、Pr  Ai   1 2かつi 1 Ai  
を満たす例が存在する。
–
そういうわけで、コンパクトを用いた論法が上の証明では必要にな
る。
–

Download Report