Collapsibility of random clique complexes

DOI10.1016/J.DISC.2022.113267MaRDI QIDQ2111927zbMATH OpenOpenAlexFDO

Authors Greg Malen

Publication date 17 January 2023

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

random simplicial complexescollapsibilityclique complexes

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorial aspects of simplicial complexes (05E45)

Abstract: We prove a sufficient condition for a finite clique complex to collapse to a $k$-dimensional complex, and use this to exhibit thresholds for $(k+1)$-collapsibility in a sparse random clique complex. In particular, if every strongly connected, pure $(k+1)$-dimensional subcomplex of a clique complex $X$ has a vertex of degree at most $2k+1$, then $X$ is $(k+1)$-collapsible. In the random model $X(n,p)$ of clique complexes of an ErdH{o}s--R'{e}nyi random graph $G(n,p)$, we then show that for any fixed $kgeq0$, if $p=n^{-alpha}$ for fixed $1/(k+1)<alpha<1/k$, then a clique complex $Xoversetdist=X(n,p)$ is $(k+1)$-collapsible with high probability.

Recommendations

• The threshold for \(d\)-collapsibility in random complexes
• Collapsibility and vanishing of top homology in random simplicial complexes
• Topology of random clique complexes
• Topology of random 2-complexes
• Large random simplicial complexes. III: The critical dimension.

Cites work

• scientific article; zbMATH DE number 3150484 (Why is no real title available?)
• Collapsibility and vanishing of top homology in random simplicial complexes
• Fundamental groups of clique complexes of random graphs
• Limit theorems for Betti numbers of random simplicial complexes
• Sharp vanishing thresholds for cohomology of random flag complexes
• Spectral gaps of random graphs and applications
• The threshold for \(d\)-collapsibility in random complexes
• Topology of random 2-complexes
• Topology of random clique complexes

Cited in

(6)

• The threshold for \(d\)-collapsibility in random complexes
• Maximal persistence in random clique complexes
• Collapsibility of simplicial complexes of hypergraphs
• Random Graphs, Retractions and Clique Graphs
• Collapsibility and homological properties of \(\mathfrak{I}\)-contractible transformations
• The question of the collapsibility of random 3-regular graphs

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

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