Topology of random clique complexes

DOI10.1016/J.DISC.2008.02.037zbMATH Open1215.05163arXivmath/0605536OpenAlexW2097040817WikidataQ105583640 ScholiaQ105583640MaRDI QIDQ1024483FDOQ1024483

Authors: Matthew Kahle 

Publication date: 17 June 2009

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: In a seminal paper, Erdos and Renyi identified the 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 n goes to 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 spheres.

Full work available at URL: https://arxiv.org/abs/math/0605536

Recommendations

• The threshold function for vanishing of the top homology group of random \(d\)-complexes
• Fundamental groups of clique complexes of random graphs
• Homological connectivity of random 2-complexes
• Homological connectivity of random k -dimensional complexes
• Topology of random -dimensional cubical complexes

zbMATH Keywords

phase transitionrandom graphdiscrete Morse theoryflag complexclique complex

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• Homological connectivity of random k -dimensional complexes
• Paths in graphs
• Title not available (Why is that?)
• Homological connectivity of random 2-complexes
• A user's guide to discrete Morse theory
• Topological characteristics of random triangulated surfaces
• The clique complex and hypergraph matching
• The neighborhood complex of a random graph

Cited In (84)

• Extremal problems related to Betti numbers of flag complexes
• Networks beyond pairwise interactions: structure and dynamics
• Statistical ranking and combinatorial Hodge theory
• Title not available (Why is that?)
• The threshold function for vanishing of the top homology group of random \(d\)-complexes
• A geometric Hall-type theorem
• Extremal Betti numbers of Vietoris-Rips complexes
• Algebraic topological characterizations of structural balance in signed graphs
• Spectral gaps of random graphs and applications
• Collapsibility of random clique complexes
• Mantel's theorem for random graphs
• Persistent homology of complex networks
• Betti curves of rank one symmetric matrices
• Random connection models in the thermodynamic regime: central limit theorems for add-one cost stabilizing functionals
• Robustness and percolation of holes in complex networks
• Random coxeter groups
• On the cycle space of a random graph
• Clique topology reveals intrinsic geometric structure in neural correlations
• Random simplicial complexes in the medial regime
• Homotopy types of random cubical complexes
• Random Simplicial Complexes: Models and Phenomena
• The topology of probability distributions on manifolds
• Random finite topologies and their thresholds
• Asymptotic behavior of lifetime sums for random simplicial complex processes
• Asymptotics of integrals of Betti numbers for random simplicial complex processes
• Network geometry and complexity
• Large random simplicial complexes. III: The critical dimension.
• Homological connectivity in random Čech complexes
• Thresholds for vanishing of `isolated' faces in random Čech and Vietoris-Rips complexes
• Limit theorems for topological invariants of the dynamic multi-parameter simplicial complex
• Analysis of crowdsourced sampling strategies for HodgeRank with sparse random graphs
• Hodge-Kodaira decomposition of evolving neural networks
• The why, how, and when of representations for complex systems
• Random Graphs, Retractions and Clique Graphs
• On topological minors in random simplicial complexes
• Confidence sets for persistence diagrams
• Exponential random simplicial complexes
• Homology of multi-parameter random simplicial complexes
• Persistent homology of collaboration networks
• Random Simplicial Complexes
• On the evolution of topology in dynamic clique complexes
• Evaluating visual properties via robust HodgeRank
• Markovian approach to tackle competing pathogens in simplicial complex
• Large random simplicial complexes. II: The fundamental group
• Sharp vanishing thresholds for cohomology of random flag complexes
• Fundamental groups of clique complexes of random graphs
• Random simplicial complexes, duality and the critical dimension
• Comparing minimal simplicial models
• The neighborhood complex of a random graph
• Competing spreading dynamics in simplicial complex
• Topology of random -dimensional cubical complexes
• Random geometric complexes
• Phase transition in cohomology groups of non-uniform random simplicial complexes
• A social communication model based on simplicial complexes
• Homological connectivity of random k -dimensional complexes
• The fundamental group of random 2-complexes.
• Random Čech complexes on Riemannian manifolds
• Random graph products of finite groups are rational duality groups
• \(\ell^2\)-Betti numbers of random rooted simplicial complexes
• The Vietoris-Rips complexes of a circle
• Fréchet means for distributions of persistence diagrams
• On the topology of random complexes built over stationary point processes
• Complexity of simplicial homology and independence complexes of chordal graphs
• Curvature sets over persistence diagrams
• Pairwise disjoint maximal cliques in random graphs and sequential motion planning on random right angled Artin groups
• Simplicial epidemic model with individual resource
• Euler characteristic surfaces
• On topological bound states and secular equations for quantum-graph eigenvalues
• On the contractibility of random Vietoris-Rips complexes
• Asymptotic degree of random monomial ideals
• What Are Higher-Order Networks?
• Girth, magnitude homology and phase transition of diagonality
• The regularity of almost all edge ideals
• Asymptotics of lower dimensional zero-density regions
• Large deviations for subcomplex counts and Betti numbers in multiparameter simplicial complexes
• First Betti number of the path homology of random directed graphs
• Maximal persistence in random clique complexes
• Topology of clique complexes of line graphs
• Large simplicial complexes: universality, randomness, and ampleness
• Multivariate central limit theorems for random clique complexes
• Random hypergraphs, random simplicial complexes and their Künneth-type formulae
• One‐sided sharp thresholds for homology of random flag complexes
• Flexible memory networks
• Maps on random hypergraphs and random simplicial complexes

This page was built for publication: Topology of random clique complexes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1024483)