Probabilistic Method.

Presentation on theme: "Probabilistic Method."— Presentation transcript:

1 Probabilistic Method

2 Chapter 3 Alterations ある性質を持つ対象（グラフ、集合）が存在することを証明したい
BasicなProbabilistic Method (Chapter 1) “ランダムな対象”を適当に定義して、対象が目的の性質を持つ確率が正であることを示した Alterationを用いたProbabilistic Method ランダムに対象を決めてしまうと、目的の性質には少し届かない ⇒対象のAlteration(変換)によって欠損を補う

3 3.1 Ramsey Numbers … 1.1節で求めたR(k,k)の下界を改善 命題1.1.1(再掲)
R(3, 3) > (n=4) R(4, 4) > (n=7) R(10,10) > (n=127) 命題1.1.1(再掲) 定理 for all n. …

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

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

6 Ramsey Number R ( k , `) 完全グラフKnの各枝を2色(赤・緑)に塗る
R ( k , `) ≦ n⇔どのようなcoloringでも、赤の枝のみの誘導部分グラフKk、または緑の枝のみのK` が存在 K6

7 Ramsey Number R ( k , `) 完全グラフKnの各枝を2色(赤・緑)に塗る
R ( k , `) ≦ n⇔どのようなcoloringでも、赤の枝のみのKkまたは緑の枝のみのK` が存在 K6 K3

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

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

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

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

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

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

14 3.2 Independent Sets 独立集合:グラフGの頂点Vの部分集合で、 任意の2頂点間に枝を持たないもの α(G) : 独立数
(最大独立集合の頂点数) G α(G)=4

15 Idea of Alteration 適当にGの誘導部分グラフを作ると、x個の頂点とy本の枝を含む x頂点から高々y頂点を 取り除けば、
独立な頂点集合が得られる ⇒α(G)≧x - y G

16 Random subset G : 頂点数n, 平均次数d≧1 (枝数nd/2) Gの各頂点を確率 p で部分集合Sに入れる.
誘導部分グラフG|Sの頂点数をX, 枝数をYとする. E[X]=np, E[Y]= 1/d Gの枝数 枝の両端点が Sに含まれる確率 で最大

17 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 定理 if |V|=n, |E|=nd/2, α(G)≧n/2d.

18 3.3 Combinatorial Geometry
Heilbronn’s Triangle Problem 1×1 正方形 : U n(≧3)個の点の配置 : S T(S) = Sの3頂点で出来る 最小の三角形の面積 U T(S) 上手くSを配置したら、 どれだけT(S)を大きくできるか？

19 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 …

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

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

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

23 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

24 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’

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

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

27 Alteration 2n to n points
E[X]< n より、 X*<nとなる2n個の点の配置S*が存在する (X* : S*で面積が1/(100n2)より小さい三角形の数) 配置S*のそのような三角形から頂点を1つずつ取り除けば、全ての三角形の面積が1/(100n2)以上となる 定理 T(n)≧1/(100n2) , for all n

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

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