グラフ$G$の直径が $D$ 以下であるということは, どの頂点ペアに対しても長さ$\leq D$のパスが存在するということになります.
今, 各辺が独立に確率$p$で結ばれたランダムグラフ $G(n,p)$ を考えます. このグラフが長さ $l$ のパスを何本持つかを考えてみましょう. 簡単のため $l\in\mathbb{N}$ は定数とします. 期待値的には, 長さ$l$のパスは$l+1$個の頂点と$l$本の辺を持つため, $n(n-1)\cdots (n-l)p^l\approx n(np)^l$だけ含まれています.
ということは長さ$\leq D$のパスは期待値的には全部で $n\sum_{l=1}^D (np)^l \approx n^{D+1}p^D$ だけ含まれています. 冷静に考えると, パスの本数といった「〜の数」というものは指示関数の和によって表すことができます. 今回の場合は$\sum_{P:path}1_{[P\subseteq G(n,p)]}$といった具合です. それぞれの指示関数は独立のいうわけではありませんが, パスが辺素なら独立なので, 「なんとなく独立っぽい感じ」の確率変数の和ということになります. たくさんの独立な確率変数の和は期待値の周りに集中する(c.f. Chernoff bound)ので, $G(n,p)$は長さ$\leq D$のパスを$n^{D+1}p^D$本くらい含んでいそうです. 実際この直感はそこそこ正しくて, Jansonの不等式やこの結果を用いるとChernoffに近い感じの集中性が示せます (ただしどれくらい集中性が強いのかはかなり難しい問題です).
さて, $G(n,p)$の直径が$\leq D$である確率を考えます. 先ほどの直感を信じて長さ$\leq D$のパスが $n^{D+1}p^D$本あるとしましょう. 各頂点ペアにこれらのパスをランダムに「配分」することを考えます. ランダムグラフなのでパスの本数に偏り（例えば頂点1,2間には長さ$D$のパスが114514本あって頂点3,4間には1本もない）みたいなものは起こりにくいはずです。そこで$\binom{n}{2}$個の空のバケツがあってそこに$n^{-1}(np)^D$個のボールを一個ずつランダムに投げ入れたときに, 全部のバケツに少なくとも一個のボールが入っている確率を考えます (このイメージは全ての頂点のペアに長さ$\leq D$のパスが少なくとも一本ある = 直径$\leq D$に対応します). するとクーポンコレクター問題を思い出してもらうと, $n^{D+1}p^D \gg \binom{n}{2}\log \binom{n}{2}\approx n^2\log n$ ならば直径$\leq D$になるような気がします.
まとめると, $n^{D-1}p^D\gg \log n$ならば$G(n,p)$の直径は$D$以下, $n^{D-1}p^D \ll \log n$ならば直径は$D+1$以上となる, ことがなんとなくわかります.
実はこの結果は理論的にも正しいです. また, 「$\gg$」と「$\ll$」の境目に関しては次の結果が知られています.
Thm [p.112, Intruduction to Random Graphsより]
定数$D,c$に対して, $p^Dn^{D-1}=\log (n^2/c)$ を満たすよう$p=p(n)$を定めると, 以下が成り立つ:
- $\lim_{n\to\infty} \Pr(\mathrm{diam}(G(n,p))=D)=\exp(-c/2)$,
- $\lim_{n\to\infty} \Pr(\mathrm{diam}(G(n,p))=D+1)=1-\exp(-c/2)$.
証明はこの記事で説明した話とは全く違いますが, それほど難しくはないです. 距離$D$のペアの個数についてPoisson approximation theoremを適用するために頑張って計算するというものです.
0 件のコメント:
コメントを投稿