10:45 am, Seminar Hall
The Lovász Vector of a Graph, with Applications to Isomorphism Testing
Gaurav Rattan
RWTH Aachen, Germany.
11-01-19

---

Abstract

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.