2017年7月15日土曜日

グラフが平面的であることの必要十分条件一覧

グラフ$G$を考える.
単射 $\phi:\,V\to\mathbb{R}^2$ 及びジョルダン曲線の族 $(J_e)_{e\in E}$ が存在し, 次の性質を満たすとき, $G$ は平面的であると定義します. 特に$G$が平面的グラフであるとき, 組 $(\phi,(J_e)_{e\in E})$を$G$の埋め込みと呼びます.

性質:
$G$ の各辺 $e=\{u,v\}\in E$に対し,

  • $J_e$ は 点 $\phi(u)$ と点 $\phi(v)$ を結ぶ.
  • $J_e\backslash \{\phi(u),\,\phi(v)\} \cap \left(\bigcup_{v\in V} \{\phi(v)\} \cup \bigcup_{f \in E\backslash \{e\}} J_f\right)=\emptyset$


$J\subseteq \mathbb{R}^2$ がジョルダン曲線であるとは, 適当な連続な単射 $f:[0,1]\to\mathbb{R}^2$の像として$J$が表せることを指します.

ちなみに, いわゆる「平面グラフ」という言葉は「平面に埋め込まれた」グラフを指すのであって「平面に埋め込める」グラフは指しません.

以下は全て同値です:


  • グラフ$G=(V,E)$が平面的である.
  • $G$は単純なサイクル基底 (任意の辺$e\in E$に対して$e$を含む閉路が高々2つであるようなサイクル基底)を持つ (MacLaneの定理).
  • $K_5$ 及び $K_{3,3}$ をマイナーとして含まない (Wagnerの定理).
  • $K_5$ 及び $K_{3,3}$ を位相的マイナーとして含まない (Kuratowskiの定理).
  • ある$k\in\mathbb{N}$が存在して, $G$の禁止マイナー $\mathrm{Forb}(G)$ ($G$をマイナーとして含まないような有限グラフの全体)に属する任意のグラフは木幅が高々$k$である (Seymour).
  • $G$に対応するグラフ的マトロイド$M$の双対マトロイド$M^{*}$をとったとき, これが別のグラフ$G^{*}$に対応するグラフ的マトロイドとなる (このとき$G^*$は平面的グラフの双対グラフになっている).

他にもめっちゃ色々あったはず (学んだら追加していく).


2017年7月10日月曜日

(計算が)ヤバイ級数










は有名です(前者はバーゼル問題で後者は部分分数分解で計算できます)。それでは








はどうなるのでしょうか?? 収束するのは明らかです。計算してみましょう。
(厳密な議論が欠けている箇所が幾つかあるので注意してください)

級数をグッと睨むと、





と変形出来そうな気がします。ここでおもむろにwikipediaを参照すると




と書けるらしいので($B_k$はベルヌーイ数)、元の級数は





となります。ここでおもむろにwikipediaを参照すると、




という双曲線関数の謎テイラー展開(ローラン展開)が得られるので、収束半径を無視して$x=\pi$を代入して整理すると




従って





となります。
(ちなみに数値的にもこの値は合致します)


余談


ゼータ関数は



と書ける(らしい)ので、級数に代入して、総和と積分の交換が出来ると信じて更に収束半径諸々を無視して無理やり計算すると




となります(最後の等式は$\sin$のテイラー展開です)。

従って、(多分)




が成り立ちます(多分)

2017年7月7日金曜日

古典的確率論から測度論的確率論へ (条件付き期待値)

0. 概要


条件付き確率は確率論における重要な概念あり, マルチンゲールを定義するために不可欠です. 従って測度論的確率論を勉強していくと必ずこの概念に出会いますが, その理解は非常に難解(気持ちが分かりにくい)で, 一つの大きな壁であるといえます. 本記事は
  • 測度論的確率論を勉強してみたけど条件付き期待値のキモチがいまいち分からない.
  • なんとなく言葉は知ってるけどちゃんとした定義はよく知らない.
