Extremal Combinatrics Chapter 4 脊戸 和寿 Logo 内容に入る前に・・・ 輪講の有効利用法 内容を聞いただけでは力になりにくい。 教科書は比較的、易しく書いてあるのでざっと読み返すのをお勧め。 せっかく練習問題がいっぱいあるので、余裕があれば解くといいすよ。 練習問題の記号 － 簡単 無印 普通 ＋ やや難しい ！ 特別価値のある問題で、有益で、面白い！（らしい） Pigeonhole Principle 残りの１個のボールを箱にいれようと思うと、 必ず２個以上入る箱が出来てしまう。 ・・・ もし、 個以上の要素を 個の集合に分けるなら、 必ず 個以上の要素が入った集合が存在する。 ・・・ 4.1 Some quickies 命題４．１ どんなグラフにおいても、 同じ次数をもった２つの頂点が存在する。 （証明） ・・・ ・・・ ・・・ ・・・ 4.1 Some quickies 命題４．２ 頂点のどんなグラフ においても、 : independence numbeｒ 最大独立集合の要素数 : chromatic number 最小彩色数 （証明） ・・・ 4.1 Some quickies 命題４．３ を 頂点のグラフとする。 もし、各頂点の次数が少なくとも そのとき、グラフは連結である。 であれば、 （証明） ・・・ 頂点 ・・・ 4.2 The Erdos-Szekeres theorem 個の異なる数字からなる列 Aの 個の要素が同じ順序で現れる列 EX.) が成り立つとき、増加(increase)という が成り立つとき、減少(decrease)という 4.2 The Erdos-Szekeres theorem 定理４．４ (Erdos-Szekeres 1935) もし、 長さ を 個の異なる実数からなる列とする。 ならば、 は長さ 以上の増加部分列か、 以上の減少部分列のいずれか（もしくは、両方）をもつ。 （証明） ① 評価値を設定 ： で終わる増加部分列の最大長 ： で始まる減少部分列の最大長 4.2 The Erdos-Szekeres theorem 定理４．４ (Erdos-Szekeres 1935) もし、 長さ を 個の異なる実数からなる列とする。 ならば、 は長さ 以上の増加部分列か、 以上の減少部分列のいずれか（もしくは、両方）をもつ。 （証明） ② Pigeonhole Principle ・・・ 4.3 Mantel’s theorem 定理４．６ (Mantel 1907) 頂点のグラフ が 本の枝をもつなら、 そのとき、グラフは三角形をもつ。 （証明） 帰納法 との間に 少なくとも、 本の枝 枝数が条件を満たせない。 の時に定理が成り立つと仮定する。 : 頂点数 枝数 もし、 本の枝を もつなら仮定より、 三角形が存在する。 : ・・・ 高々、 本の枝 ・・・ 頂点 4.4 Turan’s theorem 定理４．７ (Turan 1941) 頂点のグラフ クリーク が、 をもたないなら、そのとき、 のときは、 Mantel’s theorem!! （証明） 帰納法 不等式は成立。(trivial) 頂点数が高々、 : の時に不等式が成り立つと仮定 クリ―クをもたない、 枝数が最大の 頂点グラフ クリークを持っている クリーク 4.4 Turan’s theorem 定理４．７ (Turan 1941) 頂点のグラフ クリーク が、 をもたないなら、そのとき、 のときは、 Mantel’s theorem!! （証明） 帰納法 仮定より。 枝数をカウント クリーク 本存在すると、 クリーク になってしまう。 4.5 The Dirichlet’s theorem 定理４．８ (Dirichlet 1979) を実数とする。どんな自然数 に対しても、 以下の式が成り立つような、有理数 が存在する。 （証明） は無理数とする。 ・・・ 無理数をよい精度 で近似できる有理数 が存在する！ 4.6 Swell-colored graphs 定理４．９ (Ward-Szabo 1994) 頂点完全グラフ は、 色より少ない色で swell-colorすることができない。 swell color : 枝への彩色を考える。少なくとも２色は使うものとする。 そのとき、各三角形の枝がちょうど１色か３色で塗られること。 4.6 Swell-colored graphs 定理４．９ (Ward-Szabo 1994) 頂点完全グラフ は、 色より少ない色で swell-colorすることができない。 （証明） : 色でswell-color された完全グラフ : 頂点 につながっている枝で、 色 で塗られているものの数 最大値を とする。 ・・・ 4.6 Swell-colored graphs 定理４．９ (Ward-Szabo 1994) 頂点完全グラフ は、 色より少ない色で swell-colorすることができない。 （証明） 主張４．１０ につながっている 本の枝は 以外の色かつ、全て異なる色で塗られている。 完全グラフ 色でswell-color された完全グラフ 4.7 The weight shifting argument 命題４．１１ 個の巣箱に 匹の鳩を入れる。 ただし、空の箱を作らないように入れることとする。 どんな入れ方をしたとしても、巣箱で1匹にならなくて済む鳩は、 高々、 匹しかいない。 （証明） ・・・ ・・・ 4.7 The weight shifting argument 定理４．１２ (Graham-Kleitman 1973) 頂点の完全グラフ 異なる整数 のそれぞれの枝に、 を割り当てる。 そのとき、枝が増加列をつくる少なくとも長さ の道がある。 4.7 The weight shifting argument 定理４．１２ (Graham-Kleitman 1973) 頂点の完全グラフ 異なる整数 のそれぞれの枝に、 を割り当てる。 そのとき、枝が増加列をつくる少なくとも長さ の道がある。 証明の方針 ① 各節点 に で終わる最長増加パスの長さを重み として設定 ② 全頂点の重みの和を計算 ③ Average Principleより定理をみたす重みをもつ頂点が存在 4.7 The weight shifting argument 定理４．１２ (Graham-Kleitman 1973) 頂点の完全グラフ 異なる整数 のそれぞれの枝に、 を割り当てる。 そのとき、枝が増加列をつくる少なくとも長さ の道がある。 （証明） 枝の追加ごとに全体の 重みは少なくとも２増える 4.7 The weight shifting argument 定理４．１２ (Graham-Kleitman 1973) 頂点の完全グラフ 異なる整数 のそれぞれの枝に、 を割り当てる。 そのとき、枝が増加列をつくる少なくとも長さ （証明） 枝の追加ごとに全体の重みは少なくとも２増える の道がある。 4.8 Pigeonhole and resolution Resolution Resolution Proof Resolutionを使って、与えられた節集合が UNSATであることを証明すること 4.8 Pigeonhole and resolution example false !! 4.8 Pigeonhole Principle 定理４．１３ (Haken 1985) 十分大きな において、 に対するどんな Resolution proofも少なくともサイズ 必要である。 どの鳩も どこかの巣箱に UNSAT !! (i) (ii) for each for each and １つの巣箱には 1匹の鳩
© Copyright 2024 ExpyDoc
