A Dual to a Classical Graph Homomorphism Theorem of Lovász

Graph homomorphism is a classical object of study in structural graph theory, with applications in many areas, like constraint satisfaction and database theory.

In this talk, I will first give a short introduction into graph homomorphisms and discuss some computational aspects. Then I will present a result that is dual to a classical result of Lovász; it roughly says that every graph is uniquely described by the number of homomorphisms it has to other graphs. I will close by sketching an application of this result in counting complexity.

This is joint work with Hubie Chen.