Document

Probabilistic Method
第１回
輪講の進め方
1: Basic Method
輪講の進め方
日時：基本的に金曜日の夕方
 進め方：１回で２人が発表
（１回目と２回目のみ変則）
 前期：５章までを予定
後期：残り（９章まで）

1.1 THE PROBABILISTIC METHOD

Probabilistic Method （確率的手法）
離散数学の多くの問題への取り組みに
対して強力なツールの１つ。
ある性質をもつ構造に対して適切な確率空間
を定義し、その確率空間内でその性質が
正の確率をもつことを示す。
例： Ramsey Number

R(k, l)
n節点の完全グラフKnの枝を２色（赤・青）
で塗り分けるとき、どんな塗りわけ方をしたとしても
赤枝のみを持つ完全部分グラフKｋか青枝のみを
持つ完全部分グラフKｌが存在するような最小のn
・完全グラフ
どの２頂点間にも枝が存在するグラフ
Lower Bound for R(k,k)

定理1.1.1
k
1  
2
n
もし、    2
k 
 1 であれば、R(k,k) > n.
全ての３以上のkに対して、
R(k,k) > 2 k / 2  が成り立つ。
証明

確率½でグラフの各枝を赤か青で塗り分
ける。

ｋ頂点を固定（集合R）したときに、
そのｋ頂点から成る完全グラフの全枝が
赤か青で塗られている事象をARとする。
k
1 
 2
Pr( AR )  2
証明
n
 集合Rの要素数は全部で 
 k  個。
 

事象ARのうち少なくとも１つの事象が起こ
る確率は高々、
k
1  
2
n
   2
k 
1
事象ARが起こらない確率が存在する。
R(k,k) > n
証明

n = 2
k/2
k
1 
2
n
   2
k 

とすると、
21 k / 2 n k

 k 2 / 2  1　(k  3)
k! 2
定理１．１．１
n頂点の完全グラフを赤か青の２色で塗
りわけるときに、全枝が赤か青かで塗られ
ている2log n節点の完全部分グラフが存
在しないような塗り分け方が存在する。

実際に塗り分けると・・・

塗り方は有限だから全部調べれば、もち
ろん条件を満たす塗りわけ方は見つかる。
⇒ 現実的な時間でできそうにない。

しかし、実は・・・・
事象ARのうち少なくとも１つの事象が起こ
る確率は高々、
k
1 
2
n
   2
k 

1 k / 2
2
k!

n
2
k
k2 /2
 1　(k  3)
