Lower Bounds on the Homology of Vietoris–Rips Complexes of Hypercube Graphs
Henry Adams, Žiga Virk · Bulletin of the Malaysian Mathematical Sciences Society · 2024
Abstract We provide novel lower bounds on the Betti numbers of Vietoris–Rips complexes of hypercube graphs of all dimensions and at all scales. In more detail, let $$Q_n$$ Qn be the vertex set of $$2^n$$ 2n vertices in then-dimensional hypercube graph, equipped with the shortest path metric. Let $$\textrm{VR}(Q_n;r)$$ VR(Qn;r) be its Vietoris–Rips complex at scale parameter $$r \ge 0$$ r≥0 , which has $$Q_n$$ Qn as its vertex set, and all subsets of diameter at mostras its simplices. For integers $$r r<r′ the inclusion $$\textrm{VR}(Q_n;r)\hookrightarrow \textrm{VR}(Q_n;r')$$ VR(Qn;r)↪VR(Qn;r′) is nullhomotopic, meaning no persistent homology bars have length longer than one, and we therefore focus attention on the individual spaces $$\textrm{VR}(Q_n;r)$$ VR(Qn;r) . We provide lower bounds on the ranks of homology groups of $$\textrm{VR}(Q_n;r)$$ VR(Qn;r) . For example, using cross-polytopal generators, we prove that the rank of $$H_{2^r-1}(\textrm{VR}(Q_n;r))$$ H2r-1(VR(Qn;r)) is at least $$2^{n-(r+1)}\left( {\begin{array}{c}n\\ r+1\end{array}}\right) $$ 2n-(r+1) n r+1 . We also prove a version ofhomology propagation: if $$q\ge 1$$ q≥1 and ifpis the smallest integer for which $$\textrm{rank}H_q(\textrm{VR}(Q_p;r)) e 0$$ rankHq(VR(Qp;r))≠0 , then $$\textrm{rank}H_q(\textrm{VR}(Q_n;r)) \ge \sum _{i=p}^n 2^{i-p} \left( {\begin{array}{c}i-1\\ p-1\end{array}}\right) \cdot \textrm{rank}H_q(\textrm{VR}(Q_p;r))$$ rankHq(VR(Qn;r))≥∑i=pn2i-p i-1 p-1 ·rankHq(VR(Qp;r)) for all $$n \ge p$$ n≥p . When $$r\le 3$$ r≤3 , this result and variants thereof provide tight lower bounds on the rank of $$H_q(\textrm{VR}(Q_n;r))$$ Hq(VR(Qn;r)) for alln, and for each $$r \ge 4$$ r≥4 we produce novel lower bounds on the ranks of homology groups. Furthermore, we show that for each $$r\ge 2$$ r≥2 , the homology groups of $$\textrm{VR}(Q_n;r)$$ VR(Qn;r)