という人向けに, 直感的な説明とちゃんとした定義を織り交ぜて条件付き期待値について解説します. 本記事は測度論的確率論の基本的な概念を前提知識として仮定します.

本記事では古典的確率論における条件付き期待値から出発して測度論的確率論における条件付き期待値を「導出」していきます. 以前の記事で少しだけ条件付き期待値について書いてあるので, 理解の助けになるかもしれません.

1. 古典的確率論における条件付き期待値


条件付き期待値とは, $\mathrm{E}[X|\mathcal{G}]$で表されるスカラー値です. 古典的確率論においては条件付き確率を定義してから条件付き期待値を定義します. つまり$A,B$をそれぞれ事象として, $\mathrm{Pr}(A|B)=\mathrm{Pr}(A\cap B)/\mathrm{Pr}(B)$と定義した後に, 条件付き期待値を



と定義します. つまり古典的確率論では条件付き期待値は確率変数と事象の組に対してスカラー値を割り当てる関数と見なしていて, $\mathrm{E}[X|B]$は(確率変数, 事象)の組を受け取ってスカラー値を返す関数になるわけです. しかし, 測度論的確率論における条件付き期待値は全然異なっています.

2. 確率変数としての条件付き期待値


測度論的確率論では確率空間を$(\Omega,\mathcal{F},P)$の三つ組として定義し, 事象とは$\mathcal{F}$の元であると考えます. また, 確率変数は$\Omega\to\mathbb{R}$の関数であると考えます. 測度論的確率論ではまず条件付き期待値を定義してから条件付き確率を定義するので, 古典的確率論とは定義の順番が逆になります. そこでまず, 条件付き期待値を定義してみることにします.

$\mathcal{B}=\{B_1,\ldots,B_K\}$を$\Omega$の分割とします. つまり各$B_i\subseteq \Omega$であり, しかも$B_i\cap B_j=\emptyset$ (for $i\neq j$) かつ$\bigcup_{i=1}^K B_i=\Omega$を仮定します. 確率変数$X$と$\Omega$の分割$\mathcal{B}$に対し, 確率変数$Y:\Omega\to\mathbb{R}$を



とします. (Fig.1) ここで$\mathrm{E}[X|B_i]$は(古典的な意味での)条件付き期待値だと思ってください. 結論から言うとこの$Y$が条件付き期待値みたいなものになっていて, 気持ちとしては$Y=\mathrm{E}[X|\mathcal{B}]$になります.

FIg.1: $Y$の定義

 イメージとしては, $Y$は確率変数$X$を, 分割$\mathcal{B}$の下で出来るだけ近似しています. $Y$は各分割$B_i$内の二つの要素が区別出来ないという制約の下で出来るだけ$X$っぽい確率変数になっています. なので, より細かい分割に対して同じように$Y$を考えると, 関数としてはより「細かい」ものになっていきます. つまり分割$\mathcal{B}'$を分割$\mathcal{B}$より細かいもの(FIg.2 参照)とすると, $\mathrm{E}[X|\mathcal{B}']$は$\mathrm{E}[X|\mathcal{B}]$よりもより良い近似になっていることが分かります.

Fig.2: $\mathcal{B}$よりも$\mathcal{B}'$の方が細かい分割になっている.


さらに, $Y(\omega)$を$B_i$内で積分すると(直感的な議論だと思って読んでください)


つまり, $\int_{B_i}YdP=\int_{B_i}XdP$ という関係が成り立ちます(この関係が重要です).


3. 測度論的確率論における条件付き期待値の定義


測度論的確率論では事象とは$\sigma$-集合体の要素です. また, 前まではdisjointな事象の集まりを考えていましたが, ここでは部分$\sigma$-集合族について考えます.

確率変数$X$と部分$\sigma$-集合体$\mathcal{G}\subseteq \mathcal{F}$に対して, 条件付き期待値$Y=E[X|\mathcal{G}]$は$\Omega\to\mathbb{R}$は確率変数であり, 以下の条件を満たすものと定義します:

  1. $Y$は$\mathcal{G}$-可測 (i.e. 任意の$a\in \mathcal{R}$に対して $\{\omega \in \Omega\,:\,Y(\omega)<a\} \in \mathcal{G}$)
  2. 任意の$A\in\mathcal{G}$に対して, $\int_A YdP = \int_A XdP$.

