Random Graphs (Chapter 11, Graph Theory)

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 以上のクリークも独立集合も持たないかもしれない

定理：任意の 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 を使う

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

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

あるところで 0 から 1 （あるいは 1 から 0）に変わる事がある．これを threshold function と呼ぶ．

iwiwi 備忘録