Algebraic Methods in the Study of 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.