SUMMARY

This article is another attempt to reconcile part of graph theory and part of theoretical physics. Specifically, we shall discuss some aspects of the reconstruction problem in terms of simple models of physical phenomena. A previous essay in the same vein (Biggs 1977a, henceforth referred to as IM) may be consulted for background information and proofs of some basic theorems.

There are four sections: (1) Interaction Models, (2) the Algebra of Graph Types, (3) Reconstruction, (4) Partition Functions for Infinite Graphs.

INTERACTION MODELS

Definitions

Let G be a finite (simple) graph, with vertex set V and edge-set E. An ‘interaction model’ on G arises when the vertices of G may have certain attributes, and they interact along the edges according to the values of those attributes. To be more precise, let A denote a finite set of objects (attributes), and define a state on G to be a function ω: V → A. In graph theory, we often think of the attributes as colours, so that a state is a colouring. In theoretical physics, the vertices represent particles of some kind, and the attributes represent some physical property, such as a magnetic moment.

The interaction between a pair of adjacent vertices is measured by a real-valued function i, called the interaction function, defined on the set A(2) of unordered pairs of attributes. That is, i{a1,a2) measures the interaction between a pair of vertices when they are joined by an edge and they have attributes a1 and a2. An interaction model M is a pair (A,i), where A is a finite set and i is an interaction function.