CS Paper Radar

A data structure for quotient flag complexes

Konstantin Sorokin, Aleksandr Levin, Maxim Beketov, Anton Ayzenberg

cs.CG math.ATcs.DS ·submitted 2026-09-26 15:53 UTC · v1

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\setminus 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.

Closest papers

Nearest neighbours by meaning across the whole index.

Diameter bounds for complexes that are close to flag or close to normal

cs.DM math.COmath.MG ·2026-11-05 ·Bruno Benedetti, Giuliamaria Menara
similarity 0.63
Abstract · 22 pages

The Hirsch problem asks how large the diameter of the dual graph of a simplicial complex can be, in terms of its number of vertices. For normal complexes, the classical bounds are the Larman-Barnette bound, which is linear for fixed dimension, the Kalai-Kleitman bound, which is quasi-polynomial, and the Adiprasito-Benedetti bound n-d, which however holds only for flag complexes. After sharpening the Larman-Barnette and the Kalai-Kleitman bounds, we study how the three bounds deteriorate when flagness or normality is weakened. We give three ways to quantify the distance from flagness, and in each case we bound the diameter in a way that interpolates between the Adiprasito-Benedetti and the Larman-Barnette bounds. We also quantify the distance from normality by a parameter q, and obtain a bound that is a polynomial of degree q in n. Finally, we conjecture a statement on flag layered families that would imply an interpolation between the Adiprasito-Benedetti and the Kalai-Kleitman bounds.

0.25

Homological Trimming and Regularity of Filtrations via Local Obstruction Modules

cs.CG cs.DSmath.AT ·2026-09-23 ·Siddharth Pritam
similarity 0.57
Abstract · 29 pages, 2 figures, 6 tables, 1 algorithm

Existing link-based combinatorial preprocessing methods speed up the computation of persistent homology by removing a vertex or edge only when its link remains a cone. We replace this condition with a quantitative homological certificate. The reduced homology of the filtered link of a generator (a vertex or edge) defines a local obstruction module whose future part describes the effect of deleting that generator. Its barcode certifies either exact deletion or an explicit bound on the bottleneck error, and a conflict colouring extends this guarantee to families of generators. Our implementation, HomTrim, removes an additional 13% to 41% of the input edges beyond domination-only preprocessing and reduces backend persistence time by factors ranging from 1.55 to 4.61 on weighted flag filtrations. The same module also yields regularity diagrams that measure how far a generator can move before becoming visible to homology, together with a multiscale stability result.

0.41

Beyond the Lower-Star Filtration: Alternative Filtration Methods for Persistent Homology

cs.LG stat.MLmath.ATstat.AP ·2026-11-06 ·Innocent Abaa, Umar Islambekov
published similarity 0.56
Abstract · This is the published version of the article. Published in *International Journal of Topology*, MDPI, DOI: 10.3390/ijt3040025. Link to the o…

In the lower-star filtration (LSF), simplices are assigned filtration values according to the maximum-vertex rule, with each simplex entering the filtration when its highest-valued vertex appears. A limitation of this construction is that some higher-dimensional simplices may enter simultaneously with their boundary faces, causing certain topological features to be filled immediately upon formation and thus not appear in the resulting persistence diagram. To address this limitation, we propose three alternative filtration methods: the \(\varepsilon\)-lower-star filtration (ELSF), the \(L_p\) filtration (LpF), and the softmax filtration (SMF). {ELSF introduces a dimension-dependent delay to the maximum-vertex rule,} allowing higher-dimensional simplices to enter the filtration after their boundary faces, whereas {LpF and SMF use aggregation functions that depend on all vertex values rather} than solely on their maximum. By modifying how filtration values are assigned, these methods allow simplices to enter the filtration more progressively, so that topological features such as loops and voids may persist over longer filtration intervals rather than being filled immediately. Consequently, the resulting persistence diagrams may include persistence features that are not observed under LSF, potentially providing useful information for distinguishing data populations. Experimental results on simulated and real-world datasets demonstrate that the proposed filtration methods are computationally efficient and can provide greater sensitivity to structural differences in the data than LSF.

0.46

Updating a Discrete Morse Vector Field for a Lower Star Filtration Vineyard

cs.CG math.AT ·2026-09-25 ·Kevin Woytowich, Nkechi Nnadi, Elizabeth Munch
similarity 0.54
Abstract

In this paper, we provide a construction of an acyclic discrete vector field that is compatible with a total order associated with a lower star filtration on a simplicial complex, called the colex vector field. We show that the colex vector field induces a filtered acyclic vector field, whose resulting Morse complex computes the persistent homology of the lower star filtration on the underlying simplicial complex. We show that the colex vector field can be recomputed quickly when the vertex function that induces the lower star filtration is modified via order-adjacent vertex swaps. We provide a framework for storing and computing the number of paths between cells in the simplicial complex, as well as a method to update these values quickly when the colex vector field changes. Finally, we provide publicly available proof-of-concept code for the ideas shown. When applying it to the Persistent Homology Transform, we show that its runtime is comparable to a more standard matrix reduction approach.

0.27

CHARM: Certified Homology-Aware Reverse-scale Mapping via Diffusion-Guided Quotient Towers

cs.LG ·2026-11-07 ·Zhe Li
benchmark similarity 0.54
Abstract

