Probabilistic method 輪講 第7回 2007年7月4日(水) 岩間研究室 M2 門下 雅一

5章 The Local Lemma 1節 The Lemma 2節　Property B and Multicolored Set of Real Numbers 3節 Lower Bonds for Ramsey Numbers 4節 A Geometric Result 5節 The Linear Arboricity of Graphs

復習 確率を用いた証明論法の典型 実は確率が大きいということも(証明の中で)得られる 事象Xの生起確率が正であることを示す。 e. g. 性質Skを持つトーナメント(第1章) 完全グラフの枝に向きを付与する。 性質Sk : 任意にk個の頂点を選んだとき、それらすべての頂点に枝が出ている頂点が存在する。 kに対してnが十分大きくなるとほとんどすべての枝のむき付けに対して、性質を満たす。 S1を満たす例

独立性・希薄依存性 (independence and rare dependence) 逆に、事象の生起確率が正ではあるが非常に小さいことを示す場合もある。 特にn個の互いに独立な事象の確率が少なくともp(>0)であるとき n個のすべてが同時に起きる事象の確率はpn以上 確率は正ではあるが、nに関して指数関数的に小さくなる 互いに独立ではないが、ほとんど依存しない事象でも上のような性質と似た性質があるのではないか? これから用いたい論法 証明したい性質を持つ事象が、n個の互いに独立ではない事象が同時に起きると表現される。 確率は小さいけれど、正である。よって証明したい性質の存在が証明できる。

Lovasz Local Lemma Lemma 5.1.1 A1,　A2 , …,Anを任意の確率空間上の事象とする.n個の頂点V={1,2,…,n}を持つ有向グラフD=(V,E)で、任意の にたいして事象Aiが事象　　　　　　　と互いに独立であるとき、そのような有向グラフを依存有向グラフと呼ぶ。いま、上で示した事象上の依存有向グラフD=(V,E)と、n個の実数　　　　　　　　　　　　が存在し、任意の について を満たすならば 特に、事象Aiがすべて起きない確率が正である。

依存有向グラフD=(V,E) 事象の対が互いに独立であるか否かという情報を保持する 対称に有向枝を持つ 互いに独立

Lovasz Local Lemma(再掲) A1,　A2 , …,Anを任意の確率空間上の事象とする.n個の頂点V={1,2,…,n}を持つ有向グラフD=(V,E)で、任意の にたいして事象Aiが事象　　　　　　　と互いに独立であるとき、そのような有向グラフを依存有向グラフと呼ぶ。いま、上で示した事象上の依存有向グラフD=(V,E)と、n個の実数　　　　　　　　　　　　が存在し、任意の について を満たすならば 特に、事象Aiがすべて起きない確率が正である。

条件付確率の基本 基本的事項の復習 事象AとBが互いに独立 条件付確率 余事象の確率

実数xの役割 [補題5.1.1の証明] はじめに任意の部分集合S⊂{1,2,…,n}, |S|=s<n,と任意の について(5.1)式 　を示す。 数学的帰納法 s=0のとき

補題5.1.1の証明[1] s’<sなるすべてのs’で　　　　　　　が成立すると仮定する。　　　　　　　　　　　　　　　　　　と置く。 D=(V,E) i ｌ ｊ S2 S1

補題5.1.1の証明[2] 帰納法の仮定を 使う よって、任意の真部分集合S⊂{1,2,…,n}, |S|=s<n,と任意の 　について(5.1)式

補題5.1.1の証明[3] 証明のラストも簡単 　[証明終]

The local lemma ; symmetric case 系5.1.2 A1,　A2 , …,Anを任意の確率空間上の事象とする.どの事象Aiも、それと互いに独立でない事象Ajの個数がd個以下であるとする。事象Aiの起きる確率がp以下であるとする。条件式 を満たすならば 系5.1.2の証明 d=0のときはAi とAiはすべて互いに独立であるので、自明。 その他の場合、事象上の依存有向グラフで、任意のiについて 　　　　　　　　　　　　　を満たすものが存在する 補題5.1.1で と置くと

