chap3.1-3.3

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

Download Report