×

zbMATH — the first resource for mathematics

Topology of random clique complexes. (English) Zbl 1215.05163
Summary: In a seminal paper, Erdős and Rényi identified a sharp threshold for connectivity of the random graph \(G(n,p)\). In particular, they showed that if \(p\gg \log n/n\) then \(G(n,p)\) is almost always connected, and if \(p\ll \log n/n\) then \(G(n,p)\) is almost always disconnected, as \(n\rightarrow \infty \).
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 Erdős-Rényi 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 \(k\)th 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.

MSC:
05C80 Random graphs (graph-theoretic aspects)
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Alon, N.; Spencer, J., The probabilistic method, (2000), John Wiley
[2] Björner, A., Topological methods, (), 1819-1872 · Zbl 0851.52016
[3] Bollobás, B., Random graphs, (2001), Cambridge University Press · Zbl 0997.05049
[4] Erdős, P.; Rényi, A., On random graphs I, Publ. math. debrecen, 6, 290-297, (1959) · Zbl 0092.15705
[5] Forman, R., A user’s guide to discrete Morse theory, () · Zbl 1048.57015
[6] Hatcher, A., Algebraic topology, (2002), Cambridge University Press · Zbl 1044.55001
[7] E. Babson, C. Hoffman, M. Kahle, Simple connectivity of random 2-complexes (submitted for publication), arXiv:math.CO/0711.2704
[8] Kahle, M., The neighborhood complex of a random graph, J. combin. theory ser. A, 114, 380-387, (2007) · Zbl 1110.05090
[9] Linial, N.; Meshulam, R., Homological connectivity of random 2-complexes, Combinatorica, 26, 475-487, (2006) · Zbl 1121.55013
[10] Meshulam, R., The clique complex and hypergraph matching, Combinatorica, 21, 89-94, (2001) · Zbl 1107.05302
[11] R. Meshulam, N. Wallach, Homological connectivity of random \(k\)-dimensional complexes (submitted for publication), arXiv:math.CO/0609773 · Zbl 1177.55011
[12] Pippenger, N.; Schleich, K., Topological characteristics of random triangulated surfaces, Random structures algorithms, 28, 247-288, (2006) · Zbl 1145.52009
[13] Stanley, Richard, Enumerative combinatorics, Vol. 2, (1999), Cambridge University Press
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.