性質Bを持つハイパーグラフ ハイパーグラフH=(V,E)が性質Bを持つ 定理5.2.1 証明 頂点の２彩色で任意の枝fについてfに含まれる頂点が単一の色で塗られていない 定理5.2.1 ハイパーグラフH=(V,E)はどんな枝もk個以下の頂点を含むとする。Hのどんな枝も多くともd本の枝と交差(intersect)しているとする。このとき ならばHは性質Bを持つ。 証明 頂点vを無作為に独立に赤・青に塗る。任意の枝fについて、Afを枝fが1色で塗られているという事象とする。事象Afが起きる確率を計算すると、 f と異なる枝でｆ と交差していない枝f’ に関する同様の事象Af’ は事象Af と互いに独立である。 よって系5.1.2をそのまま用いることにより、どの枝も単一で塗られていない確率は正である。[証明終]

定理5.2.1の特殊な場合 注意 なるk-uniform k-regularハイパーグラフHはいつも性質Bを持つ。 枝 f は高々d=k(k-1)本の枝と交差する。

実数のk-彩色 定義 定理5.2.2 実数に色{1,2,…,k}のうちひとつを割り当てる 実数の部分集合T⊂RでTに割り当てられた色の集合をc(T)と書く。c(T)={1,2,…k}であるとき、Tは全彩色されたという 定理5.2.2 m ,k を正の整数とする。条件式 　　を満たすとき、m個の実数からなる任意の集合Sにたいして、任意の置換x+S (x∈R)が全彩色になるような実数のk-彩色が存在する 特に　　　　　　　　　　　　のとき、いつも条件式を満たす。

定理5.2.2の証明[1] [定理5.2.2の証明] はじめに実数の有限集合X⊂Rを固定する。任意の置換x+S (x∈X)が全彩色になるような実数k-彩色が存在することを示す。 y∈Yをランダムに選び、c(y)を{1,2,…,k}の一様分布に従って塗る。 Axをx+Sは全彩色でないという事象とする。 高々m(m-1)通り 補題5.1.2のd,pにそれぞれ代入。

定理5.2.2の証明[2] 証明したい命題は実数xを制限しないバージョン 位相数学のはなし コンパクトという概念を使う 位相空間Xの部分集合Kにたいして、任意のKの開被覆が、有限部分被覆を持つとき、Kがコンパクトであるという。 k個の点上の離散空間はコンパクトであるから、ティコノフの定理によりそういう空間の任意の直積もコンパクトである。 特に、関数R→{1,2,…,k}全体がなす空間も、通常の直積位相を用いることによりコンパクトである。 このような空間では、任意の固定したx∈Rに対して、彩色の集合Cxで、x+Sが全彩色である集合は閉集合となる。 実は開集合でもあり閉集合でもある。なぜならば開集合へのある基は、有限個の場所の個数で定められた彩色をすべて集めた彩色の集合だから。

定理5.2.2の証明[3] 無限個の事象を補題に適用しても、一般にはうまくいかない 集合Cxの有限個の族の共通集合は空集合でない。 定理5.2.2の証明[1]のスライド このような性質を有限交叉性と呼ぶ コンパクト性より、すべての集合Cxの共通集合C(0)は空集合でない。 すべての彩色を集めた集合Cがコンパクト Cの部分集合の族が有限交叉性を持つ この共通集合C(0)に含まれる任意の彩色は、定理5.2.2の結論で述べられている性質を満たす。[証明終] 無限個の事象を補題に適用しても、一般にはうまくいかない 加算的に多くの独立した事象Aiで、　　　　　　　　　　　 　を満たす例が存在する。 そういうわけで、コンパクトを用いた論法が上の証明では必要になる。