組合せ論の分野には良い性質を満たすものの存在を確率論を用いて証明する確率論的手法(probabilistic method)が知られています. 本記事では確率論的手法における非常に有名なLovász local lemmaについて紹介します.
謝辞
本記事においてU.M.さんに有益なコメントを頂いたことをこの場を借りて御礼申し上げます。
確率論的手法
確率論的手法は主に, 良い性質を満たすものの存在性を証明するために使われます. 具体的には, ランダムに構成したものが所望の性質を正の確率で満たすことが言えれば存在性を示せたことになります. に対しとします.
例1. グラフの最大カット
無向グラフの頂点部分集合に対し, を-間のカット辺の集合とします. すなわち. 集合を, 頂点集合に対するカット辺と呼びます.
与えられた無向グラフに対してを最大にするを求める計算問題を最大カット問題といいます. この問題はNP困難であることが知られており, 多項式時間で最適解を得ることは不可能であると広く信じられています.
明らかに任意のに対しですが, 一方でを満たすは必ず存在します.
各頂点に対し, 確率1/2で表が出るコインを投げ, 表が出た頂点の集合をとする. このとき
期待値以上のサイズを持つカットは必ず存在するので, 主張は示された.
命題1はタイトで, 任意のとどのようなに対してもとなるグラフが存在します. 例えば, 偶数に対し完全グラフはの時にが最大になり, そのときはとなります. 一方でなので, を十分大きくとればよいです.
の仮定の下では最大カット問題は最適解を多項式時間で計算できませんが, 上の議論より最適解の半分以上の個数の辺を持つカットはコインを投げるだけで簡単に得ることができます. これは近似解と呼ばれてます. 実はそれよりも良い約近似解を多項式時間で得る方法が知られています.
例2. ラムゼー数の下界
非常に有名な次の問題を考えてみます:
6人集まったとき, 知り合い同士の3人かもしくは互いに知らない3人が必ず存在する.
この問題はグラフで表現すると, 以下のようになります:
頂点数の完全グラフの各辺を赤もしくは青で塗り分ける. このとき, 赤い(全ての辺が赤で塗られている)もしくは青いが必ず存在する.
この問題を一般化し次の値を考えます:
ラムゼー数
次の性質を満たす最小のをとし, ラムゼー数と呼ぶ:
頂点数の完全グラフの各辺を赤もしくは青で塗り分ける. このとき, 赤いもしくは青いが必ず存在する.
数学者のFrank P. Ramsey(1903-1930)はが有限であることを証明しました (ラムゼーの定理). ラムゼー数は組合せ論において非常に多くの研究がなされているほど有名なトピックです.
ここでは, 確率論的手法を使ってラムゼー数の下界を簡単に導出することができることを紹介します.
条件を満たすを固定し, 頂点数の完全グラフを考える. の各辺を一様ランダムに赤または青で塗り分ける. を同色の(赤いまたは青い)の個数とする. 固定した一つのが同色になる確率はであり, の中から一つのを選ぶのは通りあるので, の条件より
.
期待値より必ずとなる. この確率が正ということは, 上手く塗り分けることによって同色のが存在しないようにできる. これはを意味する.
例3. ハイパーグラフの2彩色
有限集合に対しとします. に対して組をグラフと呼びますが, これを一般化して頂点部分集合族に対してをハイパーグラフと呼び, 特にならばを一様ハイパーグラフと呼びます. の元を頂点, の元をハイパー辺と呼びます. 特に, 一様ハイパーグラフはグラフと一致します.
次にハイパーグラフの彩色の概念を導入します.
ハイパーグラフの-彩色
ハイパーグラフに対し, が次の条件を満たすとき, の-彩色という. 全てのハイパー辺に対し, ある2頂点が存在し.
次の結果は, 一様ハイパーグラフに対し-彩色の存在性を主張します.
を一様ハイパーグラフとする. ならばは-彩色を持つ.
一様ハイパーグラフを考える.
をランダムな関数とする. すなわち, 各頂点に対しまたはを確率で決める. ある固定したハイパー辺が全て同じ色で塗られる(すなわち, あるが存在して全てので)確率はとなる. 同じ色で塗られたハイパー辺の個数をとすると, その期待値は. のとき, この期待値は未満なので, 特にとなる. すなわちは2-彩色を持つ.
Lovász local lemma
Lovász local lemmaを紹介します. Lovász local lemmaは, 個の事象に対しの下界を与える結果です. つまり, 個の起こって欲しくない事象が一つも起こらない確率を評価しています. もしが独立な事象ならば当然この確率はとなりますが, Lovász local lemmaでは必ずしも独立とは限らない事象を扱います.
主張を述べるために幾つか用語を準備します.
有向グラフ
有限集合に対し, とし, その部分集合に対し組を有向グラフという. グラフの頂点に対し, とする.
グラフ理論の文脈では有向グラフを考えるときは自己ループや多重辺を考えることもありますが, ここではそれらのないものを有向グラフとしています.
相互に独立
事象が事象と相互に独立(mutually independent)であるとは, 任意のに対し
が成り立つことをいう.
複数の事象の独立性を表す従属グラフを考えます.
従属グラフ
事象に対し, 以下を満たす有向グラフを従属グラフという.
一般に従属グラフはから一意に定まるわけではないことに注意してください.
どんな事象に対しても, 完全グラフは従属グラフになる.
Lovász local lemma
事象の従属グラフを一つ任意に選びとする. さらに, あるが存在して次を満たすとする: 全てのに対し. このとき,
事象を考える. 各はのうち高々個を除いた全てと相互に独立とする. 更に, とする. このとき, ならば. ここではネイピア数.
条件を満たすに対してはある従属グラフが存在して全ての頂点の出次数を高々にできる. すなわち各で. とおき, とすれば定理4の条件を満たす. 実際,
である(ここで, 任意のに対しが成り立つことを使った).
このとき, 定理4より
以降では, Lovász local lemmaを適用して色んな結果を証明していきます. カギとなるのは, 従属グラフをどう構成するか, そのために事象をどう定義するかです. 基本的には定理4系を適用します. そのためには, できるだけ出次数の小さい従属グラフを考えていきます.
適用例1. ハイパーグラフの彩色
例3で考えたハイパーグラフの彩色を考えます. ハイパーグラフの頂点の次数を, を含むハイパー辺の個数で定める. すなわちとする. の最大次数をで定義する.
最大次数が高々の一様ハイパーグラフを考える. ならばは2彩色を持つ.
をランダムな関数とする. 各ハイパー辺に対し, がの下で単色になる(すなわち, あるが存在し全ての頂点がとなる)事象とする. このとき, が2-彩色になることとが成り立つことは等価であるため, を示せば良い.
ハイパー辺を一つ固定する. もし別の辺がならば, 二つの事象とは独立である. 同様に, が全てとなるならば, とは相互に独立である.
そこで, と共通部分を持つ辺の個数を考える. は一様だからはちょうど個の頂点を持ち, 最大次数の条件から各頂点は高々個の辺に含まれている. すなわち, と共通部分を持つ辺は高々個となり, は個を除いた全ての事象と相互に独立となる.
更に, どの辺に対してもである. 次数の条件よりなので, 定理4系より所望の主張が得られる.
適用例2. CSPの充足可能解
CSP(constraint satisfaction problem)とは, 大雑把にいうと離散値をとる変数に関する連立方程式を解けという問題です. ある種のCSPは必ず方程式の解を持つということをLovász local lemmaを使って証明することができます.
を有限集合, を変数, を関数とし, 各はであって, インデックス集合に対しはに依存するものとします. CSPは, 全てのに対しとなるようなが存在するかどうかを判定する計算問題です. そのようなが存在するとき, そのをの充足解と呼び, 特に充足解を持つときは充足可能という.
例えば, , , , , とし, 各を方程式
とします. つまり, がこの方程式を満たすならばで, そうでないならです. これはは充足解の一つです.
各に対し, となるが高々個あるとする. また, のそれぞれに独立にから一様ランダムに選んだ値を代入したとき, であるとする. このとき, もしならば, は充足可能である.
各にそれぞれ独立にから一様ランダムに値を代入してとする. が充足解になる確率を考える. 各に対し, をとなる事象とする. このとき, が充足解になる確率はと等しい.
事象は, なるに対すると独立である(代入するランダム割り当ての変数が互いに素であるため). 従って定理4系より, である.
このように, 各によって定められる局所的な制約から充足可能解の存在性という大域的な情報を得られるのがLovász "local" lemmaたる所以です.
CSPは計算量理論で最も重要な問題の一つとされるSAT(satisfiability)を特殊ケースとして含み, 一般に充足可能か否かの判定はNP完全です. 定理6では, 変数の被り具合が小さい場合は必ず充足可能であることを示しました. それでは充足解を求める効率的なアルゴリズムは存在するのでしょうか? 理論計算機科学ではこのトピックはAlgorithmic Lovász local lemmaと呼ばれており, 近年の理論計算機科学のトップの国際会議STOCやFOCSにはこのトピックの論文がいくつも採択されています.
まとめ
本記事では組合せ論における確率論的手法を簡潔に導入し, その後Lovász local lemmaを解説しました. その応用としてCSPの充足可能性などを議論し, 近年の理論計算機科学ではAlgorithmic Lovász local lemmaに関する研究がなされているなど, Lovász local lemmaの影響は組合せ論にとどまらないことをみてきました. このトピックに興味のある方は参考文献[1]を読んでみてください.