7
大学数学基礎解説
文献あり

Lovász local lemma

1514
0

組合せ論の分野には良い性質を満たすものの存在を確率論を用いて証明する確率論的手法(probabilistic method)が知られています. 本記事では確率論的手法における非常に有名なLovász local lemmaについて紹介します.

謝辞

本記事においてU.M.さんに有益なコメントを頂いたことをこの場を借りて御礼申し上げます。

確率論的手法

確率論的手法は主に, 良い性質を満たすものの存在性を証明するために使われます. 具体的には, ランダムに構成したものが所望の性質を正の確率で満たすことが言えれば存在性を示せたことになります. nNに対し[n]={1,,n}とします.

例1. グラフの最大カット

無向グラフG=(V,E)の頂点部分集合S,TVに対し, E(S,T)S-T間のカット辺の集合とします. すなわちE(S,T)={{u,v}E:uS,tT}. 集合E(S,VS)を, 頂点集合Sに対するカット辺と呼びます.

与えられた無向グラフG=(V,E)に対して|E(S,VS)|を最大にするSを求める計算問題を最大カット問題といいます. この問題はNP困難であることが知られており, 多項式時間で最適解を得ることは不可能であると広く信じられています.

明らかに任意のSに対し|E(S,VS)||E|ですが, 一方で|E(S,VS)||E|/2を満たすSは必ず存在します.

任意のグラフG=(V,E)に対し, |E(S,VS)|0.5|E|を満たすSVが存在する.

各頂点に対し, 確率1/2で表が出るコインを投げ, 表が出た頂点の集合をSとする. このとき
E[|E(S,VS)|]=eEPr[eE(S,VS)]=|E|2.
期待値以上のサイズを持つカットは必ず存在するので, 主張は示された.

命題1はタイトで, 任意のϵ>0とどのようなSに対しても|E(S,VS)|(0.5+ϵ)|E|となるグラフが存在します. 例えば, 偶数nに対し完全グラフKn|S|=n/2の時に|E(S,VS)が最大になり, そのときは|E(S,VS)|=n2/4となります. 一方で|E|=(n2)=n(n1)/2なので, nを十分大きくとればよいです.

PNPの仮定の下では最大カット問題は最適解を多項式時間で計算できませんが, 上の議論より最適解の半分以上の個数の辺を持つカットはコインを投げるだけで簡単に得ることができます. これは0.5近似解と呼ばれてます. 実はそれよりも良い約0.878近似解を多項式時間で得る方法が知られています.

例2. ラムゼー数の下界

非常に有名な次の問題を考えてみます:

6人集まったとき, 知り合い同士の3人かもしくは互いに知らない3人が必ず存在する.

この問題はグラフで表現すると, 以下のようになります:

頂点数6の完全グラフK6の各辺を赤もしくは青で塗り分ける. このとき, 赤いK3(全ての辺が赤で塗られているK3)もしくは青いK3が必ず存在する.

この問題を一般化し次の値R(k,l)を考えます:

ラムゼー数

次の性質を満たす最小のnR(k,l)とし, ラムゼー数と呼ぶ:
頂点数nの完全グラフKnの各辺を赤もしくは青で塗り分ける. このとき, 赤いKkもしくは青いKlが必ず存在する.

数学者のFrank P. Ramsey(1903-1930)はR(k,l)が有限であることを証明しました (ラムゼーの定理). ラムゼー数R(k,l)は組合せ論において非常に多くの研究がなされているほど有名なトピックです.

ここでは, 確率論的手法を使ってラムゼー数の下界を簡単に導出することができることを紹介します.

n,kN
(nk)21(k2)<1
を満たすならば, R(k,k)>n.

条件を満たすk,nを固定し, 頂点数nの完全グラフKnを考える. Knの各辺を一様ランダムに赤または青で塗り分ける. Xを同色のKk(赤いKkまたは青いKk)の個数とする. 固定した一つのKkが同色になる確率は21(k2)であり, Knの中から一つのKkを選ぶのは(nk)通りあるので, k,nの条件より
E[X]=(nk)21(k2)<1.
期待値E[X]<1より必ずPr[X=0]>0となる. この確率が正ということは, 上手く塗り分けることによって同色のKkが存在しないようにできる. これはR(k,k)>nを意味する.

例3. ハイパーグラフの2彩色

