![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
A homomorphism from a graph G to a graph H is a map from the vertices of G to the vertices of H that maps every edge of G to an edge of H. Graph homomorphisms capture many interesting combinatorial structures such as independent sets and proper colourings. This talk addresses the ``the classification program of counting complexity'' as it applies to the problem of approximately counting graph homomorphisms.
It includes recent work with Andreas Galanis and Mark Jerrum.