UW Combinatorics Seminar

Counting Graph Homomorphisms

Rekha Thomas

University of Washington

April 16, 4:00pm
Padelford C-401

refreshments at 3:30pm
Pre-Seminar at 2:30pm in Padelford C-401

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. The proof involves a surprising connection to finite dimensional algebras and their idempotents. I will attempt to give 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.


Speaker's Contact Info: http://www.math.washington.edu/~thomas/


Return to seminar home page

Combinatorics Seminar, Mathematics Department, University of Washington, billey@math.washington

Page loaded on April 05, 2008 at 08:44 PM. Copyright © 1998-99, Sara C. Billey. All rights reserved.