|
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. These hom-functions play an important role in many
applications like statistical physics, modeling the internet and extremal graph theory.
For G fixed and F varying, hom(F,G) is a graph parameter on finite graphs. Freedman, Lovasz and
Schrijver have recently characterized those graph parameters that are hom-functions.
This involves algebra and representation theory and a notion of graph algebras.
Every graph G has a hom-profile which is the infinite vector (hom(F,G)) as F varies over all finite graphs
ordered in some way. These profiles allow a definition of distance between two graphs which makes
the set of all graphs into a metric space. These analytic ideas lead to interesting notions of limits of
graph sequences with further applications. I will attempt to survey this work on graph homomorphisms
due to several people such as Borgs, Chayes, Freedman, Lovasz, Schrijver, Sos, Szegedy
and Vesztergombi.
|