A data structure for quotient flag complexes
Abstract
Vietoris-Rips filtrations, which are standard in topological data analysis, are flag complexes, and a simplex tree stores these without any attaching data. In this paper we ask what survives of this economy when a flag complex K is divided by a subcomplex A, each connected component of A being crushed to a point. Such a quotient is a CW complex whose cells are the simplices of K∖ A, but their attaching maps are no longer implicit. We show that for flag K the face order of the quotient is strictly graded exactly when A is flag, and that the surviving labelled cells are determined by those of dimension at most 3. For m-flag pairs the threshold is 2m+1, and it drops to m+2 when K is flag. The prescribed cells form a regular CW decomposition only when A is full in K. These results justify the QF-tree: a cell table that stores, for each surviving simplex, its ordered list of d+1 facets with collapsed facets flagged, indexed by a trie of quotient-vertex words. For bounded dimension its size is linear in the number of surviving simplices plus the retained provenance, and we derive and verify a simple formula for the collapsed fraction above which it is smaller than the homotopy-equivalent cone model. Because a collapse changes the attaching data only on the closed star of A, the QF-tree can also be applied locally inside a simplex tree. For a ball-shaped A in the sampled Vietoris--Rips regime the closed star is a thin shell, and the median compact budget is below the cone model at every sampled radius. An accompanying library, modelled on Gudhi, implements the QF-tree, its local variant, an editable layer with local quotient updates, gluing, disc attachment, induced maps, cup products, fundamental-group presentations and zigzag persistence, and provided experiments separate the cost of maintaining a quotient from the cost of the algebra computed on it.
Related
- Field independence of the first seven Betti numbers of flag complexes
- Diameter bounds for complexes that are close to flag or close to normal
- Quotient structure of ultrafilters
- Levine Equivalence in Aura Topological Spaces: Reachability, Alexandrov Structure, and Quotient Frames
- Carleson duality and endpoint structure of Euclidean flag Triebel--Lizorkin spaces
BibTeX
@misc{sorokin2026data,
title = {{A data structure for quotient flag complexes}},
author = {Konstantin Sorokin and Aleksandr Levin and Maxim Beketov and Anton Ayzenberg},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.32733},
eprint = {2609.32733},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.32733},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - A data structure for quotient flag complexes
AU - Konstantin Sorokin
AU - Aleksandr Levin
AU - Maxim Beketov
AU - Anton Ayzenberg
PY - 2026
DA - 2026/09/26
PB - arXiv
DO - 10.48550/arxiv.2609.32733
UR - https://arxiv.org/abs/2609.32733
AB - Vietoris-Rips filtrations, which are standard in topological data analysis, are flag complexes, and a simplex tree stores these without any attaching data. In this paper we ask what survives of this economy when a flag complex K is divided by a subcomplex A, each connected component of A being crushed to a point. Such a quotient is a CW complex whose cells are the simplices of K∖ A, but their attaching maps are no longer implicit. We show that for flag K the face order of the quotient is strictly graded exactly when A is flag, and that the surviving labelled cells are determined by those of dimension at most 3. For m-flag pairs the threshold is 2m+1, and it drops to m+2 when K is flag. The prescribed cells form a regular CW decomposition only when A is full in K. These results justify the QF-tree: a cell table that stores, for each surviving simplex, its ordered list of d+1 facets with collapsed facets flagged, indexed by a trie of quotient-vertex words. For bounded dimension its size is linear in the number of surviving simplices plus the retained provenance, and we derive and verify a simple formula for the collapsed fraction above which it is smaller than the homotopy-equivalent cone model. Because a collapse changes the attaching data only on the closed star of A, the QF-tree can also be applied locally inside a simplex tree. For a ball-shaped A in the sampled Vietoris--Rips regime the closed star is a thin shell, and the median compact budget is below the cone model at every sampled radius. An accompanying library, modelled on Gudhi, implements the QF-tree, its local variant, an editable layer with local quotient updates, gluing, disc attachment, induced maps, cup products, fundamental-group presentations and zigzag persistence, and provided experiments separate the cost of maintaining a quotient from the cost of the algebra computed on it.
ER -