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
|
Page loaded on April 05, 2008 at 08:44 PM.
|
Copyright © 1998-99, Sara C. Billey.
All rights reserved.
|
|