Enumeration of graphs on a large periodic lattice

Summary

In statistical mechanics we are interested in various problems of counting subgraphs of a periodic lattice and I shall consider the plane square lattice as an illustration. Virtually all the analytically solved problems on this lattice either involve the counting of subgraphs all of whose vertices are of even valency, or can be transformed into such problems [3]. I consider a problem to be ‘analytically solved’ if we know the limiting form of the generating function in the limiting case when the numbers and lengths of the rows become very large.

One of the main methods of handling these problems is by a matrix method [3]. The matrix describes the operation of adding a row of points to the lattice. Each row of the matrix corresponded to one of the possible configurations of vertical lines in row m of the lattice, each column of the matrix to one of the possible configurations of vertical lines in row m + 1 of the lattice. Configurations of the whole lattice are then enumerated by a high power of this matrix and the crucial problem is to determine its largest eigenvalue. For a row of n points this is a 2ⁿ × 2ⁿ matrix.

I have no brand new results to report, but I think that it will be useful to describe a method that has been used for quite a number of these problems. It was originally used by Bethe for the rather different problem of the magnetisation of a one-dimensional lattice.