Spring 2016

Approximately Counting Graph Homomorphisms

Monday, March 28th, 2016 9:30 am10:15 am

Add to Calendar


Calvin Lab

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.