Lower Bounds on the Homology of Vietoris–Rips Complexes of Hypercube Graphs

期刊论文
出版模式：

开放获取
发表日期：

2024年3月4日

查看全文

Henry Adams,
Žiga Virk

摘要

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$ $Q_{n}$ be the vertex set of $2^n$ $2^{n}$ vertices in the n-dimensional hypercube graph, equipped with the shortest path metric. Let $\textrm{VR}(Q_n;r)$ $VR (Q_{n}; r)$ be its Vietoris–Rips complex at scale parameter $r \ge 0$ $r \geq 0$ , which has $Q_n$ $Q_{n}$ as its vertex set, and all subsets of diameter at most r as its simplices. For integers $r<r'$ $r < r^{'}$ the inclusion $\textrm{VR}(Q_n;r)\hookrightarrow \textrm{VR}(Q_n;r')$ $VR (Q_{n}; r) ↪ VR (Q_{n}; 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 (Q_{n}; r)$ . We provide lower bounds on the ranks of homology groups of $\textrm{VR}(Q_n;r)$ $VR (Q_{n}; r)$ . For example, using cross-polytopal generators, we prove that the rank of $H_{2^r-1}(\textrm{VR}(Q_n;r))$ $H_{2^{r} - 1} (VR (Q_{n}; r))$ is at least $2^{n-(r+1)}\left( {\begin{array}{c}n\\ r+1\end{array}}\right) $ $2^{n - (r + 1)} (\begin{matrix} n \\ r + 1 \end{matrix})$ . We also prove a version of homology propagation: if $q\ge 1$ $q \geq 1$ and if p is the smallest integer for which $\textrm{rank}H_q(\textrm{VR}(Q_p;r))\ne 0$ $rank H_{q} (VR (Q_{p}; r)) \neq 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))$ $rank H_{q} (VR (Q_{n}; r)) \geq \sum_{i = p}^{n} 2^{i - p} (\begin{matrix} i - 1 \\ p - 1 \end{matrix}) \cdot rank H_{q} (VR (Q_{p}; r))$ for all $n \ge p$ $n \geq p$ . When $r\le 3$ $r \leq 3$ , this result and variants thereof provide tight lower bounds on the rank of $H_q(\textrm{VR}(Q_n;r))$ $H_{q} (VR (Q_{n}; r))$ for all n, and for each $r \ge 4$ $r \geq 4$ we produce novel lower bounds on the ranks of homology groups. Furthermore, we show that for each $r\ge 2$ $r \geq 2$ , the homology groups of $\textrm{VR}(Q_n;r)$ $VR (Q_{n}; r)$ for $n \ge 2r+1$ $n \geq 2 r + 1$ contain propagated homology not induced by the initial cross-polytopal generators.