## PIMS - SFU Discrete Math Seminar: Andrei Bulatov

• Date: 11/09/2021
• Time: 14:30
Lecturer(s):
Andrei Bulatov, SFU
Location:

Simon Fraser University

Topic:

The Complexity of Counting Homomorphisms

Description:

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