Complete Low-Degree Magnitude-Homology Signatures in Fixed Windows for Finite Graphs

技术摘要：有限图在固定窗口内的低阶量级同调完整签名

问题陈述
量级同调（Magnitude homology）是有限图的一种双分次整数不变量，提供了量级不变量（magnitude invariant）的范畴化。尽管在理论上具有强大的威力，但精确计算整数量级同调群在计算上非常昂贵，特别是由于潜在的扭类（torsion）的存在，使得仅靠秩表（rank tables）无法替代完整的整数数据。本文解决了两个具体的计算问题：

1. 是否可以通过结合直接整数计算与标准图族的精确公式，来确定声明的二度窗口内每一个请求的整数量级同调群？
2. 当将整数签名简化为秩签名（仅自由秩）或支撑签名（仅零与非零）时，会损失多少判别信息？

方法论
作者开发了一个精确的整数同调框架，用于计算固定窗口 $W(K, L) = \{(k, l) : 0 \le k \le K, 0 \le l \le L\}$ 内的量级同调群 $MH_{k,l}(G)$。该方法依赖于三个核心组件：

1. 连续边界矩阵： 对于固定的二度 $(k, l)$，该方法构造边界矩阵 $A = D_{k,l}$ 和 $B = D_{k+1,l}$，代表链群之间的映射。目标群被定义为 $\ker(A) / \text{im}(B)$。
2. 精确整数线性代数： 计算利用了整数上的 Hermite 标准型（HNF）和 Smith 标准型（SNF）。
   • 通过对 $A$ 计算 HNF 来导出 $\ker(A)$ 的整数基。
   • 使用该基将 $B$ 转换为矩阵 $Q$。
   • 对 $Q$ 进行 SNF 运算以得出不变因子，从而确定群结构为直和形式（$\mathbb{Z}^r \oplus \bigoplus \mathbb{Z}/d_i\mathbb{Z}$）。
   • 计算使用 python-flint（FLINT 库）进行，并使用 SymPy 实现进行了验证。
3. 混合计算策略：
   • 直接计算： 用于大多数情况，特别是针对连通无标签图的数据集。
   • 闭式公式： 对于标准族（树、完全图、完全二部图、圈），作者利用现有的公式（Hepworth 和 Willerton；Gu）来填补空白或验证结果。
   • 验证： 两种方法在重叠的二度上进行了交叉验证，显示出完全一致的结果。

数据集与范围
本研究侧重于特定窗口内的两个不同数据集：

• 标准图族： 分析了 63 个选定实例（包括路径、圈、星图、完全图、双星图及各类树），分析窗口为 $W(5, 10)$。
• 连通无标签图： 分析了所有 996 个具有最多 7 个顶点的连通无标签简单图，分析窗口为 $W(3, 6)$。

主要结果

1. 完备性： 该框架成功解决了所有请求的群。
   • 标准族： $W(5, 10)$ 中的所有 4,158 个群均已解决（其中 3,618 个通过直接计算，540 个通过闭式公式）。
   • 小规模图： 996 个图中所有的 27,888 个群均通过直接计算在 $W(3, 6)$ 中得到解决。
2. 判别能力： 研究比较了具有相同“普通轮廓”（顶点数、边数、度序列、直径、圈数、圈秩、二部性及三角形计数）的非同构图对。在 7 顶点数据集中共有 564 对这样的图对。
   • 秩 vs. 整数： 秩签名与全整数签名在区分图对的能力上是相同的；两者都区分了 434 对图。
   • 支撑签名： 支撑签名（仅零/非零）仅区分了 89 对图。
   • 多重性贡献： 秩/整数区分度（434）与支撑区分度（89）之间的差异表明，有 345 对 图是专门通过同调群的多重性（秩）而非仅仅通过其存在性来区分的。
3. 扭类： 在计算的这些数据集和窗口内，未观察到扭类因子。所有解析出的群均为自由阿贝尔群。

意义与主张
本文声称提供了这些特定图集的低阶整数量级同调签名的第一个完整数据集。其主要贡献在于证明了：

• 结合 HNF/SNF 与族公式的精确计算框架在解决固定窗口内的整数群方面是可行的。
• 整数签名（以及由其衍生的秩签名）比支撑签名具有显著更高的判别力，能够区分具有相同普通轮廓的图。
• 同调群的“多重性”是区分有限图的关键不变量，这些图无法被标准图不变量所区分。

作者明确指出了局限性：结果仅限于指定的窗口内，并不构成对有限图的完整分类。在计算的数据集中未观察到扭类，这受限于计算范围，同时也承认在这些特定参数之外，量级同调中已知存在扭类。剩余的 130 对无法区分的图对为未来更大窗口的比较设定了目标。