Homological Connectivity Of Random 2-Complexes

Nathan Linial and Roy Meshulam
Combinatorica
Issue Volume 26, Number 4 / August, 2006
Pages 475-487
http://dx.doi.org/s00493-006-0027-9

n-1次元単体のランダム2次元部分複体について考える．
モデルは，まず1次元の部分はもとの単体から全て持ってきて，2次元面は1つ1つを独立に確率pで選ぶものである．
そのようにしてできた2次元複体Yのホモロジー群H_1(Y;F_2)が0になる確率を考える．
定理では，pが(2log(n)-ω(n))/nのとき，この確率は0に収束し，
pが(2log(n)+ω(n))/nのとき，この確率は1に収束することを示している．
(極限はnを無限大にもっていくときのものである．)
ランダムグラフの研究や結果はたくさんあるけれども，それを一般化したランダム複体についてはあまり研究されていない気がするので，そういう意味でも面白い論文．