条件2の気持ちは上の式で説明した通りです. 条件1は「近似」の制約の強さを規定しています. つまり「$\mathcal{G}$-可測である」という制約条件の中で$X$を近似したとき, もっともよく近似出来ている確率変数が$Y=\mathrm{E}[X|\mathcal{G}]$であると解釈します. なぜ条件1が制約条件を表すのかについては以前の記事や後に出てくる例を見ると分かり易いと思うので, 後ほど取り上げます.

そもそも本当に条件1,2を満たす$Y$が存在するのかについてですが, ラドン=ニコディムの定理からalmost everywhereの意味で一意に定まります.

ここではラドン=ニコディムの定理を用いず, 有限加法族$\mathcal{G}$に対して条件付き期待値$Y=\mathrm{E}[X|\mathcal{G}]$をちゃんと構成してみます. すると条件付き期待値について何か掴めるようになると思います. まず有限加法族$\mathcal{G}\subseteq 2^{\Omega}$に対し, 以前の記事で述べた$\Omega$の「都合の良い」分割$\mathcal{B}=\{B_1,\ldots,B_k\}$をとってきます (存在性も証明してあります).
この$\mathcal{B}$に対して1節で考えた$Y$を考えます. すると実は$Y=\mathrm{E}[X|\mathcal{G}]$となることが示せます.



つまり, 有限加法族 $\mathcal{G}$ に対しては条件付き期待値$\mathrm{E}[X|\mathcal{G}]$を1節で説明した方法によって具体的に構成することが出来るようになりました.

また, 条件付き確率$\mathrm{Pr}(A|\mathcal{G})$は, 事象$A$の指示関数$1_A$を用いて



と定義されます.

4. 例 (命題論理式)


SAT(充足可能性判定)問題では命題論理式がCNF形式で与えられます. このとき「充足されるクローズの個数が最大となるような」割り当てを求めるという最大化問題を考えることができます. 例として次の論理式$\phi$を考えます.



また, 各節(clause)$C_j$を



とおきます.

$(x_1,x_2,x_3,x_4)$にそれぞれ等確率に $0$ or $1$ を割り当てると,

$\mathrm{Pr}(C_j$ が充足される$)=1-(0.5)^3$

となり, 確率変数 $X$ を「充足された節の個数」と定義すると, $\mathrm{E}[X]=3-3\cdot (0.5)^3=2.625$ となるはずです. ここで確率空間 $\Omega$ は $\{0,1\}^3$ で, $\sigma$ -集合体 $\mathcal{F}$ は $2^{\Omega}$ とします.

ここで, 4回の(公平なコインによる)コイントスによって$x_1,x_2,x_3,x_4$の割り当てがこの順にランダムに決まっていく過程を考えます.

・$x_1$の値が決定したとき:


$(x_1,x_2,x_3,x_4)$の割り当ては $(x_1,*,*,*)$ となります($*$はランダムビット). 従って事象としては$\{(x_1,r_2,r_3,r_4)\,:\,r_2,r_3,r_4\in \{0,1\}\}\in \mathcal{F}$が発生したことになります. そこでこの事象を含む最小の$\sigma$-集合体 $\mathcal{G}_1$ を考えます. $\mathcal{G}_1$は補集合で閉じていなければならないので

$\mathcal{G}_1=\{ \emptyset, (0,*,*,*), (1,*,*,*), (*,*,*,*)=\Omega \}$

となります. ここで$Y_1=\mathrm{E}[X|\mathcal{G}_1]$を考えましょう. 3節で説明した方法により, 次のように$Y_1$を具体的に構成できます: $\mathcal{G}_1$の「都合の良い」分割として$\mathcal{B}=\{(0,*,*,*),(1,*,*,*)\}$ をとります. これはちゃんと都合の良い分割になっています. ここで$\mathrm{E}[X|(0,*,*,*)],\,\mathrm{E}[X|(1,*,*,*)]$をそれぞれ計算してみます.

