Nerve Models of Subdivision Bifiltrations

We study the size of Sheehy's subdivision bifiltrations, up to homotopy. We focus in particular on the subdivision-Rips bifiltration SR(X) of a metric space X, the only density-sensitive bifiltration on metric spaces known to satisfy a strong robustness property. Given a simplicial filtration F with a total of m maximal simplices across all indices, we introduce a nerve-based simplicial model for its subdivision bifiltration SF whose k-skeleton has size O(mᵏ⁺¹). We also show that the $0$-skeleton of any simplicial model of SF has size at least m. We give several applications: For an arbitrary metric space X, we introduce a √2-approximation to SR(X), denoted J(X), whose k-skeleton has size O(|X|ᵏ⁺²). This improves on the previous best approximation bound of √3, achieved by the degree-Rips bifiltration, which implies that J(X) is more robust than degree-Rips. Moreover, we show that the approximation factor of √2 is tight; in particular, there exists no exact model of SR(X) with poly-size skeleta. On the other hand, we show that for X in a fixed-dimensional Euclidean space with the ₚ-metric, there exists an exact model of SR(X) with poly-size skeleta for p∈ \1, ∞\, as well as a (1+ε)-approximation to SR(X) with poly-size skeleta for any p ∈ (1, ∞) and fixed ε > 0.