Conventional dimensionality-reduction methods optimize geometric fidelity but do not return auditable homology certificates or identify the input observations associated with nontrivial classes. Direct high-dimensional persistent-homology computation is costly, and its representatives are rarely linked to a shared planar view. We introduce Certified Homology-Aware Reverse-scale Mapping (CHARM), which augments two-dimensional coordinates with algebraically certified, sample-traceable structural records. Diffusion-guided cover proposals and homotopy-safe contractions compress the input neighborhood flag complex. A Cover Quotient Tower supports cross-scale representative tracking and exact $H_k$ certification when algebraic tests complete. Reverse-scale layout connects quotient-chain preimages to the same coordinates used for geometric exploration. Contraction preserves the input neighborhood flag-complex homotopy type; the quotient tower inherits a multiplicative 3-interleaving with coarse-hop Rips, and conditional distortion bounds connect it to original Euclidean Rips. In a fixed-seed benchmark of 22 datasets (41,637 samples), CHARM achieves the highest share of first- or second-place scores across 15 metrics. On nonsynthetic data, it ranks first or second on every metric and first on all four $H_0/H_1$ persistence-diagram metrics. CHARM couples strong nonsynthetic geometric performance with an auditable structural layer.

0.32

Dessins d'Enfants as a Topological Lens on Temporal Hypergraphs

cs.SI math.ATmath.CO ·2026-11-18 ·Mehmet Emin Aktas, Esra Akbas
theory similarity 0.52
Abstract

Hypergraphs are the natural language for group interactions, and topological data analysis has given us several ways to look at them: simplicial and cell complexes, persistent homology, and sheaves. All of these treat a hyperedge as an unordered set. In this paper, we introduce a different and, to our knowledge, new viewpoint that comes from Grothendieck's theory of dessins d'enfants and, unlike these approaches, takes into account the order in which vertices appear in each hyperedge and hyperedges appear around each vertex. A dessin is a bipartite graph drawn on a closed orientable surface. Through Walsh's classical correspondence between hypermaps and bipartite maps, every hypergraph equipped with a cyclic order of incidences at each vertex and inside each hyperedge is a dessin, and therefore determines a surface with faces and a genus. We develop this idea for temporal hypergraphs and build the surface by replaying history: incidences are added in the order in which they occurred, and each new incidence is inserted into the cyclic orders built so far, next to the earlier incidence to which it is related. We prove that every insertion either grows the hypergraph without creating a cycle, closes a cycle locally by splitting a face, or closes it globally by adding a handle; the number of independent cycles equals the number of local plus handle events, and the genus equals the number of handle events. These counts give interpretable, size-controlled measures of how a temporal hypergraph's cycles organize on a surface as it grows. We apply our method to five Stack Exchange communities and show that it separates communities that standard statistics cannot tell apart and quantifies how much the real order of interactions matters. We further discuss what the surface viewpoint adds to existing higher-order network analysis and how it opens a path toward dessin-based learning on hypergraphs.

0.34

Tree Bricks and Finite Tree Automata

cs.FL math.COmath.RT ·2026-09-18 ·Annoy Sengupta
similarity 0.51
Abstract · 10 pages

Let $Λ=KQ/I$ be a finite-dimensional zero-relation algebra. We encode Crawley--Boevey tree modules over $Λ$ by finite rooted trees labelled by arrows of $Q$ and their formal inverses, and construct a deterministic finite bottom-up tree automaton recognizing exactly these encodings. We define an accepted tree to be an automata-induced tree brick when it has no non-trivial factor--image self-overlap, and use Crawley--Boevey's graph-map basis to prove that this is equivalent to brickness of the associated tree module. We also introduce local colourings of $Q_1$ and show that the arrow alphabet can be compressed without changing the tree data, graph maps, or brick property. The optimal number of colours for such a compression is the maximum of the in-degree and out-degree of $Q$. We conclude by asking whether the tree language consisting only of bricks is regular.

0.22

When Matchgate Base Collapse Fails: A Qutrit Trichotomy and Unbounded Exact Width

cs.CC ·2026-09-06 ·Chenghua Liu, Boning Meng
similarity 0.50
Abstract

Holographic algorithms solve planar counting problems by encoding each value of a finite domain into several Boolean matchgate wires. Base collapse asks whether every exact representation can be compressed to a number of wires per edge bounded only by the domain size. Chen (STOC 2016) and Xia (STOC 2016) established broad positive collapse theorems under full-rank and related structural hypotheses. Together, these works left open whether a domain-only collapse bound survives when several locally deficient signatures must share one encoding. We resolve this open problem negatively, already on a three-state (qutrit) domain. For every $a\ge4$, we construct a five-label integer-valued qutrit language of maximum arity $a$ with an exact rational matchgate presentation, yet every exactly equivalent label-preserving presentation requires common width $Ω(2^{a/2}/a)$, even if its domain, base, tensors, and complex weights may all change. The construction avoids the usual local degeneracies, so the obstruction is genuinely simultaneous. Algebraic geometry then drives an exhaustive trichotomy explaining the boundary of collapse: the gadget closure either separates into rays, is Gaussian-mobile and collapses to width at most three, or is confined to a rigid plane-plus-ray flag containing our unbounded family. Pure-spinor geometry forces compression in the mobile case, while dimension bounds for matchgate varieties and Zariski avoidance place exact integer data outside every low-width algebraic image. Thus one geometric framework explains both why collapse occurs and why it can fail without bound.

0.19