Erdős–Rényiのランダムグラフ

前提知識: グラフ, 有限確率空間, 二項分布, Chebyshevの不等式, 連結グラフ

$n$ 個の頂点の各対を、硬貨を投げて独立に確率 $p$ で辺で結ぶ。こうして得られる無作為なグラフを Erdős–Rényi のランダムグラフ（Erdős–Rényi random graph）といい、$G(n,p)$ と書く。辺の本数を $m$ に固定して、$m$ 本の辺をもつグラフから等確率に 1 つ選ぶ模型 $G(n,m)$ もあり、どちらも同じ名でよばれる。ランダムグラフの理論は Erdős と Rényi の論文に始まり、$G(n,p)$ の形は Gilbert が導入した（FK26 pp. 3–4）。
$n$ を大きくしながら $p$ を $n$ の関数として動かすと、$G(n,p)$ の姿は $p$ のある大きさを境に急に変わる。たとえば $p$ が $\frac{\ln n}n$ より少し小さければほとんど確実に孤立した頂点が残り、少し大きければほとんど確実に連結になる。$p=\frac cn$ では、$c<1$ なら連結成分はどれも小さいが、$c>1$ になると頂点の一定の割合を含む巨大な成分が現れる。この記事では 2 つの模型を定義して関係を示し、単調な性質がかならず「閾値」をもつこと（Bollobás–Thomason の定理）と、連結性の閾値が $\frac{\ln n}n$ であることを証明する。巨大な成分の出現は主張と所在を述べ、条件を外すと結論が崩れる例を表にまとめる。

2 つの模型

以下、頂点集合を $[n]:=\{1,\dots,n\}$ とし、グラフは グラフ の記事の定義「グラフの定義」の単純無向グラフとする。$N:=\binom n2$ と書き、$[n]$ の 2 元部分集合（頂点の対）を単に「対」とよぶ。$[n]$ 上のグラフは辺集合で決まり、ちょうど $2^N$ 個ある（グラフ の記事の命題「ラベル付きグラフの個数」）。グラフ $G$ の辺の本数を $e(G)$ と書く。

$G(n,p)$ では、対 $e$ が辺になる事象を $A_e$ とすると、$N$ 個の事象 $A_e$ は独立で、どれも確率 $p$ をもつ。実際、相異なる対 $e_1,\dots,e_r$ を指定すると、それらがすべて辺になるグラフの確率の和は、残りの $N-r$ 個の対を辺にするかどうかで二項展開して $p^r(p+(1-p))^{N-r}=p^r$ になる。したがって辺の本数 $e(G)$ は試行回数 $N$、成功確率 $p$ の 二項分布 に従い、平均は $Np$、分散は $Np(1-p)$ である（二項分布 の命題「二項分布の期待値と分散」）。各頂点の次数は試行回数 $n-1$ の二項分布に従う。$p=\frac cn$（$c>0$ は定数）なら、次数の分布は $n\to\infty$ で平均 $c$ の Poisson 分布に近づく（Poisson分布 の系「少数の法則」）。
$p=\frac12$ のとき、どのグラフの確率も $2^{-N}$ なので、$G(n,\frac12)$ は $[n]$ 上のグラフ全体からの一様な選び方である。$G(n,\frac12)$ で性質が成り立つ確率は、その性質をもつグラフの割合にほかならない。
2 つの模型は、辺の本数で条件を付けると一致する。

$Np\to\infty$ なら、Chebyshevの不等式 の定理「Chebyshev の不等式」により、任意の $\varepsilon>0$ について $P(\lvert e(G)-Np\rvert\ge\varepsilon Np)\le\frac{Np(1-p)}{(\varepsilon Np)^2}\to0$ である。つまり $G(n,p)$ の辺の本数はほとんど確実に $Np$ に近く、上の命題と合わせて、$m$ が $Np$ に近いとき $G(n,m)$ と $G(n,p)$ は似た振る舞いをする。この近さを正確にした比較定理は FK26 Theorem 1.4（p. 9）にある（この記事では証明しない）。$G(n,p)$ は辺が独立なので計算しやすく、以下では主に $G(n,p)$ を扱う。

単調な性質と重ね合わせ

