読者です 読者をやめる 読者になる 読者になる

Random Graphs (Chapter 11, Graph Theory)

http://iwiwi.m12.coreserver.jp/iwi.tc/wiki/index.php?%E6%9B%B8%E7%B1%8D%2FGraph%20Theory%2F11.%20Random%20Graphs

The notion of a random graph

  • Erdos-Renyi model $G(n, p)$
    • $q = 1 - p$ とおく
  • 独立集合 $ P[\alpha(G) \geq k] \leq {n \choose k}q^{k \choose 2} $
  • クリーク $ P[\omega(G) \geq k] \leq {n \choose k}p^{k \choose 2} $
  • Ramsey number R(r)
    • $R(r)$ 頂点以上のグラフは必ず $K^r$ か $\overline{K^r}$ を含む
    • $R(r) > n > 2^\frac{k}{2}$ を示す
    • $G(n, 1/2)$ を考えて,$P[\alpha(G) \geq k] + P[\omega(G) \geq k] < 1$ となる
    • 従って,k 以上のクリークも独立集合も持たないかもしれない

The probabilistic method

  • 定理:任意の k について,$g(H)>k$ かつ $\chi(H)>k$ なる $H$ が存在する
    • $g(G)$ := girth (最短のサイクル長)
    • $\chi(G)$ := 彩色数
    • つまり,ローカルに見たら木みたいなのに,彩色数も大きいっていうグラフがある!
  • 証明
    • 最初に考える事
      • $p$ を小さくすると,$g(G)$ は大きくなる
      • 彩色数の代わりに独立集合を考えて,$n/k$ より大きい独立集合が 1 個はないといけない
      • そういうのがなければ,彩色数は $k$ より大きい
      • $p$ を大きくすると,独立集合はなくなって $\chi(G)$ は大きくなる
      • でも,さっきみたいに簡単に和等で証明できるような良い $p$ は存在しない(むずい!)
    • そこで
      • $n/2$ 個しか short cycle がなく,サイズ $n/2k$ より大きい独立集合がないものをつくる
      • 全 cycle から頂点を削除して $H$ を得る
      • Markov's inequality: $P[X \geq a] \leq \frac{E(X)}{a}$ (独立じゃない時に便利!)
      • サイクル同士はかぶったりするから独立じゃないので面倒だが Markov's inequality を使う

Properties of almost all graphs

  • $n \rightarrow \infty$ の時 $G$ がある性質を持つ確率が 1 や 0 に収束するものを考える
  • 任意のグラフ $H$ について,$H$ を部分誘導グラフとして含む確率は 1 に収束
  • $k$-connected である確率は 1 に収束
Zero-one laws

First-order logic で書ける性質は確率が必ず 0 か 1 に収束する!
(この本じゃなくて probabilistic methods の方に載ってる.)

Threshold functions and second moments

今度は,相変わらず大きな $n$ を考えるが,$p$ の変化によってどうなるか.今度は$p$ は定数でなく $n$ の関数.

あるところで 0 から 1 (あるいは 1 から 0)に変わる事がある.これを threshold function と呼ぶ.

  • 固定した $H$ を部分グラフとして持つ
    • 0 になる側:期待値から Markov's inequality
    • 1 になる側:期待値は使えない.second moment & Chebyshev's inequality
      • $P[|X - \mu| \leq \lambda] \leq \frac{\sigma^2}{\lambda^2}$
      • $\mu$ := 平均
      • $\sigma^2 $ := $E((X - \mu)^2)$
      • $\lambda > 0$ 任意の定数
    • threshold function は $t(n) = n^{-1/d(H)}$
      • densest subgraph $d(H) = \max_{H' \subseteq H} \frac{|E(H')|}{|V(H')|}$