Tue, 2 March 2021, 1 pm MST
We give a survey on connections between Graph Isomorphism, the CSP, and counting homomorphisms. In the first part we give a brief review of the main approaches to solving the Graph Isomorphism problem and make some observations on how the CSP techniques can be helpful. In the second part we focus on relaxations of graph isomorphisms and how they can be characterized using the numbers of homomorphisms from various graph classes.
[video]