Graph homomorphisms and long range action
by
Peter Winkler
Lucent Technologies/Bell Laboratories

If someone takes a walk on a bipartite graph H, then knowing where she is at time t, even when t is large, tells you something about where she was at time 0. Here's a fancy way to restate this easy fact: `if H is 2-colorable then for any t there are homomorphisms f and g from a 2-regular tree to H, and sets of nodes X and Y in the tree at distance at least t, such that no homomorphism agrees with f on X and g on Y.' We (with Graham Brightwell, London School of Economics) prove the same statement with 2's replaced by k's.

This theorem is part of a plan to study combinatorial versions of important concepts (in this case, long range order) from statistical physics. In this plan several parameters arise which view graphs as the targets, instead of the domains, of homomorphisms. We offer several results linking these concepts but we have many more questions than answers.

Date received: April 18, 2001