TIME: 1:30-2:20 pm, May 6, 2008

PLACE: CSE 503

SPEAKER: Rekha Thomas
         Dept of Mathematics
         University of Washington

TITLE: Counting Graph Homomorphisms

ABSTRACT:

A graph homomorphism between two finite graphs F and G is an adjacency
preserving map from the vertex set of F to the vertex set of G. Many
important properties of graphs can be expressed in terms of graph
homomorphisms. For instance, F is 4-colorable if and only if there is
a homomorphism from F into the complete graph on four nodes.  Let
hom(F,G) denote the number of homomorphisms from F to G. For G fixed,
hom(--,G) is a graph parameter on finite graphs. Freedman, Lovasz and
Schrijver have recently characterized those graph parameters that are
of the form hom(--,G) for a fixed G.  This is an expository talk on
this result which is part of a very large body of recent work on this
topic due to many people including Freedman, Lovasz, Schrijver, Borgs,
Chayes, Sos, Szegedy, Vesztergombi and others. It is also a repeat of
the talk in the Math Combinatorics Seminar at UW on April 16.