Topology of random clique complexes

DOI10.1016/J.DISC.2008.02.037MaRDI QIDQ1024483zbMATH OpenOpenAlexWikidataFDO

Authors Matthew Kahle

Publication date 17 June 2009

Published in Discrete Mathematics (Search for Journal in Brave)

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 3150484 (Why is no real title available?)
• scientific article; zbMATH DE number 1268810 (Why is no real title available?)
• scientific article; zbMATH DE number 2103273 (Why is no real title available?)
• scientific article; zbMATH DE number 863503 (Why is no real title available?)
• A user's guide to discrete Morse theory
• Homological connectivity of random 2-complexes
• Homological connectivity of random k -dimensional complexes
• Paths in graphs
• The clique complex and hypergraph matching
• The neighborhood complex of a random graph
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• Topological characteristics of random triangulated surfaces

Cited in

(84)

• Extremal problems related to Betti numbers of flag complexes
• Networks beyond pairwise interactions: structure and dynamics
• Maps on random hypergraphs and random simplicial complexes
• Statistical ranking and combinatorial Hodge theory
• Curvature sets over persistence diagrams
• scientific article; zbMATH DE number 19224 (Why is no real title available?)
• Extremal Betti numbers of Vietoris-Rips complexes
• The threshold function for vanishing of the top homology group of random \(d\)-complexes
• A geometric Hall-type theorem
• Algebraic topological characterizations of structural balance in signed graphs
• Collapsibility of random clique complexes
• Spectral gaps of random graphs and applications
• Pairwise disjoint maximal cliques in random graphs and sequential motion planning on random right angled Artin groups
• 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
• Clique topology reveals intrinsic geometric structure in neural correlations
• Random simplicial complexes in the medial regime
• On the cycle space of a random graph
• Homotopy types of random cubical complexes
• Simplicial epidemic model with individual resource
• Euler characteristic surfaces
• 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
• On topological bound states and secular equations for quantum-graph eigenvalues
• Network geometry and complexity
• On the contractibility of random Vietoris-Rips complexes
• Homological connectivity in random Čech complexes
• Large random simplicial complexes. III: The critical dimension.
• Asymptotic degree of random monomial ideals
• 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
• What Are Higher-Order Networks?
• Girth, magnitude homology and phase transition of diagonality
• Hodge-Kodaira decomposition of evolving neural networks
• Random Graphs, Retractions and Clique Graphs
• The why, how, and when of representations for complex systems
• On topological minors in random simplicial complexes
• The regularity of almost all edge ideals
• Asymptotics of lower dimensional zero-density regions
• Confidence sets for persistence diagrams
• Exponential random simplicial complexes
• Large deviations for subcomplex counts and Betti numbers in multiparameter simplicial complexes
• Persistent homology of collaboration networks
• Homology of multi-parameter random simplicial complexes
• Evaluating visual properties via robust HodgeRank
• On the evolution of topology in dynamic clique complexes
• Random Simplicial Complexes
• First Betti number of the path homology of random directed graphs
• Topology of clique complexes of line graphs
• Maximal persistence in random clique complexes
• Markovian approach to tackle competing pathogens in simplicial complex
• Sharp vanishing thresholds for cohomology of random flag complexes
• Large simplicial complexes: universality, randomness, and ampleness
• Multivariate central limit theorems for random clique complexes
• Large random simplicial complexes. II: The fundamental group
• The neighborhood complex of a random graph
• Comparing minimal simplicial models
• Fundamental groups of clique complexes of random graphs
• Competing spreading dynamics in simplicial complex
• Random simplicial complexes, duality and the critical dimension
• 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 graph products of finite groups are rational duality groups
• Random Čech complexes on Riemannian manifolds
• \(\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
• Random hypergraphs, random simplicial complexes and their Künneth-type formulae
• One‐sided sharp thresholds for homology of random flag complexes
• Complexity of simplicial homology and independence complexes of chordal graphs
• Flexible memory networks

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)