Random Subgraphs Of Finite Graphs: III. The Phase Transition For The n-Cube

Christian Borgs, Jennifer T. Chayes, Remco van der Hofstad, Gordon Slade and Joel Spencer
Combinatorica
Volume 26, Number 4 / August, 2006
Pages 395-410
http://dx.doi.org/10.1007/s00493-006-0022-1

超立方体のランダム部分グラフに関する論文．
ランダムグラフのモデルは各辺が確率pで選ばれるというErdos-Renyiモデルの類似．
このモデルをはじめに考察したのはErdos & Spencer (1979) だそうで，
彼らは上述のランダム部分グラフが連結である確率の収束先がp<1/2のときに0，p=1/2のときに1/e，p>1/2のときに1となることを示したようだ．(いわゆる閾値現象．)
また彼らはp=(1+ε)/nでε<0のとき最大サイズ連結成分の頂点数がo(V)になることも示し
(ここでnは超立方体の次元，Vは超立方体の頂点数，すなわちV=2^n)，
ε>0のときにはそれがΘ(V)になることを予想した．(いわゆる相転移．)
この予想が正しいことを証明したのはAjtai, Komlos & Szemeredi (1982) で，
彼らはsprinklingという技法を使ったようだ．これはパーコレーションに似てるらしい．
(論文のイントロしか読んでないから，こんな煮え切らない言い方ばかりですいません．)
しかし彼らの結果はεが定数の場合にしか適用できない．
定数じゃない場合の結果が後にBollobas, Kohayakawa & Luczak (1992) で証明され，彼らは
n→∞のときε→0となる場合の確率p=(1+ε)/nを考えた．
そして，ε≦-(log n)^2 /( (loglog n) n^(1/2) ) のときasymptotically almost surelyで
最大サイズ連結成分の頂点数が(2log V)(1+o(1))/ε^2となり，
ε≧60(log n)^3/nのときasympototically almost surelyで最大サイズ連結成分の頂点数が2εV(1+o(1))となることを示した．
しかしこの場合に臨界的なpがまだ判明しているわけではない．
この研究論文は3部作で，この問題に挑んでいる．これは3部作の3本目で臨界閾値 (critical threshold) という概念を定義して，問題を精緻化している．