期刊
DISCRETE MATHEMATICS
卷 309, 期 6, 页码 1658-1671出版社
ELSEVIER
DOI: 10.1016/j.disc.2008.02.037
关键词
Random graph; Phase transition; Clique complex; Flag complex; Discrete Morse theory
类别
资金
- NSA [H98230-05-1-0053]
- University of Washington's NSF-VIGRE
In a seminal paper, Erdos and Renyi identified a sharp threshold for connectivity of the random graph G(n, p). In particular, they showed that if p >> log n/n then G(n. p) is almost always connected, and if p << log n/n then G(n. p) is almost always disconnected, as it -> infinity. The clique complex X(H) of a graph H is the simplicial complex with all complete subgraphs of H as its faces. In contrast to the zeroth homology group of X(H), which measures the number of connected components of H, the higher dimensional homology groups of X(H) do not correspond to monotone graph properties. There are nevertheless higher dimensional analogues of the Erdos-Renyi Theorem. We study here the higher homology groups of X(G(n. p)). For k > 0 we show the following. If p = n(alpha), with alpha < -1/k or alpha > - 1/(2k + 1), then the kth homology group of X(G(n, p)) is almost always vanishing, and if -1/k < alpha < -1/(k + 1), then it is almost always nonvanishing We also give estimates for the expected rank of homology, and exhibit explicit nontrivial classes in the nonvanishing regime. These estimates suggest that almost all d-dimensional clique complexes have only one nonvanishing dimension of homology, and we cannot rule out the possibility that they are homotopy equivalent to wedges of a spheres. (C) 2008 Elsevier B.V. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据