Seminar in Discrete Mathematics - Alexander Gavrilyuk

This week's seminar is given by Alexander Gavrilyuk, Shimane University, Matsue, Japan.

Title: An algebraic approach to the graph isomorphism problem

Abstract: I will introduce the d-dimensional Weisfeiler-Leman (d-dim WL) algorithm, a powerful heuristic tool for solving the graph isomorphism problem, and a related matrix algebra, which allows one to study the output of the algorithm. When restricted to some natural graph classes, the d-dim WL often serves as a complete graph isomorphism test. If time permits, I will discuss some applications and possible research directions.