Collapsibility of random clique complexes

DOI10.1016/J.DISC.2022.113267zbMATH Open1506.05226arXiv1903.05055OpenAlexW2920847275MaRDI QIDQ2111927FDOQ2111927

Authors: Greg Malen 

Publication date: 17 January 2023

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

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.

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

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.

zbMATH Keywords

random simplicial complexescollapsibilityclique complexes

Mathematics Subject Classification ID

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

Cites Work

• Topology of random clique complexes
• Limit theorems for Betti numbers of random simplicial complexes
• Title not available (Why is that?)
• Sharp vanishing thresholds for cohomology of random flag complexes
• Topology of random 2-complexes
• Collapsibility and vanishing of top homology in random simplicial complexes
• The threshold for \(d\)-collapsibility in random complexes
• Spectral gaps of random graphs and applications
• Fundamental groups of clique complexes of random graphs

Cited In (5)

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

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)