Extremal Combinatrics Chapter 4 脊戸　和寿 Extremal Combinatorics

Extremal Combinatorics 内容に入る前に・・・ 輪講の有効利用法 内容を聞いただけでは力になりにくい。 教科書は比較的、易しく書いてあるのでざっと読み返すのをお勧め。 せっかく練習問題がいっぱいあるので、余裕があれば解くといいすよ。 練習問題の記号 　－　　簡単 無印　 普通 　＋　　やや難しい 　！　　特別価値のある問題で、有益で、面白い！（らしい） Extremal Combinatorics

Extremal Combinatorics Pigeonhole Principle 残りの１個のボールを箱にいれようと思うと、 必ず２個以上入る箱が出来てしまう。 ・・・ もし、 個以上の要素を 　個の集合に分けるなら、 必ず　 個以上の要素が入った集合が存在する。 ・・・ Extremal Combinatorics

Extremal Combinatorics 4.1 Some quickies 命題４．１ どんなグラフにおいても、 同じ次数をもった２つの頂点が存在する。 （証明） ・・・ ・・・ ・・・ ・・・ Extremal Combinatorics

Extremal Combinatorics 4.1 Some quickies 命題４．２ 　　頂点のどんなグラフ　　においても、 （証明） 　　　: independence numbeｒ 最大独立集合の要素数 　　 : chromatic number 最小彩色数 ・・・ Extremal Combinatorics

Extremal Combinatorics 4.1 Some quickies 命題４．３ 　　を　　頂点のグラフとする。 もし、各頂点の次数が少なくとも　　　 であれば、 そのとき、グラフは連結である。 （証明） ・・・ ・・・ 頂点 Extremal Combinatorics

4.2 The Erdos-Szekeres theorem 　個の異なる数字からなる列 Aの　個の要素が同じ順序で現れる列 EX.) が成り立つとき、増加(increase)という が成り立つとき、減少(decrease)という Extremal Combinatorics

4.2 The Erdos-Szekeres theorem 　　　　　　　　　　　　　　　を　 個の異なる実数からなる列とする。 もし、　　　　　　　ならば、　　は長さ　　　　以上の増加部分列か、 長さ　　　　以上の減少部分列のいずれか（もしくは、両方）をもつ。 （証明） ①　評価値を設定 ：　 で終わる増加部分列の最大長 ：　 で始まる減少部分列の最大長 Extremal Combinatorics

4.2 The Erdos-Szekeres theorem 　　　　　　　　　　　　　　　を　 個の異なる実数からなる列とする。 もし、　　　　　　　ならば、　　は長さ　　　　以上の増加部分列か、 長さ　　　　以上の減少部分列のいずれか（もしくは、両方）をもつ。 （証明） ②　Pigeonhole Principle ・・・ Extremal Combinatorics

Extremal Combinatorics 4.3 Mantel’s theorem 定理４．６ (Mantel 1907) 　　頂点のグラフ　　が 本の枝をもつなら、　 そのとき、グラフは三角形をもつ。 （証明）　帰納法 　　との間に 少なくとも、 　　　　本の枝 枝数が条件を満たせない。 の時に定理が成り立つと仮定する。 : 頂点 　:　頂点数　　　 　　　枝数 ・・・ ・・・ もし、　　　　本の枝を もつなら仮定より、 三角形が存在する。 高々、　　 　　本の枝 Extremal Combinatorics

Extremal Combinatorics 4.4 Turan’s theorem 定理４．７ (Turan 1941) 　　頂点のグラフ　　　　　　　　が、　 　　　クリーク　　　　をもたないなら、そのとき、 のときは、 Mantel’s theorem!! （証明）　帰納法 不等式は成立。(trivial) 頂点数が高々、 の時に不等式が成り立つと仮定 　クリーク : 　　　 クリ―クをもたない、 　枝数が最大の　　頂点グラフ 　クリークを持っている Extremal Combinatorics

Extremal Combinatorics 4.4 Turan’s theorem 定理４．７ (Turan 1941) 　　頂点のグラフ　　　　　　　　が、　 　　　クリーク　　　　をもたないなら、そのとき、 のときは、 Mantel’s theorem!! （証明）　帰納法 仮定より。 枝数をカウント 　本存在すると、 　　　クリーク になってしまう。 　クリーク Extremal Combinatorics

