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.
|