10:45 am, Seminar Hall
The Lovász Vector of a Graph, with Applications to Isomorphism Testing
RWTH Aachen, Germany.
We discuss an unexpected correspondence between:
(1) counting graph homomorphisms, underlying Lovász's beautiful theory of Graph Limits;
(2) the Weisfeiler-Leman algorithm (a.k.a. colour refinement, naive vertex classification), a simple combinatorial graph isomorphism test;
(3) the linear programming formulation of the Graph Isomorphism problem.
This is joint work with Holger Dell and Martin Grohe.