Document

5.3, 5.4
D2 岡本和也
5.3 Ramsey Number の下限の改良

The Local Lemma を利用する。
Ramsey Number の復習

R(k, l)
n節点の完全グラフKnの枝を２色（赤・青）で
塗り分けるとき、どんな塗り分け方をしたとしても、
赤枝のみを持つ完全部分グラフKｋか青枝のみを
持つ完全部分グラフKlが存在するような最小のn。
完全グラフ
どの2頂点間にも枝が存在するグラフ。
Ramsey Number の復習

R(k, l)
n節点の完全グラフKnの枝を2色（赤・青）で
塗り分けるとき、どんな塗り分け方をしたとしても、
赤枝のみを持つ完全部分グラフKｋか青枝のみを
持つ完全部分グラフKlが存在するような最小のn。
R(3, 3) = 6
Ramsey Number の下限の改良
k = l の場合 ( R (k, k) )





ランダムに辺に色を塗る。
S ・・・完全グラフ Kn の k 頂点からなる頂点集合
AS ・・・ S の頂点間の枝が単色になる事象
Pr(AS) =
2
2
k C2
1/2
1/2
1/2
AS は他のほとんどの事象 AS’ と互いに独立である。


S と S’ が2頂点以上共有していない場合・・・互いに独立である。
S と S’ が2頂点以上共有している場合・・・互いに独立でない。

互いに独立でない S’ は多く見積もっても
n頂点(Kn)
k頂点(S)
k
C 2 n C  k  2 
以下である。
The Local Lemma; Symmetric Case
の復習




事象 A1, A2, …, An がある。
任意の事象 Ai に関して Pr(Ai) ≦ p
任意の事象 Ai は最大 d 個以外の事象と互いに独立。
ep(d+1) ≦ 1
ならば



Pr ni1 Ai  0

全ての事象が起きない可能性がある。
Ramsey Number の下限の改良
k = l の場合 ( R (k, k) )



ランダムに辺に色を塗る。
S ・・・完全グラフ Kn の k 頂点からなる頂点集合
AS ・・・ S の頂点間の枝が単色になるイベント
2
p

Pr(AS) =

AS は他のほとんどのイベント AS’ と互いに独立である。


2 k C2
S と S’ が2頂点以上共有していない場合・・・互いに独立である。
S と S’ が2頂点以上共有している場合・・・互いに独立でない。

互いに独立でない S’ は多く見積もっても
n頂点(Kn)
k頂点(S)
k
C 2 n C  k  2 
以下である。
d
Ramsey Number の下限の改良
k = l の場合 ( R (k, k) )
Proposition 5.3.1
ep(d+1) ≦ 1
e
2
2
k C2

k
C 2 n C k  2   1  1
ならば
R(k, k) > n
>
2
1  o1k 2 k / 2
e
ヒント
 en 
C

 
n k
 k 
p. 26 の 3.1.1 より2倍良くなった。
k
The Local Lemma

互いに独立でない事象が多いと効果が薄い。



symmetric な場合、k が大きくなるにつれて d が大きくなる。
symmetric でない場合 (k = l) を考える。
さらに、l が小さい場合を考える。

例えば、R(k, 3)
Ramsey Number の下限の改良
k = l の場合 ( R (k, 3) )









辺を確率 p で青色に塗る。（後は赤色に塗る。）
T ・・・完全グラフ Kn の3頂点からなる頂点集合
AT ・・・ T の頂点間の枝が青色になる事象
S ・・・完全グラフ Kn の k 頂点からなる頂点集合
BS ・・・ S の頂点間の枝が赤色になる事象
Pr(AT) = p3
Pr(BS) = 1  p 
k
C2
AT は 3C2(n – 3) < 3n の AT’ と nCk 以下の BS と独立でない。
BS は kC2(n – k) < k2n/2 の AT と nCk 以下の BS’ と独立でない。
The Local Lemma; General Case
の復習



事象 A1, A2, …, An がある。
Ai, Aj が独立でない場合、(i, j) ∈ E とする。（必要十分条件）

0

xi  1 (1 ≦ i ≦ n)
任意の事象 Ai に関して、
Pr  Ai   xi (i , j )E (1  x j )
ならば


Pr 
n
i 1

n
Ai   1  xi 
i 1

全ての事象が起きない可能性がある。
Ramsey Number の下限の改良
k = l の場合 ( R (k, 3) )









辺を確率 p で青色に塗る。（後は赤色に塗る。）
T ・・・完全グラフ Kn の3頂点からなる頂点集合
AT ・・・ T の頂点間の枝が青色になる事象
S ・・・完全グラフ Kn の k 頂点からなる頂点集合
BS ・・・ S の頂点間の枝が赤色になる事象
Pr(AT) = p3
Pr(BS) = 1  p 
k
C2
AT は 3C2(n – 3) < 3n の AT’ と nCk 以下の BS と独立でない。
BS は kC2(n – k) < k2n/2 の AT と nCk 以下の BS’ と独立でない。
Ramsey Number の下限の改良
k = l の場合 ( R (k, 3) )
Pr  Ai   xi (i , j )E (1  x j )
AT :
BS : 1  p 
Ai = AT ならば xi = x
Ai = BS ならば xi = y
p  x1  x  1  y 
3n
3
k C2
 y1  x 
k 2n / 2
n Ck
1  y 
n Ck
ならば
R(k, 3) > n
>
k2
c
log 2 k
最も n が大きくなるように
p, x, y を定めると・・・
（c は定数）
Ramsey Number の下限の改良
k = l の場合 ( R (k, 3) )

R(k, 3) > c k2 / log2k



1961年に Erdös が複雑な確率的手法で
求めたものと一致している。
R(k, 3) > c’ k2 / log k [Kim ‘95]
R(k, 4) > k5/2+o(1)