有限集合Vに対し(Vk)={SV:|S|=k}とします. E(V2)に対して組G=(V,E)をグラフと呼びますが, これを一般化して頂点部分集合族F2Vに対してH=(V,F)ハイパーグラフと呼び, 特にF(Vk)ならばH=(V,F)k一様ハイパーグラフと呼びます. Vの元を頂点, Fの元をハイパー辺と呼びます. 特に, 2一様ハイパーグラフはグラフと一致します.

次にハイパーグラフの彩色の概念を導入します.

ハイパーグラフのk-彩色

ハイパーグラフH=(V,F)に対し, c:V[k]が次の条件を満たすとき, Hk-彩色という. 全てのハイパー辺eFに対し, ある2頂点a,beが存在しc(a)c(b).

次の結果は, 一様ハイパーグラフに対し2-彩色の存在性を主張します.

H=(V,E)k一様ハイパーグラフとする. |E|<2k1ならばH2-彩色を持つ.

k一様ハイパーグラフH=(V,F)を考える.
c:V[2]をランダムな関数とする. すなわち, 各頂点vVに対しc(v)=1またはc(v)=2を確率1/2で決める. ある固定したハイパー辺eFが全て同じ色で塗られる(すなわち, あるc[2]が存在して全てのaec(a)=c)確率は21kとなる. 同じ色で塗られたハイパー辺の個数をXとすると, その期待値はE[X]=|E|21k. |E|<2k1のとき, この期待値は1未満なので, 特にPr[X=0]>0となる. すなわちHは2-彩色を持つ.

Lovász local lemma

Lovász local lemmaを紹介します. Lovász local lemmaは, n個の事象A1,,Anに対しPr[A1An]の下界を与える結果です. つまり, n個の起こって欲しくない事象が一つも起こらない確率を評価しています. もしA1,,Anが独立な事象ならば当然この確率はi[n]Pr[Ai]となりますが, Lovász local lemmaでは必ずしも独立とは限らない事象A1,,Anを扱います.

主張を述べるために幾つか用語を準備します.

有向グラフ

有限集合Vに対し, (V)2={(i,j):i,jV,ij}とし, その部分集合E(V)2に対し組G=(V,E)を有向グラフという. グラフG=(V,E)の頂点iVに対し, N+(v)={jV:(i,j)E}とする.

グラフ理論の文脈では有向グラフを考えるときは自己ループや多重辺を考えることもありますが, ここではそれらのないものを有向グラフとしています.

相互に独立

事象Eが事象A1,,An相互に独立(mutually independent)であるとは, 任意のS[n]に対し
Pr[EiSAi]=Pr[E]Pr[iSAi]
が成り立つことをいう.

複数の事象A1,,Anの独立性を表す従属グラフを考えます.

従属グラフ

事象A1,,Anに対し, 以下を満たす有向グラフG=(V,E)従属グラフという.

  • V=[n].
  • 各頂点iに対し, 事象Aiは事象(Aj)jV({i}N+(i))と相互に独立.

一般に従属グラフはA1,,Anから一意に定まるわけではないことに注意してください.

事象A1,,Anが独立ならば, 空グラフG=([n],)は従属グラフになる.

どんな事象A1,,Anに対しても, 完全グラフ([n],([n])2)は従属グラフになる.

Lovász local lemma

事象A1,,Anの従属グラフを一つ任意に選びGとする. さらに, ある(x1,,xn)[0,1]nが存在して次を満たすとする: 全てのi[n]に対しPr[Ai]xijN+(i)(1xi). このとき,
Pr[i[n]Ai]i[n](1xi).

事象A1,,Anを考える. 各AiA1,,Anのうち高々d個を除いた全てと相互に独立とする. 更に, Pr[Ai]pとする. このとき, ep(d+1)<1ならばPr[i[n]Ai]>0. ここでe=2.7182はネイピア数.

条件を満たすA1,,Anに対してはある従属グラフGが存在して全ての頂点の出次数を高々dにできる. すなわち各i[v]|N+(i)|d. xi=1/(d+1)とおき, p<1e(d+1)とすれば定理4の条件を満たす. 実際,
p<1e(d+1)1d+1jN+(i)(11d+1)
である(ここで, 任意のd1に対し(11/(d+1))d>1/eが成り立つことを使った).
このとき, 定理4より
Pr[i[n]Ai](11d+1)n>0.

