定理2.3.1

定理2.3.1
節点数nの完全グラフ K nがあり、
その枝を全て二色（赤、青）で色分けする。
そのとき節点数aの単一色の完全グラフ K aが
a
1

n
   2 
 2
個以下である塗りわけ方が存在する。
a
証明：定理2.3.1
• 全枝を確率1/2で赤、青に塗り分ける。
• ある節点数aの節点集合 があり、
X  を、 が単一色完全グラフであるとき１，
そうでなければ０を表す確率変数とする。
1 a 
2
期待値 E  X  は
2
となる。
証明：定理2.3.1
•
X を節点数aの単一色な完全グラフ K a の
数とする。 X の期待値は以下で表される。
n
E  X    E  X     2
a
1 a 
2
• 期待値が以上の値なので
X  EX 

とするような塗り分け方が存在する□
定理2.3.2
• 節点数m,nの完全二部グラフ K m , n があり、
その枝を全て二色（赤、青）で色分けする。
• そのとき、節点数a,bの単一色な完全二部グ
 m  n  1 ab
ラフ K a ,b が   2 個以下であるような塗
 a  a 
り分け方が存在する。
※頂点数mの集合は頂点数aの集合に対応し、
頂点数nの集合は頂点数bの集合に対応する
証明：定理2.3.2
• 全枝を確率1/2で赤、青に塗り分ける。
• ある節点数a,bの節点集合  があり、
X  を、 が単一色完全二部グラフであると
き１，そうでなければ０を表す確立変数とする。
期待値 E  X  は 21 ab となる。
証明：定理2.3.2
•
X を節点数aの単一色な完全二部グラフ K a ,b
の数とする。X の期待値は以下で表される。
 m  n  1 ab
E  X    E  X      2
 a  b 
• 期待値が以上の値なので
X  EX 

とするのような塗り分け方が存在する□
定理2.4.1
• 任意の v1 , v2 ,  , vn  R , all vi  1 に対して、
以下を満たす  ,  ,  ,   1 が存在する。
n
1
2
n
1v1   2v2       n vn  n
同様に以下を満たす 1 ,  2 ,  ,  n  1も存在する。
1v1   2v2       n vn  n
証明：定理2.4.1
• 1 ,  2 ,  ,  n に確率1/2で{-1,+1}を当てはめる。
X   1 v1  ...   n vn
• 展開すると X 
n
とおく。
n
   v v
i 1 j 1
• X の期待値 E  X  
2
i
j i
j
 v v E  
n
n
i 1 j 1
i
j
i
j
証明：定理2.4.1
• i≠jのとき
 
 
E  i j  E i E  j  0
∵ は確率1/2で{-1,+1}をとる
i
 
• i=jのとき E  i  E1  1
2
• よって E  X  
n
v v
i 1
i
i
n
証明：定理2.4.1
EX   n より X  nやX  nとするような
割り当て 1 ,  2 ,  ,  n が存在する。
2
• X   1 v1  ...   n vn より、
•
平方根をとることで定理2.4.1を得られる□
定理2.4.2
• 任意の v1 , v2 ,  , vn  R n , all vi  1
p1 , p2 ... pn  [0,1] に対して、
以下を満たす 1 ,  2 ,  ,  n  0,1 が存在する。
n
wv 
2
※ただし w  p1v1  ...  pn vn
v  1v1  ...   n vn
証明：定理2.4.2
•  i それぞれに確率 pi で１、1  pi で０を割り当てる。
2
• X  w  v とおく
X
n
  p   v
i
i 1
i
2
i
 j

期待値は EX    vi v j E  pi   i  p j   j

展開すると X 
 v v  p    p
n
n
i 1 j 1
n
n
i 1 j 1
i
j
i

i

j
証明：定理2.4.2
• i≠jのとき E  pi   i  p j   j   E pi   i E  p j   j 
 
  pi  E i  p j  E  j   0
 
∵ E  i  pi
2
2
2
• i=jのとき E  pi   i   pi  2 pi E  i   E  i


 pi  2 pi pi  pi
1
 pi 1  pi  
4
2
 
証明：定理2.4.2


E  X    vi v j E  pi   i  p j   j 
n
n
i 1 j 1
n
  pi 1  pi  vi
i 1
2
1 n
  vi
4 i 1
2
n

4
n
• 以上より X  E  X  
とするような
4 
割り当て 1 ,  2 ,  ,  n が存在し、 X の平方根

をとることで定理2.4.2を得られる□

Download Report