5.3, 5.4 D2　岡本　和也.

Presentation on theme: "5.3, 5.4 D2　岡本　和也."— Presentation transcript:

1 5.3, 5.4 D2　岡本　和也

2 5.3 Ramsey Number の下限の改良 The Local Lemma を利用する。

3 Ramsey Number の復習 R(k, l) n節点の完全グラフKnの枝を２色（赤・青）で
　塗り分けるとき、どんな塗り分け方をしたとしても、 　赤枝のみを持つ完全部分グラフKｋか青枝のみを 　持つ完全部分グラフKlが存在するような最小のn。 完全グラフ 　どの2頂点間にも枝が存在するグラフ。

4 Ramsey Number の復習 R(k, l) n節点の完全グラフKnの枝を2色（赤・青）で
　塗り分けるとき、どんな塗り分け方をしたとしても、 　赤枝のみを持つ完全部分グラフKｋか青枝のみを 　持つ完全部分グラフKlが存在するような最小のn。 R(3, 3) = 6

5 Ramsey Number の下限の改良 k = l の場合 ( R (k, k) )
ランダムに辺に色を塗る。 S ・・・ 完全グラフ Kn の k 頂点からなる頂点集合 AS ・・・ S の頂点間の枝が単色になる事象 Pr(AS) = AS は他のほとんどの事象 AS’　と互いに独立である。 S と S’ が2頂点以上共有していない場合 ・・・ 互いに独立である。 S と S’ が2頂点以上共有している場合 ・・・ 互いに独立でない。 互いに独立でない S’ は多く見積もっても　　　　　　　　　　以下である。 1/2 1/2 1/2 n頂点(Kn) k頂点(S)

6 The Local Lemma; Symmetric Caseの復習
事象 A1, A2, …, An がある。 任意の事象 Ai に関して Pr(Ai) ≦ p 任意の事象 Ai は最大 d 個以外の事象と互いに独立。 ep(d+1) ≦ 1 　　　　　　　　　　　　　　　　　　ならば 全ての事象が起きない可能性がある。

7 Ramsey Number の下限の改良 k = l の場合 ( R (k, k) )
ランダムに辺に色を塗る。 S ・・・ 完全グラフ Kn の k 頂点からなる頂点集合 AS ・・・ S の頂点間の枝が単色になるイベント Pr(AS) = AS は他のほとんどのイベント AS’　と互いに独立である。 S と S’ が2頂点以上共有していない場合 ・・・ 互いに独立である。 S と S’ が2頂点以上共有している場合 ・・・ 互いに独立でない。 互いに独立でない S’ は多く見積もっても　　　　　　　　　　以下である。 p n頂点(Kn) d k頂点(S)

8 Ramsey Number の下限の改良 k = l の場合 ( R (k, k) )
Proposition 5.3.1 ep(d+1) ≦ 1 ならば R(k, k) > n ヒント > p. 26 の より2倍良くなった。

9 The Local Lemma 互いに独立でない事象が多いと効果が薄い。 symmetric でない場合 (k = l) を考える。
symmetric な場合、k が大きくなるにつれて d が大きくなる。 symmetric でない場合 (k = l) を考える。 さらに、l が小さい場合を考える。 例えば、R(k, 3)

10 Ramsey Number の下限の改良 k = l の場合 ( R (k, 3) )
辺を確率 p で青色に塗る。（後は赤色に塗る。） T ・・・ 完全グラフ Kn の3頂点からなる頂点集合 AT ・・・ T の頂点間の枝が青色になる事象 S ・・・ 完全グラフ Kn の k 頂点からなる頂点集合 BS ・・・ S の頂点間の枝が赤色になる事象 Pr(AT) = p3 Pr(BS) = AT は 3C2(n – 3) < 3n の AT’ と nCk 以下の BS と独立でない。 BS は kC2(n – k) < k2n/2 の AT と nCk 以下の BS’ と独立でない。

11 The Local Lemma; General Case の復習
事象 A1, A2, …, An がある。 Ai, Aj が独立でない場合、(i, j) ∈ E とする。（必要十分条件） 任意の事象 Ai に関して、 (1 ≦ i ≦ n) 　　　　　　　　　　　　　　　　　　ならば 全ての事象が起きない可能性がある。

12 Ramsey Number の下限の改良 k = l の場合 ( R (k, 3) )
辺を確率 p で青色に塗る。（後は赤色に塗る。） T ・・・ 完全グラフ Kn の3頂点からなる頂点集合 AT ・・・ T の頂点間の枝が青色になる事象 S ・・・ 完全グラフ Kn の k 頂点からなる頂点集合 BS ・・・ S の頂点間の枝が赤色になる事象 Pr(AT) = p3 Pr(BS) = AT は 3C2(n – 3) < 3n の AT’ と nCk 以下の BS と独立でない。 BS は kC2(n – k) < k2n/2 の AT と nCk 以下の BS’ と独立でない。