・$x_1=0$が定まったとき, 節$C_3$は確率1で充足されるので
$\mathrm{E}[X|(0,*,*,*)]=2-2\cdot (0.5)^2+1=2.5$

・$x_1=1$が定まったとき, 節$C_1,C_2$は確率1で充足されるので
$\mathrm{E}[X|(1,*,*,*)]=2+(1-(0.5)^2)=2.75$

以上より, $Y_1=\mathrm{E}[X|\mathcal{G}_1]$は




となります. 当然のことながら, $\mathrm{E}[Y_1]=0.5\times(2.5+2.75)=2.625=\mathrm{E}[X]$となっています.


・$x_1,x_2$の値が決定したとき:



先ほどと同様の考察を続けます. $\{(x_1,x_2,*,*)\}$を含む最小の$\sigma$-集合体$\mathcal{G}_2$は,



となります ($(0,*,*,*), (1,*,*,*)$が含まれていることに注意). そして分割$\mathcal{B}_2$としては



をとれます. (古典的な意味での)条件付き期待値をそれぞれ計算してやると,



となるので,



ここで, $\mathcal{G}_2$は$\mathcal{G}_1$よりも「細かい」ものになっていることがわかります. この後コイントスを続けていくとより細かいσ-集合体が得られ, 対応する条件付き期待値もまたより細かい関数になっていくことがわかると思います. そして最終的に4つの変数の割り当てが決定すると$\mathcal{G}_4=\mathcal{F}$となり, $Y_4=X$となります.

このように, 「過程が進んでいくにつれて情報が決定していき, 対応する$\sigma$-加法族が細かくなっていく」ことが重要で, その列$(\mathcal{G}_t)$をフィルトレーションと呼びます.


5. まとめ



古典的確率論における条件付き期待値から出発し, これを測度論的確率論における条件付き期待値の概念に(有限加法族に限定して)拡張していきました.
更に, 命題論理式の例を用いて, 観測される事象に応じて$\sigma$-集合体が細かくなっていき(フィルトレーション), それに応じて条件付き期待値がどんどん近似として精度の良いものになっていくことを見ていきました.

これらの概念はマルチンゲールを学ぶ出発点となるので, よく理解しておくと良いと思います.

2017年7月6日木曜日

有限加法族の分割

有限加法族とは, 有限集合$E$上のσ-加法族 $\mathcal{G}\subseteq 2^E$ でとなるものです. 有限加法族を台集合の分割を用いて表現する定理を証明します.
(おそらく既存の結果として知られているほどの簡単なものですが, そういうのを調べず私が個人的に見つけた証明を載せているので, もし関連結果 or よりスマートな証明をご存知の方がいらしたら教えていただければ幸いです).


この定理を使えば, 有限加法族に対する条件付き期待値を具体的に構成することが出来ます.
(有限でない場合は無理です)

2017年7月1日土曜日

最大平均次数と彩色数について

グラフ$G$に対して



を$G$の最大平均次数 (maximum average degree) と言います.  ここでグラフ$H$に対し$||H||$は$H$の辺数, $|H|$は$H$の頂点数を表します.
頂点$v$に対して$d(v)$で$v$の次数を表すことにすると, 握手補題より$2||H||=\sum_{v\in V(H)} d(v)$となるので, $\frac{2||H||}{|H|}$は$H$の平均次数を表しています. この値はグラフの「疎っぽさ」を表すような値になっていて, 色々と興味深い結果が知られています. 実は最小カットを二分探索の判定として用いることによって多項式時間でこの値を計算することが出来ます.

$\mathrm{mad}(G)$はグラフ理論の有名な本Sparistyにも重要な指標の一つとして紹介されていて, 次のような事実が(証明なしに)紹介されています.

$\chi(G)\leq \lfloor \mathrm{mad}(G) \rfloor+1$.