以降では, Lovász local lemmaを適用して色んな結果を証明していきます. カギとなるのは, 従属グラフをどう構成するか, そのために事象A1,,Anをどう定義するかです. 基本的には定理4系を適用します. そのためには, できるだけ出次数の小さい従属グラフを考えていきます.

適用例1. ハイパーグラフの彩色

例3で考えたハイパーグラフの彩色を考えます. ハイパーグラフH=(V,F)の頂点vV次数deg(v)を, vを含むハイパー辺の個数で定める. すなわちdeg(v)=|{eF:ve}|とする. H最大次数maxvVdeg(v)で定義する.

最大次数が高々dk一様ハイパーグラフH=(V,F)を考える. d<(2k1/e1)/kならばHは2彩色を持つ.

c:V[2]をランダムな関数とする. 各ハイパー辺eFに対し, ecの下で単色になる(すなわち, あるi[2]が存在し全ての頂点aec(a)=iとなる)事象Aeとする. このとき, cが2-彩色になることとeFAeが成り立つことは等価であるため, Pr[eFAe]>0を示せば良い.

ハイパー辺eFを一つ固定する. もし別の辺fFef=ならば, 二つの事象AeAfは独立である. 同様に, f1,,fmFが全てefi=となるならば, AeAf1,,Afmは相互に独立である.

そこで, eと共通部分を持つ辺の個数を考える. Hk一様だからeはちょうどk個の頂点を持ち, 最大次数の条件から各頂点veは高々d個の辺に含まれている. すなわち, eと共通部分を持つ辺は高々kd個となり, Aekd個を除いた全ての事象と相互に独立となる.

更に, どの辺に対してもAe=21kである. 次数dの条件よりe21k(kd+1)<1なので, 定理4系より所望の主張Pr[eFAe]>0が得られる.

適用例2. CSPの充足可能解

CSP(constraint satisfaction problem)とは, 大雑把にいうと離散値をとる変数に関する連立方程式を解けという問題です. ある種のCSPは必ず方程式の解を持つということをLovász local lemmaを使って証明することができます.

Σを有限集合, x1,,xnを変数, C1,,Cmを関数とし, 各CiCi:Σn{true,false}であって, インデックス集合Si[n]に対しCi(xj)jSiに依存するものとします. CSPは, 全てのi[m]に対しCi(x)=trueとなるようなxΣnが存在するかどうかを判定する計算問題です. そのようなxが存在するとき, そのx(C1,,Cm)充足解と呼び, 特に充足解を持つとき(C1,,Cm)充足可能という.

例えば, n=5, Σ={0,1}, S1={1,2,3}, S2={2,3,4}, S3={3,4,5}とし, 各Ciを方程式
jSixj=1mod2
とします. つまり, (x1,,xn){0,1}nがこの方程式を満たすならばCi(x1,,xn)=trueで, そうでないならCi(x1,,xn)=falseです. これはx1==x5=1は充足解の一つです.

Siに対し, SiSjとなるjが高々d個あるとする. また, x=(x1,,xn)のそれぞれに独立にΣから一様ランダムに選んだ値を代入したとき, Pr[Ci(x)=false]pであるとする. このとき, もしep(d+1)<1ならば, (C1,,Cm)は充足可能である.

xjにそれぞれ独立にΣから一様ランダムに値を代入してx=(x1,,xn)とする. xが充足解になる確率を考える. 各i[m]に対し, AiCi(x)=falseとなる事象とする. このとき, xが充足解になる確率はPr[i[n]Ai]と等しい.

事象Aiは, SiSj=なるjに対するAjと独立である(代入するランダム割り当ての変数が互いに素であるため). 従って定理4系より, Pr[i[n]Ai]>0である.

このように, 各Ciによって定められる局所的な制約から充足可能解の存在性という大域的な情報を得られるのが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]を読んでみてください.

参考文献

[1]
N. Alon and J. H. Spencer, The Probabilistic Method, Wiley
投稿日:2021224
OptHub AI Competition

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。
バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

投稿者

knewknowl
knewknowl
22
5930
東工大助教. 理論計算機科学.

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中
  1. 謝辞
  2. 確率論的手法
  3. 例1. グラフの最大カット
  4. 例2. ラムゼー数の下界
  5. 例3. ハイパーグラフの2彩色
  6. Lovász local lemma
  7. 適用例1. ハイパーグラフの彩色
  8. 適用例2. CSPの充足可能解
  9. まとめ
  10. 参考文献