13 Ramsey Number の下限の改良 k = l の場合 ( R (k, 3) )
Ai = AT ならば xi = x Ai = BS ならば xi = y AT : BS : ならば R(k, 3) > n 最も n が大きくなるように p, x, y を定めると・・・ > （c は定数）

14 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 を用いないどんな証明よりも　　　　　　良い結果である。

15 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次元)

16 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 に覆われるような点が出来てしまう。 （個人的見解）

17 Theorem 5.4.1 ならば F = {Bi}i∈I を k-fold covering とする。
R3 のどの点も t 個以上の open unit ball に　　　　含まれていない。 e･t / 2 k-1 ≦ 1 F は分解可能である。 ならば Theorem を利用して導く。

18 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}} Ex = {2}, Ey = {2} 2 x y 3

19 Proof of Theorem 5.4.1 主張 任意の枝 Ex は t 3 218 本未満の枝としか依存関係にない。
半径4の球の体積は 半径1の球の体積の 43 = 26 倍である。 どの点も t 個以上の open unit ball で カバーされていないため、 半径4の球に最大 26t 個含まれる。 m 個の球が重なったとき、 最大 m3 個の部分に分かれる。 よって、主張が正しいことがわかる。 Bj’’’’ Bj’’ Bj’ x Bj’’’ 1以下 3以下 Bi 4以下 Bj

20 m 個の球が重なったとき、 最大 m3 個の部分に分かれる？
2次元 m +1個目 2m 本 m2 + 2m + 1 = (m + 1)2 展開 m 個の円 m 個の円が重なった時、 最大 m2 個の部分に分かれる。 3次元 m 個の球の中に、m +1 個目の球を入れる。 さらに、無理やり展開する。 2次元の議論から、 最大 m2 個の部分に 分かれている。 m3 + m2 + 1 < (m + 1)3 m 個の球が重なった時、 最大 m3 個の部分に分かれる。

21 Proof of Theorem 5.4.1 主張 任意の枝 Ex は t 3 218 本未満の枝としか依存関係にない。
半径4の球の体積は 半径1の球の体積の 43 = 26 倍である。 どの点も t 個以上の open unit ball で カバーされていないため、 半径4の球に最大 26t 個含まれる。 m 個の球が重なったとき、 最大 m3 個の部分に分かれる。 よって、主張が正しいことがわかる。 Bj’’’’ Bj’’ Bj’ x Bj’’’ 1以下 3以下 Bi 4以下 Bj

22 Proof of Theorem 5.4.1 ハイパーグラフ H の有限のサブハイパーグラフ L を考える。
L の各枝は k 個以上の頂点からなる。(k-fold covering) L の各枝は最大 d < t 本の L に含まれる枝と依存関係にある。 ハイパーグラフ H’ = (V’, E’) 各枝 (∈ E’) は k’ 個以上の頂点からなる。 各枝 (∈ E’) は最大 d’ 本の他の枝と依存関係にある。 e(d’+1) ≦ 2k’-1 H’は2彩色可能である。 Theorem の仮定 (e･t / 2 k-1 ≦ 1) より、L は2彩色可能である。 Theorem 5.2.1 e(d’+1) ≦ e･t ≦ 2k’-1 ならば 単色の枝が無い

23 Proof of Theorem 5.4.1 ハイパーグラフ H の有限のサブハイパーグラフ L を考える。
L の各枝は k 個以上の頂点からなる。(k-fold covering) L の各枝は最大 d < t 本の L に含まれる枝と依存関係にある。 ハイパーグラフ H’ = (V’, E’) 各枝 (∈ E’) は k’ 個以上の頂点からなる。 各枝 (∈ E’) は最大 d’ 本の他の枝と依存関係にある。 e(d’+1) ≦ 2k’-1 H’は2彩色可能である。 Theorem の仮定 (e･t / 2 k-1 ≦ 1) より、L は2彩色可能である。 青の頂点を F1 とし、赤の頂点を F2 とすれば、L は分解可能である。 Theorem 5.2.1 x x Ex = {3, 5, 8, 9} 3, 5, 8, 9 5 e(d’+1) ≦ e･t ≦ 2k’-1 ならば 単色の枝が無い

24 Proof of Theorem 5.4.1 Compactness Argument (Theorem 5.2.2 と同じ)
有限のサブハイパーグラフ L が分解可能である。 ハイパーグラフ H が分解可能である。 位相空間・開被覆・コンパクト・ the axiom of choice （選択公理）で うんたらかんたら・・・