On weighted graph homomorphisms

Abstract

For given graphs G and H, let |Hom(G, H)| denote the set of graph homomorphisms from G to H. We show that for any finite, n-regular, bipartite graph G and any finite graph H (perhaps with loops), |Hom(G, H)| is maximum when G is a disjoint union of K n,n 's.This generalizes a result of J. Kahn on the number of independent sets in a regular bipartite graph.We also give the asymptotics of the logarithm of |Hom(G, H)| in terms of a simply expressed parameter of H.We also consider weighted versions of these results which may be viewed as statements about the partition functions of certain models of physical systems with hard constraints.

Locations

• DIMACS series in discrete mathematics and theoretical computer science - View
• arXiv (Cornell University) - View - PDF
• CiteSeer X (The Pennsylvania State University) - View - PDF