我们提出了一种基于多项式向量空间的图同构类型区分方法，这些多项式在置换下具有集合不变性（即“分离模”，为对称群的表示），灵感来源于几何复杂性理论中用于区分复杂性类的方法（Mulmuley & Sohoni, SIAM J. Comput., 2001）。我们对该方法在不同复杂性度量下区分非同构图的能力进行了表征：
-
我们展示了“支持度”为 $k$ 的分离模（每个单项式最多触及 $k$ 个顶点）等价于 $O(k)$-顶点子图的计数。这一结果严格弱于 $O(k)$-维的 Weisfeiler–Leman 方法（Fürer, ICALP '01）。
-
我们证明了对称电路大小为 $n^{\theta(k)}$ 的分离模与 $\theta(k)$-WL 等价。这一结果推广并强化了 Dawar & Wilsenach 的研究成果（CSL '18; ICALP '20; ACM Trans. Comput. Log., 2022; Theory Comput., 2025）：他们证明了这一等价关系的一个方向，而我们则推广到分离模并证明了两个方向。
-
当仅考虑分离模的重数时（如同 Mulmuley & Sohoni 在 GCT 中所提到的，而非多项式本身），我们证明了当且仅当两个图的自同构群具有不同的循环指数时，这两个图可以通过重数区分。这个结果在 GCT 的类比中是显著的，因为这是我们所知的唯一一个在对象自身的“内在”特征方面给出的通过重数区分同构类型的结果。
我们利用这一点展示，对于图而言，重数障碍优于发生障碍。我们还将不变多项式与图重构猜想以及 Forman 的“有限类型不变量”（Adv. Math., 2004）联系起来。
博主点评： 本文在图同构问题的研究中提供了新的视角，通过引入分离模的概念，显著提高了我们对图的复杂性分析能力。这不仅在理论上具有重要意义，也为未来的图算法设计提供了新的思路，值得深入关注。