chap7.3

7.3 CHROMATIC NUMBER
岩間研究室
M2 門下雅一
7 Martingales and Tight
Concentration
1.
2.
3.
4.
5.
6.
7.
8.
Definitions
Large Deviations
Chromatic Number
Two General Settings
Four Illustrations
Talagrand’s Inequality
Applications of Talagrand’s Inequality
Kim-Vu Polynomial Concentration
• Chap10.3ではランダムグラフG( n, 1/2)に対して”ほ
とんど確実に”
n
 G ～
2 log n
であることを証明する。
• 節の前半はChap10.3の設定を用いて、Bela
Bollobasのマルチンゲールを使った証明を紹介する。
証明の目標
• クリーク数がk以下になる確率を評価する
PrG   k   e
 n 2 o 1
• より厳密に定理7.3.2の主張は以下である
Pr G   k   e
c  o 1
n2
ln8 n
準備
• Chap4.5を確認
k
 n   2 
f k    2
k 
f k はG n,1 2 上の kクリークの個数の期待値.Chap 4.5
k0  k0 n  : f k0  1  1  f k0 
k～2 log n, f k   n 3 o 1となるように
k  k0  4を決める。 Chap10.3
kの決め方
n 2
k 1 o 1
 k 1 


 n   2

2
k

1
f k  1 


k
f k 

n
   2 
 2
k 

n k
2 1  o1  n 1 o 1
k
f k   f k0  1n 3 o 1  n 3 o 1
互いに素な極大kクリーク族
– Hからk-クリークを枝が互いに素になるようにいくつか選ぶ。
– Y=Y(H):そのように選んだ極大な、クリーク族のサイズ
• マルチンゲールがうまく動く
• 補題7.3.1
n2
EY   4 1  o1
2k
• kクリークの族をKと書く
• fの定義より、 |K|の期待値はf(k)となる。
• A,Bは異なるk-クリーク
– 少なくとも1本の枝を共有する
• W:二元集合{A,B}の個数
• E[W]を計算する。
枝を共有する4クリークのペア
•
•
•
•
Chap4.5参照
S,T:k個の頂点からなる集合
AS:事象「Sがクリークである」
AS ,ATは T  S  i 2  i  k 1 のとき
– 互いに独立でない
– 枝を共有する
• あるS,Tで,ともにクリークで、 AS ,ATが互いに独立で
ないときそのようなペアが1つ存在
•
1

E[W ]   Pr  As  AT  
2 S～T
2

 Pr A
S
S～T
 AT    Pr  AS   Pr  AT | AS 
   Pr  AS 
S
S～ T
S
X Sを事象 ASの特性関数とする .
X
X
S k
s
とすると Xは kクリークの個数を表す
E[ X ]  f k 
   E[ X ]
。すなわち
以下の式は chap 4.5にある
 k  n  k  1 
 
    
i  2  i  k  i  2 

k 1
k 1

  g i ただし
E[ X ] i  2
 k  n  k 
 
  i 
i  k  i   2 

g i  
2
n
 
k 
k  i 
   
 2  2
• 初期設定より、∑g(i)はg(2)のオーダーで拘束される
ので(chap10.3)
k4
g 2～ 2
n
   E[ X ]
 
 : kクリークの個数の平均 
  2  g i 
～u 2 k 4 n  2
• 以上で「then E[W]=Δ/2」の説明終わり!
•
•
•
•
CをKのランダムな部分族
Pr[A∈C]=q
qは後で決める
W’:ペア{A’,B’}の個数
– A’,B’∈C
– 枝共有
E[W ]  E[W ]q 2  q 2 2
K
E[W ]  E[W ]q
C
枝がかぶる
kクリークを削除
 
E[Y ]  E[C  ]  E[C ]  E[W ]  q  q 2 2   2 2 ～ n 2 2k 4
Conjecture
• 筆者は補題の結果を改善できると予想
E[Y ]  c n k
2
2
• 定理7.3.2
Pr G   k   e
c  o 1
n2
ln8 n
• 証明
n
– Y0 ,, Ym , m    枝公開マルチンゲール
 2
– 関数Y
• 枝リプシッツ条件を満たす
• 枝を追加した後のグラフで増える互いに素なkクリークは高々1個
– Y=0のときkクリークはひとつもない
Pr G   k   PrY  0  PrY  E Y    E Y 
e
e
 n
 E Y 2  2   
  2
 c  o 1n 2 ln8 n
 e c o 1n
2
k8
k～2 log n 
Azumaの不等式 
証明終わり
精度が良い染色数の推定
• 定理7.3.3
• α>5/6,fixed
• p=n-α
• G=(n,p)
– 以上のとき,n,pを入力とする関数uが存在して
• u   G   u  3
特徴量=「3彩色可能性」
• 補題7.3.4
• α>5/6,fixed
• p=n-α
• G=(n,p)
– Gの任意の c n個の頂点は、"ほぼ確実に"3彩色可能
• 証明(背理法)
–
–
–
–
T:(G[T]上で)3彩色できない極小のG上の頂点集合
T-{x}は3彩色可能(for every x in T)
G[T]上のxの次数は3以上
|T|=tとするとGは3t/2本以上の枝を持つ
 t 

c n n 
   2   32t
Tが存在する確率    
p  o1


t  4  t  3t


 2 
証明終わり
• 定理7.3.3の証明
– ε>0 任意の正実数
– u=u(n,p,ε) 条件を満たす最小の整数
• Pr G  u  
– S：G-Sがu彩色可能である極小な頂点集合
– Y(G) Sの要素数
– Yは頂点リプシッツ条件を満たす
• 異なる頂点xがSにある場合は自明にG-Sはu彩色可
• XがG-Sにある場合で、u彩色できなくなった場合
– サイズが|S|と等しい他の集合が存在する
– XをSに加えればG-Sはu彩色可
• 頂点公開マルチンゲールを適用

PrY    

n  1  e
Pr Y     n  1  e
 2 2
 2 2
• λを
と満たすようにとる
 2 2
e

• Yが平均から離れた値をとる確率をε未満にする
• Gの染色数がu以下になる確率が正になるようにuを
決めた。
– Gはu彩色できる。
– このときY=0,Pr[Y=0]>ε
–    n 1
– Pr Y  2 n  1  Pr Y     n  1  

 

•


よりGは確率(1-ε)で高々
除いてu彩色可能である
Pr Y  2 n  1  
• 補題より確率(1-ε)以上で残りの
は別の色で3彩色可能である
• さらに確率(1-ε)で
c n個を
c n個の頂点
 G  u
• あわせて
Pru   G   u  3  1     1  3
3
証明終わり

Download Report