⇒ 適当に塗っても高い確率で成功する！！
1.2 GRAPH THEORY
T(V,E) : tournament（有効グラフ）
V : 節点集合
E : 枝集合
正し、枝集合の中には（x,y)か(y,x）の
どちらかしか含まれない。

(x,y) : xがyを負かすという意味

Tが性質Skを持つ
全てのk人の集合に対して、
ｋ人全てに勝つ人間が存在する。

例： T3={ V, E }, V={1, 2, 3}
E={(1,2) , (2,3) , (3,1)}
⇒ 性質S1をもつ。

問題
全ての有限値kに対して、性質Skをもつ
tournamentは存在するか？？
定理1.2.1
n
k nk



(
1

2
)
 1 であれば、そのとき
もし、  k 
 
性質Skをもつn節点のtournamentが存在する。

証明

ランダムなn節点のtournamentを考える。
ランダムなn節点のtournament
n個の節点から２個を選び、その２節点を
つなぐ有向枝として(x,y)か(y,x)の
どちらかを確率1/2で選ぶ。
⇒ tournamentの数は全部で 2
n
2
 
個。
証明

節点集合Vからサイズkの部分集合Kを
１つ取り出し、集合Kの人間（節点）全員に
勝利する人間（節点）がいない事象をAkと
おく。
k
Pr( Ak )  (1  2 )
nk
証明
n
 集合Kの選び方は全部で 
 k  個。
 

事象Akのうち少なくとも１つの事象が起こ
る確率は高々、
n
Pr(  Ak )   Pr( Ak )  (1  2  k ) n  k  1
K V
K V
k 
|K |k
|K |k
事象Akが起こらない確率が存在する。
性質Skをもつtournamentが存在。

支配集合：U
無向グラフGの全ての節点が節点部分集合
Uに含まれているか、U内の節点に隣接して
いる。
U

定理1.2.2
n節点のグラフG=(V,E)の最低次数がδ
1  ln(   1)
であるとき、高々、サイズ n   1
の支配集合をグラフGはもつ。
証明


確率p∈[0,1]でVの節点を選ぶ。
X : 上で選んだ節点集合
Y : V-Xの中でXに隣接してない節点集合
|x|の期待値はpn
X
隣接節点
集合
Y
証明
Vから任意に選んだ節点vがYに入る確率
Pr(v  Y )  (1  p)
 1
|X|+|Y|の期待値  np  n(1  p)
ln(   1)
p
 1
とすると、
1  ln(   1)
|X|+|Y|の期待値  n
 1
 1
決定性アルゴリズム

実際に支配集合になるように節点を１つ
１つ選んでいく。

各ステップでまだカバーされてない節点を
最も多くカバーする節点を選ぶ。

C(v) : 節点vとその隣接節点の集合。

節点を選んでいくときに、まだカバーされ
ていない、節点uの数をrと仮定する。

仮定より、集合C(u)の（重複も許した）
要素の和は、r(1+δ)以上。

よって、各集合C(U)に含まれる要素数は
少なくとも、ｒ（δ+1)/n個。
なので、次の要素を選んだ後に
カバーされてない変数の個数は
 1

r 1 

n 

 1
つまり、各ステップで、 1  n
の割合で減少していく。
ln(   1)
n
ステップ繰り返す。

 1
n
個となるので、
 1
⇒ 残りの変数が
これを支配集合の中に入れてしまえば、
定理1.2.2の値が達成される。

カット
グラフＧの頂点集合Ｖを２つの互いに素な
集合Ｖ１とＶ２に分けること。

カットのサイズ
枝の端点の一方がＶ１にもう一方がＶ２に
含まれるような枝の数。グラフＧにおける
カットサイズの最小値を枝連結度という。
補題1.2.3
G(V,E)を最小次数δのグラフとして、
V=V1∪V2をカットサイズがδ以下となる
ものとする。そのとき、どの支配集合Ｕも
V1,V2内の両方に頂点をもつ。

証明
補題が誤りであると仮定する。
⇒ Ｕ ⊆ V1 とする。
 V2から任意の節点vを選ぶ。
 v1,v2,…,vδをvの隣接節点とする。

証明
各i (1≦i≦δ)について以下のように
枝を張る。
① vi∈ V1なら、 ei ={v,vi}をはる。
② vi∈ V2なら、 ei ={u,vi}をはる。
・・・Ｕが支配集合なので必ず隣接
する節点uが少なくとも１つは
存在する。

v1
v
V2
V1
u
v2
証明

①、②ではったδ本の枝は全て異なって
いて、しかもカットされている。
⇒ 補題でグラフのカットサイズはδより
小さいことを仮定している。
⇒ 矛盾 ⇒ 補題を誤りとした仮定が誤り。
1.3 COMBINATORICS
Hypergraph （超グラフ）
V : 頂点集合
E : 頂点集合の部分集合族

例
V : { 1, 2, 3, 4, 5}
E : { ( 1, 2, 4), ( 2, 3, 4, 5), ( 1, 3), ( 1, 4, 5)}
n-uniform
E内の各集合がちょうどn頂点を含む。

超グラフHが性質Bをもつ。
頂点集合Vの要素を２色に塗り分けたときに、
E内に同色の頂点のみを要素とする集合が
存在しない。

Hypergraph （超グラフ）
V : 頂点集合
E : 頂点集合の部分集合族

例
V : { 1, 2, 3, 4, 5}
E : { ( 1, 2, 4), ( 2, 3, 4), ( 1, 3, 4), ( 1, 4, 5)}

