betaFeedback

WorksMathematics

Collapsibility of Vietoris–Rips complexes of hypercube graphs in codimension two

Abstract

Shukla conjectured that the collapsibility number of the Vietoris-Rips complex VR(In;r)\mathrm{VR}(I_n;r) of the nn-dimensional hypercube graph at scale rr equals 2r2^r for all n≥r+1n\ge r+1. We prove the conjecture for n=r+2n=r+2 and every rr, which gives the first known cases with r≥4r\ge 4 beyond the cross-polytope case n=r+1n=r+1. Writing VR(In;r)\mathrm{VR}(I_n;r) as the independence complex of the graph Hn,rH_{n,r} that joins two points when their Hamming distance exceeds rr, we construct a cover of Hr+2,rH_{r+2,r} by 2r2^r co-chordal subgraphs. The key general tool is the inequality that, for every graph GG, the θθ-number of Bıyıkoğlu and Civan of the independence complex of GG, and hence the collapsibility number of that complex, is at most the co-chordal cover number of GG; this strengthens Woodroofe's regularity bound. We also show, using a theorem of Alon, Jin, and Sudakov, that the induced matching number of Hn,rH_{n,r} equals 2r2^r for every n>rn>r, and that VR(In;r)\mathrm{VR}(I_n;r) is vertex decomposable if and only if r=1r=1 or n=r+1n=r+1. As consequences, we determine the top degree of nonvanishing homology and the coconnectivity of VR(Ir+2;r)\mathrm{VR}(I_{r+2};r), 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 VR(In;r)\mathrm{VR}(I_n;r) is at most 2r+1−42^{r+1}-4 for all n>r≥2n>r\ge 2.

Paper details

vlnc:W_4be4nv8n
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 2

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

OpenAI’s ChatGPT

View statement
Looking for related papers…