Algebraic Graph Theory Seminar - Ján Pastorek (12.12.2025)
Friday 12.12.2025 at 13:15, Lecture room M VIII (online too)
Ján Pastorek:
Forth from Extensions of Partial Automorphisms to the Weisfeiler - Leman Algorithm & Counting Logic & Bijective Pebble Games and Back Again
Abstract:
The graph isomorphism (GI) problem sits in an unresolved position between P and NP-complete and is polynomially equivalent to computing an orbit partition of a graph’s automorphism group. The Weisfeiler–Leman (WL) algorithm is a central combinatorial method for isomorphism testing that iteratively aggregates local neighbourhood information to approximate this orbit structure. A partial automorphism of a graph is an isomorphism between induced subgraphs of a graph. The set of all partial automorphisms under composition and inverses forms a partial automorphism inverse monoid which encodes complete algebraic information.
In this talk, we discuss how these viewpoints of WL and partial automorphisms can be related. In particular, we review four different but equivalent perspectives on WL and show how they interact. After reviewing the necessary background, we revisit the k-dimensional WL algorithm and its logical characterization via bijective pebble games. From duplicator strategies in the bijective k-pebble game played on two copies of the same graph, one can collect all pebbled positions into a set of partial automorphisms of rank at most k. Among others, this set inherits back-and-forth extension properties from the underlying game.