m(n) : 性質Bをもたないようなn-uniformな
超グラフの枝の最小可能数。

定理1.3.1
n-1
全ての枝の数が2 よりも少ないn-uniform
な超グラフは性質Bをもつ。
n-1
つまり、m(n)≧2
証明
n-1

H(V,E) : n-uniform かつ枝数が2 よりも
少ない超グラフ。

Vの要素をランダムに２色で塗り分ける。
証明

各枝において、Aeを枝が単色となる事象
とおく。
1 n
Pr( Ae ) 2
よって、
Pr(  Ae )   Pr( Ae )  1
eE
eE
事象Aeが起こらない確率が存在する。
n-1
m(n) ≧ 2
Upper Bound for m(n)

定理1.3.2
e ln 2 2 n
m(n)  (1  o(1))
n 2
4
Upper bound for m(n)




V : v個の要素（頂点）
χ : v個のうちa個を１つの色で塗り、
b (= v-a)個をもう１つの色で塗る。
S : Vの部分集合でn個の要素をもつ。（枝）
Cχ : χの塗り方をしたときに、Sの要素が全
て同一色になる事象
a  b
 n n
Pr(C  )     
v
n
 
証明
a  b
 n n




Pr(C  ) 
v
n
 
 y
n
 
Vを偶数とする。
が凸関数なので、
上式はa=b=v/2のときに最小
 v / 2   v / 2
 n   n 




Pr(C  ) 

v
n
 
2 v / 2 
 n  p
v
n
 
証明


S1,S2,…,Sm : Vの部分集合でn個の要素を
もつ。（枝集合）
Aχ : χの塗り方をしたときに、 S1,S2,…,Sm の
どの集合も要素全てが同一色で塗られて
いない事象。
Pr( A )  (1  p)
m
証明

v
色の塗り方は全部で2 通り
Pr( A )  2 (1  p)
v


m
上式の値を１より小さくすれば、
S1,S2,…,Sm の集合（枝集合）のどれかは
同一色で塗られた要素のみが存在している。
⇒ m(n) ≦ m
証明

 v ln 2 
前スライド式で、m  
とすると、

 p 
2 (1  p)  2 e
v

m
v
 pm
1
次にv/pを最小化することを考える。
証明
2 v / 2 
n 1
n
v  2i


1 n
1 n  n 2 / 2 v
p
2 
~2 e
v
i 0 v  i
n
 

v  n
3/ 2
の条件の間は、
v  2i
i
i
 1   O( 2 )  e
v i
v
v
2

あとは v  n 2 / 2 をとる。
i
i2
 O ( 2 )
v
v
(k,l)-system
F  {( Ai , Bi )}
h
i 1

を任意の集合の部分
集合の対の族とする。

F が (k, l)-system
| Ai | k , | Bi | l
Ai  Bi  　(all i 1
 i  h)
Ai  B j  　(all distinct i, j 1  i, j  h)

定理1.3.3
F  {( Ai , Bi )}
h
i 1
k

l


h

k


が (k,l)-systemのとき、
(3,2)-system
{
{
{
{
{
{1,2},
{1,4},
{2,3},
{2,5},
{3,5},
{3,4,5}
{2,3,5}
{1,4,5}
{1,3,4}
{1,2,4}
},
},
},
},
},
{
{
{
{
{
{1,3},
{1,5},
{2,4},
{3,4},
{4,5},
{2,4,5} }
{2,3,4} }
{1,3,5} }
{1,2,5} }
{1,2,3} }
証明
h

X   ( Ai  Bi )
とおき、ランダムなXの
i 1
順序πを考える

Xiを順序π上でAiの要素がすべてBiの要
素の前にくる事象とする。
k

l


Pr( X i )  1 

 l 

事象Xiは同時におこりえない。

もし、そうでないと仮定して、
πをAiの全ての要素がBiの前に、
Ajの全ての要素がBjの前に現れるような
順序を与えるものとする。

Aiの最後の要素がAjの最後の要素よりも
後に現れることはないとしても一般性を
失わない。
Ai
Aj
Bi
Bj

