WorksMathematics
Collapsibility of Vietoris–Rips complexes of hypercube graphs in codimension two
Abstract
Shukla conjectured that the collapsibility number of the Vietoris-Rips complex of the -dimensional hypercube graph at scale equals for all . We prove the conjecture for and every , which gives the first known cases with beyond the cross-polytope case . Writing as the independence complex of the graph that joins two points when their Hamming distance exceeds , we construct a cover of by co-chordal subgraphs. The key general tool is the inequality that, for every graph , the -number of Bıyıkoğlu and Civan of the independence complex of , and hence the collapsibility number of that complex, is at most the co-chordal cover number of ; this strengthens Woodroofe's regularity bound. We also show, using a theorem of Alon, Jin, and Sudakov, that the induced matching number of equals for every , and that is vertex decomposable if and only if or . As consequences, we determine the top degree of nonvanishing homology and the coconnectivity of , and we prove split injectivity in top-degree integral homology. Finally, assuming a recent skew Hamming set-pair theorem of Gao and Zhao, we prove that the collapsibility number of is at most for all .