つまり$\mathrm{mad}(G)$を使って彩色数$\chi(G)$を上から抑えることができます. 非自明な感じがするので今回はこの事実の証明を載せたいと思います. 内容としては$\chi(G)\leq \mathrm{mad}(G) +1$を示しています(床関数をとっても本質的には変わらないので).

(この証明は私が考えたものなので, 他にもっとスマートな証明を知っている方がいらしたら教えていただければ幸いです).







[1] A Fast Parametric Maximum Flow Algorithm and Applications, G. Gallo, M.D. Grigoriadis, R. E. Tarjan (1986)

2017年6月24日土曜日

多分, 読むとランダムグラフを勉強したくなる記事

0. 概要


本記事では
  • ランダムグラフ理論の動機と応用
  • ランダムグラフ理論のさわり
  • ランダムグラフの面白い定理
について書きます. 読むとランダムグラフ理論を勉強したくなります.

1. ランダムグラフ理論の動機と応用


ランダムグラフ理論の主な動機としては
  1. 「とある性質Pを満たすグラフが存在するか?」という問に対する肯定的な解決
  2. 現実のネットワークにおける様々な現象の理論的説明
歴史的には1が重要で、グラフ理論における有名問題「任意に大きい彩色数と内周(長さ最小の閉路)を持つグラフは存在するか?」をErdősらが解決した際に初めてランダムグラフを用いられました. ロジックとしては「性質Pを満たすグラフの存在性」という問に対し, Pr[ランダムに生成したグラフがPを満たす確率]$>0$であることを示すことにより, この問を肯定的に解決する, というものになります.

2は応用上重要だと思います. 現実世界のネットワーク(複雑ネットワーク)にはスモールワールド性, 高いクラスタ係数, 次数のベキ乗則といった様々な現象が観測されます. そこでWSモデル, BAモデルといった複雑ネットワークを模倣するランダムグラフのモデルを解析することによってこれらの現象の発生を理論的に説明出来るようになります.

また, ランダムグラフはグラフアルゴリズムのベンチマークとして用いられることがよくあります. しかしベンチマークとして用いる際, そのランダムグラフはどのような性質(高い確率で連結なのか, 直径が小さいかどうかなど)を持つかについて知っておかなければいけません. 例えば「小直径グラフに対してはたまたま速く動作してしまうアルゴリズム」のベンチマークとして「高い確率で小直径になってしまうランダムグラフ」を(小直径になるとは知らずに)ベンチマークとして用いて数値実験を行い「ランダムグラフで高速に動いたから大体のグラフでも動く」と結論づけてしまったら最悪です. このような事態を避けるためにも, ランダムグラフの性質についての知識や簡単な導出過程については知っておくべきでしょう.

2. ランダムグラフ理論のさわり


2.1. Erdos-Renyi (ER)モデル


 頂点数 $n$ のグラフを考えます. 各頂点ペア $u \neq v$に対し, 確率$p$で独立に辺を引きます. このグラフ生成モデルを Erdos-Renyi(ER)モデルと呼び, 生成したグラフを$G(n,p)$で表します.


 ERモデルはランダムグラフ理論で最も多くの研究結果があります. ERモデルは通常, パラメータ$p$を$p=p(n)$(つまり, $n$の関数)として, $n\to\infty$における$G(n,p)$の構造を解析します. グラフの性質$\mathcal{P}(例えば連結性, 平面性など)に対してPr[G(n,p)がPを満たす]$\to 1$ (as $n\to\infty$) ならば$G(n,p)$はほとんど確実に性質$\mathcal{P}$を満たすと言います. ランダムグラフ理論では$n$頂点のランダムグラフ(例えば$G(n,p)$)はどのような性質をほとんど確実に満たすのか, について解明している理論であると言い換えることも出来ます.

 本稿では,

  • $p=o(n^{-2})$(注*)ならば, $G(n,p)$はほとんど確実に辺を持たない.
  • $p=\omega(n^{-2})$(注**)ならば, $G(n,p)$はほとんど確実に辺を持つ.
  • $p\sim \alpha \cdot n^{-2}$(注***)ならば, $\mathrm{Pr}$[$G(n,p)$が辺を持つ]$\to 1-e^{\alpha/2}$.

