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.