技术摘要：商标旗复形（Quotient Flag Complexes）的数据结构

1. 问题陈述

在拓扑数据分析（TDA）中，Vietoris–Rips 过滤是标准的工具，通常以标量复形（flag complexes）的形式表示。**单纯形树（simplex tree）**是此类复形的主流数据结构，因为它利用了标量复形的存储经济性：标量复形完全由其 1-骨架（即由边组成的图）决定，这意味着每个单纯形都由其顶点唯一确定，无需存储显式的附着数据。

本文探讨了当标量复形 $K$ 被子复形 $A$ 除时，这种存储经济性会发生什么变化。具体而言，本文研究了分量逐个商（componentwise quotient） $K/SCA$，即其中每个连通分支都被压缩为一个不同的点。虽然所得空间是一个 CW 复形，但商运算破坏了原始标量复形中隐含的附着映射性质：

• 一个端点位于同一压缩分支内的存留边会变成一个环（loop）。
• 一个有两个边位于 $A$ 中的存留三角形会沿单条边进行附着。
• 商空间通常不是标量复形，且其拓扑不再仅由其低维骨架（1-骨架或 2-骨架）决定。

核心问题包括：

1. Q1： 哪些标量树结构可以存留？阶序是否仍然是严格分级的（strictly graded）？能否仅使用余维数为一的数据来记录附着映射？
2. Q2： 确定该商空间所需的最小骨架是什么，从而允许丢弃更高维度的记录？

2. 方法论与理论框架

2.1. 装饰（The Decoration $D(K, A)$）

作者引入了一个称为装饰的数学对象，记作 $D(K, A)$。这是一个有基点的半单纯集（pointed semisimplicial set），其中：

• **真实单元（Genuine cells）**对应于 $K \setminus A$ 中的单纯形。
• **基点（Basepoints）**对应于 $A$ 的连通分支（记作 $\perp_\alpha$）。
• 面映射（Face maps）被修改： 如果一个存留单元的单纯形面（facet）完全位于某个坍缩的分支 $A_\alpha$ 内，则该面映射指向相应的基点 $\perp_\alpha$；否则，它指向存留的单纯形面。

该装饰的实现 $|D(K, A)|_\bullet$ 自然地同胚于分量逐个商 $|K|/SCA$。

2.2. 结构性质

论文分析了子复形 $A$ 相对于 $K$ 的两个关键性质：

• 标量性（Flagness）： $A$ 是否为标量复形（由其 1-骨架决定）。
• 充分性（Fullness）： $A$ 在 $K$ 中是否是充分的（即 $A$ 是否包含了由其顶点所张成的所有 $K$ 的单纯形）。

作者证明了这些性质控制着商空间的结构完整性：

• 严格分级性（Strict Gradedness）： 商空间的阶序是严格分级的（没有秩跳跃）当且仅当 $A$ 是标量复形。如果 $A$ 不是标量复形，一个存留的单纯形可能其整个边界都坍缩到基点，从而在偏序集中产生“跳跃”。
• 正则性（Regularity）： 商空间具有正则 CW 分解（即特征映射是球面的同胚）当且仅当 $A$ 的每个连通分支在 $K$ 中都是充分的。作者提供了一个显式的凸模型来证明充分性，避免了依赖于同调或可收缩性测试，因为后者无法在此语境下区分球体与球面。

2.3. 骨架确定性（Skeletal Determinacy）

论文研究了必须存储多少商空间信息才能重建其余部分。

• 对于标量坍缩（flag collapses）（即 $A$ 是标量复形），商空间由其维度至多为 3 的单元决定。
• 对于 $m$-标量对（$m$-flag pairs）（其中最小非面最多包含 $m+1$ 个顶点），阈值为 $2m+1$。
• 如果环境复形 $K$ 是标量复形，该阈值降至 $m+2$。
• 至关重要的是，对于一般的粘合（gluings）（通过仿射映射识别单纯形），不存在任何有限的骨架足以确定商空间；必须需要完整的识别数据。

3. 核心贡献：QF-树（The QF-Tree）

基于这些理论结果，作者提出了 QF-树（Quotient Flag tree），这是一种旨在高效存储商标量复形的数据结构。

3.1. 结构

QF-树由以下部分组成：

1. 单元表（Cell Table）： 存储每个存留的单纯形。对于每个 $d$-单元，它存储一个有序的 $d+1$ 个面（facets）列表。至关重要的是，已被坍缩的面会被标记（flagged）为对应连通分支点（$\perp_\alpha$）的标识符，而非更低维度的单元。
2. 词树（Word Trie）： 单元表之上的索引。对于一个源单纯形，其“单词”是其顶点图像（连通分支点或原始顶点）的排序列表。这允许高效查找，尽管多个不同的单元可能会共享相同的单词（这与标准的单纯形树不同）。