を証明して, 最後に$G(n,p)$の他の面白い性質を簡単に紹介していくという流れになります.

(注*) $f,g:\mathbb{N} \to \mathbb{R}_{\geq 0}$に対し
$f(n)=o(g(n)) \, \iff \, \lim_{n\to\infty}\frac{f(n)}{g(n)}=0$

(注**) $f,g:\mathbb{N} \to \mathbb{R}_{\geq 0}$に対し
$f(n)=\omega(g(n)) \, \iff \, \lim_{n\to\infty}\frac{f(n)}{g(n)}=\infty$

(注***) $f,g:\mathbb{N} \to \mathbb{R}_{\geq 0}$に対し
$f(n)\sim g(n) \, \iff \, \lim_{n\to\infty}\frac{f(n)}{g(n)}=1 \,\iff\, f(n)=(1+o(1))g(n)$.


2.2. First Order Method



$X$を非負の値をとる確率変数とします. 任意の$a>0$に対して



が成り立ちます. この不等式をMarkovの不等式と呼びます.
$G(n,p)$の辺数$m$は非負整数値をとる確率変数なので,

.

$p=o(n^{-2})$ならば, $n^2p\to 0$ (as $n\to\infty$)より,

.

以上より, $p=o(n^{-2})$ならば$G(n,p)$はほとんど確実に辺をもたないことが示されました. 他にも, $Y=G(n,p)$が含む三角形(長さ3の閉路)の個数 と定義すると,

$\mathrm{Pr}$($G(n,p)$が三角形を含む)$=\mathrm{Pr}(Y\geq 1) \leq \mathrm{E}[Y] \sim n^3p^3/6 \to 0$ (as $n\to\infty$).

となるので, $p=o(n^{-1})$ならば$G(n,p)$はほとんど確実に三角形を含まない ことが示せました. このように, Markovの不等式を用いて「ない」ことを示す証明技法をFirst Order Methodと呼びます. なぜ "First" なのかというと, 確率変数の一次モーメント(期待値)を計算するからです.


2.3. Second Order Method



First Order MethodはMarkovの不等式を用いて「ない」ことを証明する技法でした. 一方でランダムグラフ理論では「ある」ことを証明する技法が知られています. それがSecond Order Methodです.

一般に, 平均と分散が有限となるような確率変数$X$に対してChebyshevの不等式と呼ばれる次の不等式が成り立ちます.

.

ここで, $t=\mathrm{E}[X]$を代入すると,


したがって

.

となります. この$X$が例えば「辺の本数」「三角形の個数」などを表すなら, この不等式は「辺が存在する確率」「三角形が存在する確率」の下界を与えることになります.
このように分散を使ってランダムグラフ内に「ある」ことを証明する技法を Second Order Method と呼びます. 分散$\mathrm{V}[X]$を計算するためには二次モーメント$\mathrm{E}[X^2]$を計算する必要があるため "Second" の名を冠しています.

また, $X$が非負整数値をとるとき, コーシーシュワルツの不等式を用いることで次のような不等式が示せます.


これらの不等式から共通して言えることは, $\mathrm{E}[X^2]\sim \mathrm{E}[X]^2$が示せたら$\mathrm{Pr}(X>0)\to 1$が示せるということです.

それでは, $p=\omega(n^{-2})$として, $G(n,p)$が辺をほとんど確実に持つ, 即ち $\mathrm{Pr}(m>0)\to 1$ を示しましょう. ($m=m(G(n,p))$は$G(n,p)$に含まれる辺の個数を表す確率変数). 最も肝心なのは, $m$は指示関数の和で書き表わせるということです. 即ち, $n$頂点完全グラフ$K_n$の辺$e$に対して


という確率変数を定義したとき,


が明らかに成り立ちます. 従って, 期待値の線型性より


となり, 二次モーメント $\mathrm{E}[m^2]$については


となるので, 



従って