$[n]$ 上のグラフの集合 $\mathcal A$ を グラフの性質 といい、$G\in\mathcal A$ を「$G$ は性質 $\mathcal A$ をもつ」と読む。実際には「連結である」「三角形を含む」のように各 $n$ ごとに定まる性質の列を考え、$n$ を省いて書く。$P_p(\mathcal A):=P(G\in\mathcal A)$（$G\sim G(n,p)$）と書く。

「連結である」「三角形を含む」「Hamilton 閉路をもつ」は単調増加であり、「孤立点（次数 $0$ の頂点）をもつ」「平面グラフである」は単調減少である。$\mathcal A$ が単調増加であることと、その補集合が単調減少であることは同値である。
独立な 2 つのランダムグラフを重ねると、またランダムグラフになる。

2 は「辺を増やしやすくすれば、単調増加な性質は成り立ちやすくなる」という直観どおりのことだが、式 $\sum_{G\in\mathcal A}p^{e(G)}(1-p)^{N-e(G)}$ の形からは直接は見えない。1 のように 1 つの確率空間の上で 2 つのランダムグラフを同時に作って比べる方法を 結合（coupling）という。

閾値

以下、各 $n\ge2$ について $p=p(n)\in[0,1]$ を与え、$n\to\infty$ での振る舞いを考える。事象の列 $E_n$ が $P(E_n)\to1$ を満たすとき、$E_n$ は 漸近的にほとんど確実に（asymptotically almost surely）起こるという。

閾値は定数倍の違いを除いてしか決まらない（$p^*$ が閾値なら $\frac12p^*$ も閾値である）。鋭い閾値は閾値である。定義は FK26 Definition 1.6・1.9（pp. 10–11）と同じであり、単調減少な性質には補集合の閾値を使う。