The Local Lemma を用いないどんな証明よりも
良い結果である。
5.4 Geometric Result

ユークリッド空間 R3 が open unit ball で充満している。

任意の点( x ∈ R3 )が k 個以上の open unit ball に含まれているとき、
R3 の k-fold covering という。


1-fold covering は単に covering ということもある。
k-fold covering F を互いに素な F1 と F2 に分解し、
F1 と F2 がそれぞれ covering となっているとき、
分解可能(decomposable)という。
1
open unit ball
(本当は3次元)
Mani-Levitska and Pach (1988)

任意の k （ ≧ 1 ）に対して、
解不可能な k-fold covering を作成した。

どの点も c 2k/3 個以上の open unit ball でカバーされていない
ような k-fold covering は分解可能であると示した。


いささか驚くべき現象であると述べられている。
正確な記述は、Theorem 5.4.1（次ページ）。
（個人的見解）

分解不可能な k-fold covering を作成しようとすると、
多くの open unit ball に覆われるような点が出来てしまう。
分
Theorem 5.4.1



F = {Bi}i∈I を k-fold covering とする。
R3 のどの点も t 個以上の open unit ball に
含まれていない。
e･t 3 218 / 2 k-1 ≦ 1
ならば

F は分解可能である。
Theorem 5.2.1 を利用して導く。
Proof of Theorem 5.4.1

ハイパーグラフ H = (V(H), E(H))



V(H) は F = {Bi}i∈I
Ex は x （∈ R3）を含んでいる open unit ball の集合
E(H) は Ex の集合
但し、Ex = Ey の場合、どちらか一方しか含まない。

1
V(H) = {1, 2, 3}
E(H) = { {1}, {2}, {3}, {1, 2}, {2, 3}, {1, 2, 3}}
2
x
3
y
Ex = {2}, Ey = {2}
Proof of Theorem 5.4.1

主張

任意の枝 Ex は t 3 218 本未満の枝としか依存関係にない。

Ex に含まれる頂点と同じ頂点を含む枝は t 3 218 本未満である。
半径4の球の体積は
半径1の球の体積の 43 = 26 倍である。
Bj’’’’
Bj’’’
Bj’’
x
Bj’
1以下
3以下
Bi
4以下
どの点も t 個以上の open unit ball で
カバーされていないため、
半径4の球に最大 26t 個含まれる。
m 個の球が重なったとき、
最大 m3 個の部分に分かれる。
よって、主張が正しいことがわかる。
Bj
m 個の球が重なったとき、
最大 m3 個の部分に分かれる？
2次元
2m 本
m +1個目
m2 + 2m + 1
= (m + 1)2
展開
m 個の円
m 個の円が重なった時、
最大 m2 個の部分に分かれる。
3次元
m 個の球の中に、m +1 個目の球を入れる。
さらに、無理やり展開する。
2次元の議論から、
最大 m2 個の部分に
分かれている。
m3 + m2 + 1
< (m + 1)3
m 個の球が重なった時、
最大 m3 個の部分に分かれる。
Proof of Theorem 5.4.1

主張

任意の枝 Ex は t 3 218 本未満の枝としか依存関係にない。

Ex に含まれる頂点と同じ頂点を含む枝は t 3 218 本未満である。
半径4の球の体積は
半径1の球の体積の 43 = 26 倍である。
Bj’’’’
Bj’’’
Bj’’
x
Bj’
1以下
3以下
Bi
4以下
どの点も t 個以上の open unit ball で
カバーされていないため、
半径4の球に最大 26t 個含まれる。
m 個の球が重なったとき、
最大 m3 個の部分に分かれる。
よって、主張が正しいことがわかる。
Bj
Proof of Theorem 5.4.1

ハイパーグラフ H の有限のサブハイパーグラフ L を考える。


L の各枝は k 個以上の頂点からなる。(k-fold covering)
L の各枝は最大 d < t 3 218 本の L に含まれる枝と依存関係にある。
Theorem 5.2.1






ハイパーグラフ H’ = (V’, E’)
各枝 (∈ E’) は k’ 個以上の頂点からなる。
各枝 (∈ E’) は最大 d’ 本の他の枝と依存関係にある。
2k’-13 218 ≦ 2k’-1
e(d’+1) ≦ e･t
ならば
H’は2彩色可能である。
単色の枝が無い
Theorem 5.4.1 の仮定 (e･t 3 218 / 2 k-1 ≦ 1) より、L は2彩色可能である。
Proof of Theorem 5.4.1

ハイパーグラフ H の有限のサブハイパーグラフ L を考える。


L の各枝は k 個以上の頂点からなる。(k-fold covering)
L の各枝は最大 d < t 3 218 本の L に含まれる枝と依存関係にある。
Theorem 5.2.1






ハイパーグラフ H’ = (V’, E’)
各枝 (∈ E’) は k’ 個以上の頂点からなる。
x
Ex = {3,
3, 5,
5 8, 9}
9
各枝 (∈ E’) は最大 d’ 本の他の枝と依存関係にある。
2k’-13 218 ≦ 2k’-1
e(d’+1) ≦ e･t
ならば
H’は2彩色可能である。
単色の枝が無い
Theorem 5.4.1 の仮定 (e･t 3 218 / 2 k-1 ≦ 1) より、L は2彩色可能である。

青の頂点を F1 とし、赤の頂点を F2 とすれば、L は分解可能である。
Proof of Theorem 5.4.1

Compactness Argument (Theorem 5.2.2 と同じ)

有限のサブハイパーグラフ L が分解可能である。
位相空間・開被覆・コンパクト・
the axiom of choice （選択公理）で
うんたらかんたら・・・

ハイパーグラフ H が分解可能である。

Download Report