Talks
Spring 2016

# Approximately Counting Graph Homomorphisms

Monday, Mar. 28, 2016 9:30 am10:15 am PDT

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.