よって、
k

l

 1
Pr( X i )   Pr( X i )  h 1 

l


i 1
i 0
h
h
1.4 CONBINATORIAL NUMBER THEORY

アーベル群の集合の部分集合をＡとする。

Aがsum-freeとは、(A+A)∩A=φ
（＊） a1+a2=a3となるような、
a1,a2,a3∈Aが存在しない。
定理1.4.1
0でないn個の整数を要素としてもつ
全ての集合B={b1,…,bn}はサイズ
|A| > n/3 を満たすsum-freeな部分集合A
を含む。

証明
pをp>2max|bi|を満たすp=3k+2の素数と
する。
 C={k+1,k+2,…,2k+1}のk+1個の要素を
もつ集合とする。
⇒ Cは巡回群Zp(pの剰余環)のsum-freeな
部分集合

|C |
k 1 1


p  1 3k  1 3
証明
一様分布{1,2,…,p-1}から整数x
をランダムに選ぶ。
 d1,d2,…,dn を di≡xbi (mod p) と定義。

(＊) xが1,2,…,p-1の全ての値をとりうるので、
diはZpに含まれる全ての値をとりうる。
|C |
1
Pr( d i  C ) 

p 1 3
(*)







xとdiが１対１に対応してないと仮定する。
xbi ≡ x’bi (mod p) となる x, x’が存在。
つまり、 (x-x’)bi = pk とおける。
biはpと互いに素なので、x-x’がpの倍数になる。
よって、x ≡ x’ (mod p)
今だと、x = x’ となるので矛盾。
よって、xとdiは１対１に対応している。
証明
一様分布{1,2,…,p-1}から整数x
をランダムに選ぶ。
 d1,d2,…,dn を di≡xbi (mod p) と定義。

(＊) xが1,2,…,p-1の全ての値をとりうるので、
diはZpに含まれる全ての値をとりうる。
|C |
1
Pr( d i  C ) 

p 1 3
証明

前スライドより、diが集合Ｃに含まれるよ
うな要素biの個数はn/3より大きい。

よって、定理をみたす部分集合|A|が
存在する。
1.5 DISJOINT PAIRS


F : X={1,2,…,n}のm個の異なる部分集合
d(F) : Fの中でdisjointな対の数。
d (Ｆ ) | {( F , F ' ) : F , F 'Ｆ , F  F '  } |

定理1.5.1
(1/2+δ)
FをX={1,2,…,n}のm=2
個(δ>0)の
異なる部分集合の族とするとき、
d (Ｆ )  m
2 2 / 2
証明



定理の式が誤ってると仮定する。
Ｆからt個の集合をランダムに取り出す。
tは十分に大きな正の数とする。
証明の概要
① |A1∪A2∪…∪At| > n/2 となる確率が
正であることを示す。
n/2
② 上の集合がＸの2 個より多くの異なる
補集合とdisjointであることを示す。
①、②の矛盾より定理を証明。
証明
Pr(| A1  A2  ...  At | n / 2)
 S  X ,|S |n / 2 Pr( Ai  S , i  1,..., t )
 2 (2
n
n/2
/2
((1 / 2 )  ) n t
) 2
n (1t )

v(B)=|{A∈Ｆ : B∩A=φ| と定義すると、
 v( B)  2d (F)  2m
2  2 / 2
BＦ
V(B)はAとdisjointな集合の数で、
d(F)はdisjointとなっている対の数に
なっているので、v(B)はd(F)の２倍に
なる。

Yを全てのAiの要素とdisjointである集合
B∈Ｆの数の値をとるランダムな変数とする。
t

v
(
B
)
1

t

E (Y )   (v( B ) / m)  t  m

m
m
BＦ

t
1
 2d (F) 
1 t 2 / 2
 t  m
  2m
m
 m 





Y≦mより、
1t 2 / 2
Pr(Y  m

)m
 t 2 / 2
あとは、
t  1  1 /  , m
1t 2 / 2
とすれば、証明終了。
2
n/2

Download Report