4.5 The Dirichlet’s theorem を実数とする。どんな自然数　 に対しても、 以下の式が成り立つような、有理数　　 が存在する。 無理数をよい精度で近似できる有理数が存在する！ （証明） 　は無理数とする。 ・・・ Extremal Combinatorics

Extremal Combinatorics 4.6 Swell-colored graphs 定理４．９ (Ward-Szabo 1994) 頂点完全グラフ　　は、　　　　色より少ない色で swell-colorすることができない。　 swell color : 枝への彩色を考える。少なくとも２色は使うものとする。 そのとき、各三角形の枝がちょうど１色か３色で塗られること。 Extremal Combinatorics

Extremal Combinatorics 4.6 Swell-colored graphs 定理４．９ (Ward-Szabo 1994) 頂点完全グラフ　　は、　　　　色より少ない色で swell-colorすることができない。　 （証明） : 　色でswell-color された完全グラフ : 頂点　 につながっている枝で、 　色　で塗られているものの数 　最大値を　 とする。 ・・・ Extremal Combinatorics

Extremal Combinatorics 4.6 Swell-colored graphs 定理４．９ (Ward-Szabo 1994) 頂点完全グラフ　　は、　　　　色より少ない色で swell-colorすることができない。　 （証明） 主張４．１０ 　につながっている　　　　本の枝は 　 以外の色かつ、全て異なる色で塗られている。 完全グラフ 色でswell-color された完全グラフ Extremal Combinatorics

4.7 The weight shifting argument 命題４．１１ 個の巣箱に　　　　　　　　　　　匹の鳩を入れる。 ただし、空の箱を作らないように入れることとする。 どんな入れ方をしたとしても、巣箱で1匹にならなくて済む鳩は、 高々、　　　　　匹しかいない。 （証明） ・・・ ・・・ Extremal Combinatorics

4.7 The weight shifting argument 定理４．１２ (Graham-Kleitman 1973) 頂点の完全グラフ　　 のそれぞれの枝に、 異なる整数　　　　　　　　　　　　を割り当てる。 そのとき、枝が増加列をつくる少なくとも長さ　　　　の道がある。 Extremal Combinatorics

4.7 The weight shifting argument 定理４．１２ (Graham-Kleitman 1973) 頂点の完全グラフ　　 のそれぞれの枝に、 異なる整数　　　　　　　　　　　　を割り当てる。 そのとき、枝が増加列をつくる少なくとも長さ　　　　の道がある。 証明の方針 ①　各節点　 に　 で終わる最長増加パスの長さを重み　　として設定 ②　全頂点の重みの和を計算 ③　Average Principleより定理をみたす重みをもつ頂点が存在 Extremal Combinatorics

4.7 The weight shifting argument 定理４．１２ (Graham-Kleitman 1973) 頂点の完全グラフ　　 のそれぞれの枝に、 異なる整数　　　　　　　　　　　　を割り当てる。 そのとき、枝が増加列をつくる少なくとも長さ　　　　の道がある。 （証明） 枝の追加ごとに全体の 重みは少なくとも２増える Extremal Combinatorics

4.7 The weight shifting argument 定理４．１２ (Graham-Kleitman 1973) 頂点の完全グラフ　　 のそれぞれの枝に、 異なる整数　　　　　　　　　　　　を割り当てる。 そのとき、枝が増加列をつくる少なくとも長さ　　　　の道がある。 （証明） 枝の追加ごとに全体の重みは少なくとも２増える Extremal Combinatorics

4.8 Pigeonhole and resolution Resolution Proof Resolutionを使って、与えられた節集合が UNSATであることを証明すること Extremal Combinatorics

4.8 Pigeonhole and resolution example false !! Extremal Combinatorics

Extremal Combinatorics 4.8 Pigeonhole Principle 定理４．１３ (Haken 1985) 十分大きな　 において、　　 に対するどんなResolution proofも少なくともサイズ　　　必要である。 どの鳩も どこかの巣箱に UNSAT !! (i) for each (ii) for each and １つの巣箱には 1匹の鳩 Extremal Combinatorics