3.2. 存储效率

论文推导了 QF-树与锥模型（cone model）（另一种通过向每个 $A$ 的连通分支附加一个锥来保持同伦型的方案）之间的存储交叉点。

• 令 $\alpha = |A|/|K|$ 为坍缩单纯形的比例。
• 令 $s$ 为存留单元的平均面数。
• 当 $\alpha > \frac{s-1}{s+1}$ 时，QF-树比锥模型更小。
• 对 Vietoris–Rips 复形的实验表明，在典型参数下，这种交叉发生在坍缩比例约为 0.3 到 0.7 左右。

3.3. 局部应用（闭星形 Closed Star）

意识到坍缩仅改变 闭星形（closed star） $A$ 内部的附着数据，作者提出了 QF-树的局部变体。

• QF-树仅针对 $A$ 的闭星形（即“星形”和“前沿”单纯形）进行构建。
• 其余部分保留在原始的单纯形树中。
• 这种“紧凑”表示法比重建整个商空间要高效得多，尤其是在坍缩区域相对于整个复形较小时。

4. 结果与实验验证

4.1. 理论结果

• 定理 4.2： 商空间阶序的严格分级性成立，当且仅当 $A$ 是标量复形。
• 定理 5.4 & 5.5： 确立了骨架确定性的精确阈值（标量情形为 3，$m$-标量情形为 $2m+1$，若 $K$ 为标量则为 $m+2$）。
• 定理 6.4： 商空间 CW 分解的正则性成立，当且仅当 $A$ 的每个连通分支在 $K$ 中是充分的。
• 命题 5.8： 粘合过程无法由任何有限骨架确定。

4.2. 软件实现

作者实现了一个名为 qfcore 的库（基于 C++17 并提供 Python 接口），其模型参考了 Gudhi API。功能包括：

• 不可变的 QF-树构建。
• 局部闭星形变体。
• 支持点粘合、多边形盘附着及诱导映射的可编辑层。
• 计算上同调环（带有杯积）、基本群表示以及交错持久性（zigzag persistence）。

4.3. 实验发现

• 存储： 当坍缩比例超过推导出的阈值时，QF-树明显小于锥模型。在采样机制下（点云中的球形 $A$），在每个采样半径下，紧凑预算的中位数均低于锥模型。
• 计算速度：
  • 单次相对同调： 直接计算相对边界矩阵（由 Gudhi 计算）比构建 QF-树更快。
  • 迭代操作： 维护局部商空间的成本比重建整个商空间要低 1 到 3 个数量级。
  • 上同调环： 从保留的商空间计算上同调环比从源三角剖分计算要快数倍。
  • 交错持久性： 该库成功地与 Gudhi 的流式交错引擎集成，将维护商空间的成本与代数计算的成本分离。

5. 意义与局限性

意义

论文证明了 QF-树作为处理商标量复形工作流中必要结构的合理性。它表明，虽然标量复形的“经济性”（由 1-骨架决定）虽然丧失了，但仍存在一种结构化的经济性：

• 附着映射可以仅使用余维数为一的数据（通过标记/flags）进行存储。
• 结构由低维骨架决定（标量情形下维度为 3）。
• 局部更新在计算上是可行的，这使得在涉及坍缩子复形的复杂过滤过程中进行动态分析成为可能。

局限性

作者明确指出了以下约束：

• 标记（Labeling）： 重建定理假设存在固定的顶点集和标记对。目前尚不清楚无标签截断是否能一般性地确定同构意义下的商空间。
• 粘合（Gluing）： 该库支持点粘合和盘附着，但不支持任意的仿射识别或置换粘合，后者需要每个面（facet）都有完整的顶点双射。
• 存储开销： 如果商空间单元极少（例如，坍缩一条长路径后只剩一个单元但保留了所有顶点标签），则源标签和溯源信息可能会占据主导地位。
• 同调更新： 局部拓扑更新并不增量地维护同调基（homology bases）；基的构建仍然是一个主要的成本。
• 通用性： 仅当维度有界时，存储界限才与单元数量呈线性关系；对于高维复形，面引用可能会呈超线性增长。

总之，本文为处理商标量复形的 TDA 工作流提供了严谨的理论基础和实用的数据结构，弥补了标量复形的效率与坍缩子复形在拓扑上的必要性之间的鸿沟。