Algebraic Methods in the Study of Graph Isomorphism

图同构研究中的代数方法

• 批准号: 2119781
• 金额: --
• 依托单位: University of Cambridge
• 依托单位国家: 英国
• 项目类别: Studentship
• 财政年份: 2018
• 资助国家: 英国
• 起止时间: 2018 至 无数据
• 项目状态: 已结题
• 来源: https://gtr.ukri.org/projects?ref=studentship-2119781
• 关键词: Algebraic; Methods; Study; Graph; Isomorphism

The aim of this project is to understand the complexity of the graph isomorphism problem.We aim to understand the limitations of well known polynomial time algorithms which constitute an approximation to the problem. The Weisfeiler-Leman and invertible map tests are two well known ones. Whilst the former has been well studied, the latter has many related open questions. For instance, how does this test behave over finite fields?Is this the best polynomial approximation of graph isomorphism? We would also like to relate this to known quantum graph invariants, such as the k-boson invariant and the quantumisomorphism game. We conjecture that there is an extension of the latter which forms an invariant which is stronger than Weisfeiler-Leman.Our project is based on previous work by Bjarki Holm, Anuj Dawar and Simone Severini. Most of this work was formulated in terms of logic and pebble games on graphs. We aim to formulate our ideas (as well as their previous work) in terms of algebras from graphs, permutation groups and combinatorics so as to make it more accessible to scientists from a more general background.

这个项目的目的是了解图同构问题的复杂性。我们的目标是了解众所周知的多项式时间算法的局限性，构成了一个近似的问题。Weisfeiler-Leman和可逆映射检验是两个著名的检验。虽然前者已经得到很好的研究，但后者有许多相关的开放问题。例如，这个测试在有限域上是如何表现的？这是图同构的最佳多项式逼近吗？我们还想把它与已知的量子图不变量联系起来，比如k玻色子不变量和量子同构博弈。我们猜想，有一个扩展的后者形成的不变量是强于Weisfeiler-Leman.Our项目是基于以前的工作由Bjarki霍尔姆，Anuj Dawar和西蒙Severini。大部分工作都是用逻辑和图上的卵石游戏来表述的。我们的目标是制定我们的想法（以及他们以前的工作）在代数从图，置换群和组合学，使其更容易从一个更一般的背景科学家。

项目成果

Variations on the Theme of Higher Dimensional Weisfeiler-Leman Algorithms

高维 Weisfeiler-Leman 算法主题的变奏

• DOI: 10.17863/cam.95245
• 发表时间: 2021
• 作者: Vagnozzi D

Generalizations of k-dimensional Weisfeiler-Leman stabilization

k 维 Weisfeiler-Leman 稳定性的推广

• DOI: 10.2140/moscow.2020.9.229
• 发表时间: 2020
• 期刊: Moscow Journal of Combinatorics and Number Theory
• 作者: Dawar A