三角形を含む性質の閾値は $\frac1n$ である（確率論的方法 の命題「ランダムグラフの三角形」）。一般に、辺をもつ固定したグラフ $H$ を部分グラフとして含む性質の閾値は $n^{-1/m(H)}$ である。ここで $m(H)$ は $H$ の部分グラフ $H'$ にわたる $\frac{e(H')}{\lvert V(H')\rvert}$ の最大値である（FK26 Theorem 5.3、p. 77。この記事では証明しない）。
閾値の存在そのものは、単調性だけから従う。

この定理は FK26 Theorem 1.7（p. 10）にある。定理は閾値の存在を保証するが、閾値がいくらかは性質ごとに調べなければならず、鋭い閾値をもつとも限らない（反例の表の 2 行目）。

連結性の閾値

連結性は、孤立点がなくなるのと同じ時期に起こる。以下 $\ln$ は自然対数とし、$\omega=\omega(n):=np-\ln n$ と書く。すなわち $p=\frac{\ln n+\omega}n$ である。

最後の主張は、$p\ge(1+\varepsilon)\frac{\ln n}n$ なら $\omega\ge\varepsilon\ln n\to\infty$、$p\le(1-\varepsilon)\frac{\ln n}n$ なら $\omega\le-\varepsilon\ln n\to-\infty$ であることから従う（孤立点のある連結なグラフは頂点 $1$ 個のものだけである）。

$\omega$ が定数 $c$ に近づくときは、孤立点の個数の分布は平均 $e^{-c}$ の Poisson 分布に近づき（FK26 Theorem 3.1、p. 52）、$G$ が連結である確率は $e^{-e^{-c}}$ に近づく（FK26 Theorem 4.1 の証明、p. 67。そこでは $\omega=c$ の場合を示しており、$\omega\to c$ の一般の列へは prop-er-coupling の 2 の単調性で移る）。どちらもこの記事では証明しない。さらに、$G(n,m)$ で辺を 1 本ずつ無作為に加えていく過程では、漸近的にほとんど確実に、最後の孤立点が消えた瞬間にグラフは連結になる（FK26 Theorem 4.2、p. 69）。

巨大成分の出現

辺の本数が頂点数の半分を超えるころ、連結成分の大きさが急に変わる。これは Erdős と Rényi が見いだした、ランダムグラフの相転移の代表例である。$c>1$ について、方程式
$$ \beta=1-e^{-c\beta} $$
は $0< \beta<1$ の解をただ 1 つもつ。実際 $g(\beta):=1-e^{-c\beta}-\beta$ は狭義に凹で、$g(0)=0$、$g'(0)=c-1>0$、$g(1)=-e^{-c}<0$ である。$c\le1$ なら $g'(\beta)=ce^{-c\beta}-1< 0$（$\beta>0$）なので正の解はない。

同書は 2 の大きさを $1-\frac xc$、$xe^{-x}=ce^{-c}$、$0< x<1$ の形で書く。$x=c(1-\beta)$ とおけば上の方程式と同じである。平均次数 $\frac{2m}n$ は $c$ に近く、$G(n,p)$ では $p=\frac cn$ にあたる。境目の $p=\frac1n$ では、最大の連結成分の大きさは $n^{2/3}$ の程度である（FK26 Theorem 2.21、p. 42）。
$\beta$ の方程式の意味は次のように理解できる。頂点 $v$ から出発して連結成分を探ると、各頂点から新しく見つかる隣の頂点の個数は、成分がまだ小さいうちは近似的に平均 $c$ の Poisson 分布に従う（Poisson分布 の系「少数の法則」）。この探索が終わらない確率を $\beta$ とすると、$v$ の隣の頂点のどれからも探索が続かない確率 $1-\beta$ は、隣の個数 $K$ について $E[(1-\beta)^K]=e^{-c\beta}$ に等しいはずである。これが上の方程式であり、$\beta$ は頂点が巨大成分に入る確率を表す。この説明は直観であって証明ではない。
辺の本数を増やしていくと、$G(n,m)$ の典型的な姿は次のように移り変わる（$m$ と $p$ は $p\approx\frac{2m}{n^2}$ で対応する）。

辺の確率が定数のとき

$p$ を $n$ によらない定数 $0< p<1$ にすると、$G(n,p)$ は非常に密で均質になる。たとえば、相異なる頂点 $a_1,\dots,a_k,b_1,\dots,b_l$ を任意に指定したとき、すべての $a_i$ と隣接しどの $b_j$ とも隣接しない頂点 $z$ がある、という性質は漸近的にほとんど確実に成り立つ。証明は、$z$ の候補 $n-k-l$ 個について条件が独立に確率 $p^k(1-p)^l$ で成り立つことから、条件を満たす $z$ のない指定の確率の和が $n^{k+l}(1-p^k(1-p)^l)^{n-k-l}\to0$ となることによる。$p=\frac12$ の場合、有限モデル理論 の補題「拡大公理はほとんど確実に成り立つ」はこれを示し、そこから定理「グラフの 0-1 法則」を導いている。すなわち、一階の文で書けるグラフの性質が $G(n,\frac12)$ で成り立つ確率は $0$ か $1$ に近づき、極限が $1$ になるのは可算ランダムグラフ（Rado グラフ）でその文が成り立つときちょうどである。

条件を外した反例

補足

• ランダムグラフ過程。 $N$ 個の対を一様に無作為な順に並べ、空グラフから始めて 1 本ずつ辺を加えると、グラフの列 $G_0\subset G_1\subset\cdots\subset G_N$ が得られる。各 $G_m$ は $G(n,m)$ に従う（順列の最初の $m$ 個の集合は、$m$ 元部分集合のどれも等しい確率でとる）。この列は、性質がいつ現れるかを 1 本の過程の中で追う道具であり、thm-er-connectivity の後で述べた「最後の孤立点が消えた瞬間に連結になる」はこの過程についての主張である。
• 存在証明への応用。 内周と彩色数がともに大きいグラフの存在（確率論的方法 の定理「内周と彩色数がともに大きいグラフ」）は $G(n,p)$ を $p=n^{\theta-1}$ でとって示され、Ramsey 数の下界（Ramseyの定理 の定理「Erdős の下界」）は、辺を確率 $\frac12$ で 2 色に塗ること、すなわち $G(n,\frac12)$ とその補グラフを考えることと同じである。ランダムグラフの性質の多くは、こうした存在証明の中で調べられてきた。
• ほかの模型。 次数がすべて $r$ のグラフから一様に選ぶランダム正則グラフや、平面の無作為な点を距離で結ぶランダム幾何グラフなど、辺の独立性をもたない模型も研究されている（FK26 第 9 章・第 10 章）。$G(n,p)$ の計算の多くは辺の独立性に頼るので、これらの模型では別の道具が要る。

関連項目

• 前提: グラフ, 連結グラフ, 二項分布, Chebyshevの不等式
• 方法: 確率論的方法, 期待値の線形性と数え上げ, Lovászの局所補題
• 比較: 有限モデル理論, 無限グラフ, Poisson分布
• 発展: Ramseyの定理, 彩色数