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(再掲) R(3, 3) > 3 (n=4) R(4, 4) > 5.90 (n=7) R(10,10) > 115.11 (n=127) 命題1.1.1(再掲) 定理3.1.1 for all n. …

Ramsey Number R ( k , `) 完全グラフKnの各枝を2色(赤・緑)に塗る K5

Ramsey Number R ( k , `) 完全グラフKnの各枝を2色(赤・緑)に塗る R ( k , `) > n⇔あるcoloringでは、赤の枝のみの誘導部分グラフKk、緑の枝のみのK` が存在しない K5

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節のおさらい [証明概略] Knの各枝をそれぞれ確率1/2でcoloringする。 このとき単色の誘導部分グラフKkの個数の期待値は とすると期待値は1より小さくなる。 すなわち単色のKkが存在しないようなKnのcoloringが可能である。 命題1.1.1(再掲)

Idea of Alteration R(k, k) > n -(Knから取り去った頂点数) nが大きいと適当にKnをcoloringすると、単色のKkが出来てしまう それぞれの単色誘導部分グラフの頂点を1つずつ取り去ってしまえば良い K3 R(k, k) > n -(Knから取り去った頂点数)

選んだk頂点間の枝が全て同じ色である確率 Sum of Monochromatic まずはR(k, k)について あるnを選び、Knの枝を1/2で赤緑に塗り分けたとき、単色の完全部分グラフKkはいくつできるか？ Xn,k = 単色の完全部分グラフの数 E[Xn,k] = n頂点からk頂点を選ぶ組み合わせ数 選んだk頂点間の枝が全て同じ色である確率

Sum of Monochromatic E[Xn,k] = より, xn,k ≦ となるcoloringφが存在 (xn,k : φに対する単色の誘導部分グラフKkの数) 単色の誘導部分グラフKkがxn,k個あるから、　　高々 頂点を取り除けばよい。 定理3.1.1 for all n.

Off-diagonal Ramsey Numbers R(k, `)について あるnを選び、Knの枝を確率pで赤、1-pで緑に塗り分けたとき、単色の誘導部分グラフKk, K`はいくつできるか？ 　Xn,k,` = redKkの数 + greenK`の数 E[Xn,k,`] =

Off-diagonal Ramsey Numbers E[Xn,k,`] = より, xn,k,` ≦ となるcoloringが存在 定理3.1.3 for all n , p∈[0,1] ,

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の各頂点を確率 p で部分集合Sに入れる. 誘導部分グラフG|Sの頂点数をX, 枝数をYとする. E[X]=np, E[Y]= 1/d Gの枝数 枝の両端点が Sに含まれる確率 で最大

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 T(S) = Sの3頂点で出来る 最小の三角形の面積 U T(S) 上手くSを配置したら、 どれだけT(S)を大きくできるか？

Heilbronn’s Triangle Example T(n)=maxST(S) : 上手にn個の点の配置した場合のT(S) T(7)≧1/12, T(8)≧ , T(9)≧1/21, T(10)≧ 1/4 1/2 1/2 2/3 T(3)=T(4)=1/2 Open Problem …

Heilbronn’s Conjecture Komlosらによる反証 (1982) 　→証明は複雑 Alterationを用いて T(n)=Ω(1/n2) を簡単に示す T(n) = O(1/n2) ? T(n) = Ω(log n/n2)

Idea of Alteration 適当にy個の頂点を配置したとき、 あるεより小さい 三角形がx個できたとする 高々x頂点を取り去れば、 全ての三角形がε以上 ⇒T(y-x)≧ε U

Random Triangle 3点P, Q, RをU上に独立に一様確率で配置 μ : 三角形PQRの面積 μ≦εとなる三角形の数 (の期待値)を求めたいので、 εに対して Pr[μ≦ε]はどれくらいか ? U R P μ Q

Distance from P to Q Pがランダムに配置されているとする C : Pを中心とする半径bの円 C ':Pを中心とする半径b+dbの円 内に点Qが含まれる確率 ≦ |(C ’＼C)|/|U| =π(b+db)2-πb2 =2πb・db (db*0) U C ’ C P b+db b

Height of R to PQ PQ=b なる2点P, Qが与えられているとする μ(PQR)≦εであるとき、 RのPQからの高さhは h≦2ε/b 内に点Rが含まれる確率 ≦2(2ε/b)|P ’Q’|/|U| ≦ U P ’ P b Q Q’

Bound of probability Pr[b≦|PQ|≦b+db] ≦ 2πb・db Pr[μ≦ε| |PQ|=b] ≦ したがって、　 において積分して ∴Pr[μ≦ε]≦

Alteration 2n to n points 2n個の点をU上に配置する X=面積が1/(100n2)より小さい三角形の数 E[X]= 2n頂点から3頂点を選ぶ組み合わせ数 選んだ三角形の面積が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

Turán's Theorem Turánの定理より α(G)≧n/(d+1)が導ける. Turánの定理 |E(G)|> ならば、 Gはサイズsのクリークを持つ.

Improved lower bound of α(G) を示す概要 全ての頂点にランダムに番号を振る. 頂点vの番号がvのどの隣接頂点 よりも小さい時のみ、 集合Sにvを挿入. 明らかにX|Sは独立集合. G 6 1 4 5 3 7 8 2