![Counting Complexity and Phase Transitions_hi-res logo](/sites/default/files/styles/workshop_banner_sm_1x/public/2023-01/Counting%20Complexity%20and%20Phase%20Transitions_hi-res.jpg?h=bf33d09a&itok=MrH5eN5T)
Abstract
H-colourings of a graph G (a.k.a. homomorphisms from G to H) generalise familiar proper vertex colourings of G. More than 15 years ago, Dyer and Greenhill presented a dichotomy for exactly counting H-colourings. That was for exact counting, and, even now, there is only a partial complexity classification for approximate counting. A familiar theme in the study of CSPs is that the “conservative” case is often easier to resolve. This is one reason to look at list H-colourings. The decision problem for list H-colourings was studied by Feder, Hell and Huang, who proved a dichotomy result. In this talk, I’ll present a classification for the problem of approximately counting list H-colourings of a graph, and briefly consider weighted variants.
This is joint work with Andreas Galanis and Leslie Ann Goldberg (Oxford), and others.