これを上記で紹介した不等式に代入すると, $p=\omega{n^{-2}}$より$n^2p\to \infty$なので,

.


となって所望の命題が示せました. まとめると, $p=o(n^{-2})$ならば$G(n,p)$はほとんど確実に辺を持たないが, $p=\omega(n^{-2})$ならば$G(n,p)$はほとんど確実に辺を持つことが証明されました. このようにパラメータのオーダーを変えた瞬間に一気に性質のオンオフが変わってしまう性質のことを相転移(phase transition)と言います. ランダムグラフ理論ではこのような相転移現象が数多く証明されてます.

三角形の個数も指示関数の和で表せるので, 全く同様にして同じようなことを示すことができ, 相転移を観察することが出来ます.

この節の最後に, monotonicity について紹介します. グラフの性質$\mathcal{P}$が以下の性質を満たすとき, $\mathcal{P}$はmonotone increasingであると言います.

「$G$が$\mathcal{P}$を満たすならば, $G$に任意の新しい辺$e$を追加して得られたグラフ$G\cup e$も$\mathcal{P}$を満たす.」

例えば, $\mathcal{P}$を「連結であるという性質」とします. $G$が$\mathcal{P}$を満たすとき, $G$は連結グラフです. そして$G$に新しい辺を追加しても連結なままです. 従って「連結性」は monotone increasing です. 他にも「辺を持つ」「直径$\leq 100$である」「辺連結度が100以上である」「ハミルトン閉路を持つ」などの数多くの重要な性質が monotone increasing となります.

一方、性質$\mathcal{P}$を満たすグラフ$G$からどの辺を削除しても依然として$\mathcal{P}$を満たすならば, 性質$\mathcal{P}$は monotone decreasing であるといいます. 例えば「平面的である」「森である」「ハミルトン閉路を持たない」などの性質が monotone decreasingとなります.

$\mathcal{P}$をmonotone increasingであるとします.  このとき必ず相転移が発生するような閾値関数が存在するということが証明されています (Bollobas, Thomasson, 1997). 具体的には

nontrivial で monotone increasingな性質 $\mathcal{P}$に対し, ある$p^*=p^*(n)$が存在して
$p=\omega(p^*)$ならばほとんど確実に$G(n,p)$は$\mathcal{P}$を満たし, $p=o(p^*)$ならばほとんど確実に$G(n,p)$は$\mathcal{P}$を満たさない.

ことが示されています(monotone decreasing についても同様のことが成り立ちます). 例えば, 「辺を持つ」という性質では$p^*=n^{-2}$となります.


2.4. 閾値関数上の振る舞い


$p=o(n^{-2})$, $p=\omega(n^{-2})$に対する$G(n,p)$の辺の有無について解析してきました. それではこれらの中間, すなわち $p\sim c\cdot n^{-2}$のときはどうなるでしょうか?

$m$はiidな指示関数の和として書けるので, 二項分布$\mathrm{Bin}\left(\binom{n}{2}, p\right)$に従う確率変数です. ここで, ポアソンの極限定理によると,



となるので (ここでは確率密度関数が各点収束するという意), 今回の場合は



となります. 即ち, 辺の本数$m$は漸近的に平均$c/2$のポアソン分布に従うため, $\mathrm{Pr}(m=0) \to e^{-c/2}$ となります.

様々な性質$\mathcal{P}$について, $p$が閾値関数上のときの$G(n,p)$の振る舞いの確率にはポアソン分布が絡んできていることが分かっています. 例えば$G(n,p)$の頂点を一つ固定してその次数を確率分布 $d$ で表すと, 明らかに $d$ は二項分布 $\mathrm{Bin}(n-1,p) \sim \mathrm{Bin}(n,p)$に従います. 従って

・$p=o(n^{-1})$のときは



・$p=\omega(n^{-1})$のときは, $d$が指示関数の和で表せることを用いると



・$p\sim c\cdot n^{-1}$のときは, ポアソン極限定理より, $d$は漸近的に平均$c$のポアソン分布に従うため,



