Probabilistic Method Chapter 3 Alterations ある性質を持つ対象(グラフ、集合)が存在す ることを証明したい BasicなProbabilistic Method (Chapter 1) “ランダムな対象”を適当に定義して、対象が目的 の性質を持つ確率が正であることを示した Alterationを用いたProbabilistic Method ランダムに対象を決めてしまうと、目的の性質に は少し届かない ⇒対象のAlteration(変換)によって欠損を補う 3.1 Ramsey Numbers 1.1節で求めたR(k,k)の下界を改善 命題1.1.1(再掲) 定理3.1.1 R( k; k) > b2k=2c à n á 1à ( k) R( k; k) > n à k 2 2 R(3, 3) > 3 (n=4) R(4, 4) > 5.90 (n=7) R(10,10) > 115.11 (n=127) … for all n. R( k; k) > 1 e(1 + ð k=2 o(1)) k á2 ñ n ø eà 1k2k=2(1 à o(1)) Ramsey Number R ( k , `) 完全グラフKnの各枝を2色(赤・緑)に塗る K5 Ramsey Number R ( k , `) 完全グラフKnの各枝を2色(赤・緑)に塗る R ( k , `) > n⇔あるcoloringでは、赤の枝のみ の誘導部分グラフKk、緑の枝のみのK` が存 在しない K 5 Ramsey Number R ( k , `) 完全グラフKnの各枝を2色(赤・緑)に塗る R ( k , `) ≦ n⇔どのようなcoloringでも、赤の 枝のみの誘導部分グラフKk、または緑の枝 のみのK` が存在 K6 Ramsey Number R ( k , `) 完全グラフKnの各枝を2色(赤・緑)に塗る R ( k , `) ≦ n⇔どのようなcoloringでも、赤の 枝のみのKkまたは緑の枝のみのK` が存在 K6 K3 Proof of Proposition1.1.1 1.1節のおさらい 命題1.1.1(再掲) R( k; k) > b2k=2c [証明概略] Knの各枝をそれぞれ確率1/2でcoloringする。 このとき単色の誘導部分グラフKkの個数の期 à n á 1à ( k) 待値は 2 á2 k n = b2k=2c とすると期待値は1より小さくなる。 すなわち単色のKkが存在しないようなKnの coloringが可能である。 Idea of Alteration nが大きいと適当にKnをcoloringすると、単色 のKkが出来てしまう それぞれの単色誘導部分グラフの頂点を1つ ずつ取り去ってしまえば良い K3 R(k, k) > n -(Knから取り去った頂点数) Sum of Monochromatic まずはR(k, k)について あるnを選び、Knの枝を1/2で赤緑に塗り分けたとき、 単色の完全部分グラフKkはいくつできるか? Xn,k = 単色の完全部分グラフの数 E[Xn,k] = àn á k n頂点からk頂点を選ぶ組 み合わせ数 k 1à ( 2) á2 選んだk頂点間の枝が全て 同じ色である確率 Sum of Monochromatic à n á 1à ( k) 2 より, 2 à nk á 1à ( k) 2 となるcoloringφが存在 2 k E[Xn,k] = xn,k ≦ (xn,k : φに対する単色の誘導部分グラフKkの数) 単色の誘導部分グラフKkがxn,k個あるから、 à n á 1à ( k) 高々 2 頂点を取り除けばよい。 2 k à n á 1à ( k) 定理3.1.1 R( k; k) > n à k 2 2 for all n. Off-diagonal Ramsey Numbers R(k, `)について あるnを選び、Knの枝を確率pで赤、1-pで緑 に塗り分けたとき、単色の誘導部分グラフKk, K`はいくつできるか? Xn,k,` = redKkの数 + greenK`の数 ò E[Xn,k,`] = ó n k ò ( k2) p + ó n ` (1 à p) ( `2) Off-diagonal Ramsey Numbers à n á ( k) à n á ` ( E[Xn,k,`] = k p 2 + ` (1 à p) 2) より, à n á ( k) à n á ` ( xn,k,` ≦ k p 2 + ` (1 à p) 2) となるcoloringが存在 定理3.1.3 for all n , p∈[0,1] , à n á ( k) à n á ` ( R( k; ` ) > n à k p 2 à ` (1 à p) 2) 3.2 Independent Sets 独立集合:グラフGの頂点Vの部分集合で、 任意の2頂点間に枝を持たないもの G α(G) : 独立数 (最大独立集合の頂点数) α(G)=4 Idea of Alteration 適当にGの誘導部分グラフを作ると、 x個の頂点とy本の枝を含む x頂点から高々y頂点を 取り除けば、 独立な頂点集合が得られる ⇒α(G)≧x - y G Random subset G : 頂点数n, 平均次数d≧1 (枝数nd/2) Gの各頂点を確率 1/d p で部分集合Sに入れる. 誘導部分グラフG|Sの頂点数をX, 枝数をYとする. E[X]=np, E[Y]= nd áp2 2 Gの枝数 E [X à Y] = E [X ] à E [Y] 2 = np à nd á p 2 = n 2d 枝の両端点が Sに含まれる確率 p = n=(2 ánd 2) = で最大 1 d Alteration of Subgraph E[X-Y]=n/2d より、 x-y≧n/2dなる誘導部分グラフG|S*が存在 (x:G|S*の頂点数, y:G|S*の枝数) G|S*のx頂点から高々y頂点を取り除けば、 独立部分グラフが得られ、その頂点数はx-y 定理3.2.1 if |V|=n, |E|=nd/2, α(G)≧n/2d. 3.3 Combinatorial Geometry Heilbronn’s Triangle Problem 1×1 正方形 : U n(≧3)個の点の配置 : S U T(S) = Sの3頂点で出来る 最小の三角形の面積 T(S) 上手くSを配置したら、 どれだけT(S)を大きくできるか? Heilbronn’s Triangle Example T(n)=maxST(S) : 上手にn個の点の配置した場合のT(S) p 1/4 3 =3 1/2 1/2 2/3 T(3)=T(4)=1/2 T(5) = T(7)≧1/12, p T(8)≧ (2 à 3) =4, T(9)≧1/21, p T(10)≧ (3 17 à 11) =32 p 3 =9 Open Problem T(6) = 1=8 … Heilbronn’s Conjecture Heilbronnの予想 T(n) = O(1/n2) ? Komlosらによる反証 (1982) T(n) = Ω(log n/n2) →証明は複雑 Alterationを用いて T(n)=Ω(1/n2) を簡単に示す Idea of Alteration 適当にy個の頂点を配置したとき、 あるεより小さい 三角形がx個できたとする 高々x頂点を取り去れば、 全ての三角形がε以上 ⇒T(y-x)≧ε U Random Triangle 3点P, Q, RをU上に独立に一様確率で配置 μ : 三角形PQRの面積 U R μ≦εとなる三角形の数 (の期待値)を求めたいので、 εに対して Pr[μ≦ε]はどれくらいか ? μ Q P Distance from P to Q Pがランダムに配置されているとする U C : Pを中心とする半径bの円 C ':Pを中心とする半径b+dbの円 内に点Qが含まれる確率 ≦ |(C ’\C)|/|U| =π(b+db)2-πb2 =2πb・db (db*0) C’ C b P b+d b Height of R to PQ PQ=b なる2点P, Qが与えられているとする μ(PQR)≦εであるとき、 P’ RのPQからの高さhは h≦2ε/b 内に点Rが含まれる確率 ≦2(2ε/b)|P ’Q’|/|U| p ≦ 4 2 ï =b U P 2" b 2" b b Q Q’ Bound of probability Pr[b≦|PQ|≦b+db] ≦ 2πb・db p Pr[μ≦ε| |PQ|=b] ≦ 4 2 ï =b p したがって、0 ô b ô ∴Pr[μ≦ε]≦ 8 ; p 0 2 2 において積分して p (2ùb)(4 2 ï =b) db = 16ùï Alteration 2n to n points 2n個の点をU上に配置する X=面積が1/(100n2)より小さい三角形の数 E[X]= ( 2n 3 ) 2n頂点から3頂点を選ぶ 組み合わせ数 16ù á100n 2 (2n ) 3 16ù < 6 á100n 2 128ù = 600 n < n 選んだ三角形の面積が 1/(100n2)より小さい確率 Alteration 2n to n points E[X]< n より、 X*<nとなる2n個の点の配置S*が存在する (X* : S*で面積が1/(100n2)より小さい三角形の数) 配置S*のそのような三角形から頂点を1つずつ 取り除けば、全ての三角形の面積が1/(100n2) 以上となる 定理3.3.1 T(n)≧1/(100n2) , for all n
© Copyright 2024 ExpyDoc