PIMS - SFU Discrete Math Seminar: Andrei Bulatov

  • Date: 11/09/2021
  • Time: 14:30
Andrei Bulatov, SFU

Simon Fraser University


The Complexity of Counting Homomorphisms


The Constraint Satisfaction Problem (CSP) provides a general framework for a wide range of combinatorial problems. The simplest way to state the problem is: Given relational structures (say, graphs) G and H, decide if there is a homomorphism from G to H. The counting version of the CSP, #CSP, asks for the number of such homomorphisms. In order to represent specific problems, the CSP is often restricted in various ways, in particular by fixing the target structure H. Thus, CSP(H) asks if, for a given structure G, there is a homomorphism from G to H. If H is a graph such a problem is often called H-Coloring. The counting versions #CSP(H), #H-Coloring of these problems are defined accordingly.


In this talk we survey the developments in the study of the complexity of #CSP(H) that eventually led to a complete classification of such problems and their various generalizations.

Other Information: 

This is an in-person event with the option of online attendance.


In-person Location: K9509, SFU
There is a limit of 15 people for in-person attendance. Drop by and say hi and to grab a cup of coffee.


Online link: https://www.sfu.ca/math.html

Scroll to the calendar at the bottom of the page to select the event date. Zoom information can be found in event description.


Or https://www.sfu.ca/math/research/discrete-mathematics/discrete-math-seminars.html