Graph theory and statistical physics

AbstractA graph theoretic formulation of the Ising, percolation and graph colouring problems is given, and it is shown that the solution to all three problems is derivable from the Whitney rank function.The Möbius inversion technique is illustrated in the context of the colouring problem using both the lattice of all subgraphs and the lattice of only bond closed subgraphs of a graph. It is pointed out that, in statistical mechanics, the lattice of all connected subgraphs is more useful than either of these, and its Möbius function is given. The weight factors in the resulting linked-cluster expansion of the Whitney rank function are discussed, special consideration being given to the mean number of clusters.The duality relation for the rank function is derived from Minty's theorem and the theorem is extended to enable a similar relation for the site problem to be obtained