が簡単に示せます. 特に$d=0$ということは固定した頂点が孤立点であり, つまり$G(n,p)$が非連結であるということになるので,

.

即ち $p\sim c/n$のときは正の確率で$G(n,p)$は非連結になることが示せました.
実際には頂点を$k$個だけ固定してそれぞれの次数を$d_1,\ldots,d_k$として$k$個の確率変数を定義すると, それぞれは漸近的に平均$c$のポアソン分布に従い, しかも実は漸近的にこれらの確率変数は独立であることが言えます. つまり



となり, グラフが連結であるならば $d_1>0,\ldots,d_k>0$となるので



今, $k$は任意の自然数だったので, 右辺は任意に小さくできるので,



つまり, $G(n,p)$はほとんど確実に非連結であることが示せました.

3. ランダムグラフ理論の面白い定理


ランダムグラフ理論では閾値関数などの様々な定理が知られているので個人的に面白いと思ったものを列挙します.

3.1. 連結性




とおきます. このとき







3.2. 頂点連結度


グラフ$G$が$k$-connectedであるとは, $G$を非連結にするためには最低でも$k$個の頂点を削除しなければならないことを意味します.



とします. このとき




3.3. ハミルトン閉路


ハミルトン閉路とは, 全ての頂点を一度ずつ通るような閉路のことです. 与えられたグラフがハミルトン閉路を持つかどうかを判定する問題はNP-完全で多項式時間では判定できないとされていますが, ランダムグラフがハミルトン閉路を含むかどうかもまた大きな難問でした.



とします. このとき,




3.4. 最大独立点集合のサイズ


グラフの独立点集合とは, 頂点部分集合$S\subseteq V$で$S$の任意の二頂点間に辺が存在しないようなものです. 独立点集合のうち要素数最大なものを最大独立点集合といい, その要素数を$\alpha(G)$と書きます. 与えられたグラフに対して$\alpha(G)$を計算する問題はNP-困難ですが, ランダムグラフ理論においては次の結果が知られています.

$p\in(0,1)$を定数とし, $b=\frac{1}{1-p}$とします. このときほとんど確実に



つまり, おおよそ $\alpha(G(n,p)) \simeq 2\log_b n$.


3.5. 彩色数


グラフの彩色(頂点彩色)とは, 頂点から色への写像で, 隣接頂点同士は異なる色に写される(塗られる)という性質を持ったものです. 彩色が存在するような色の種類数のうち最小の値を彩色数と呼び, $\chi(G)$で表します. 与えられたグラフ$G$に対して$\chi(G)$を計算する問題はNP-困難です.

$p\in(0,1)$を定数とし, $b=\frac{1}{1-p}$とします. すると

おおよそ $\chi(G(n,p)) \simeq \frac{n}{\log_b n}$ となります.

(注:) 彩色数と最大独立点集合の間には, $\chi(G)\alpha(G)\geq n$という関係があってこれを用いています.




4. おわりに


 ランダムグラフ理論の動機を概説し, first order method, second order ethod, Poisson approximation theoremについて紹介しました.
 私は東大でランダムグラフ理論について研究していますが, 日本にはランダムグラフをやっている人があまり居ません(少し寂しいことですが...). ランダムグラフ理論で用いられる確率的議論(そしてそのアイデア)は, 乱択アルゴリズムの解析や組合せ論において非常に有用で, それらを学ぶことはランダムグラフのみならず他の分野でも大きな武器になるのではないかと思います(あと二項係数に強くなれます). グラフ理論と確率論のインターセクションにあるランダムグラフ理論はそれらの深い理解に通じる面白い理論であり, そしてランダムグラフ理論の勉強を通じて確率論の深い理解に繋がることがあるので, 本格的に研究しなくても学んでみる価値は大いにあると信じています.


参考文献


[1] R. Diestel, "Graph Theory"
[2] A. Frieze, M. Karoński  "Introduction to Random Graphs" (著者がドラフトをウェブ上で公開しています)
[3] ‎Bollobás, "Random Graphs"