From the Ising and Potts Models to the General Graph Homomorphism Polynomial

Abstract

A number of classical models in statistical physics, such as the Ising model, Potts model, and lattice gas, can be formulated in terms of the generating function for weighted versions of homo-morphisms from G to some graph H. This chapter discusses the generating polynomial for homomorphisms from a graph G to the most general weighted graph on q vertices. For a fixed q, this is an object of polynomial size which contains a wealth of information about the graph G, but as we will later show it is not a complete graph invariant. The chapter describes this generating function as a polynomial, then recalls the definitions of a number of well-known graph polynomials, and partition functions from physics, and then proceeds to study the properties and relationships of these polynomials. There has been several approaches to defining an analogue of the Tutte polynomial for directed graphs as well.

Locations

• arXiv (Cornell University) - View - PDF
• Chapman and Hall/CRC eBooks - View