Bi-Weekly Talk: Tim Seppelt: Homomorphism Tensors and Linear Equations

Wednesday, February 16, 2022, 10:30am

Location: Online session

Speaker: Tim Seppelt

 

Abstract: 

Lovász (1967) showed that two graphs $G$ and $H$ are isomorphic if and only if they are homomorphism indistinguishable over the class of all graphs, i.e. for every graph $F$, the number of homomorphisms from $F$ to $G$ equals the number of homomorphisms from $F$ to $H$. Recently, homomorphism indistinguishability over restricted classes of graphs such as bounded treewidth, bounded treedepth and planar graphs, has emerged as a surprisingly powerful framework for capturing diverse equivalence relations on graphs arising from logical equivalence and algebraic equation systems.

In this talk, a unified algebraic framework for such results is introduced by examining the linear-algebraic and representation-theoretic structure of tensors counting homomorphisms from labelled graphs. The existence of certain linear transformations between such homomorphism tensor subspaces can be interpreted both as homomorphism indistinguishability over a graph class and as feasibility of an equational system.

This is joint work with Martin Grohe and Gaurav Rattan.