Two-point correlation function for planar Potts model

Question

Fastest known method for computing Potts model partition function (Bedini and Jacobsen's "A tree-decomposed transfer matrix for computing exact Potts model partition functions for arbitrary graphs, with applications to planar graph colourings") uses a "tree decomposition" of the square lattice. How can this method be extended to computing two-point correlation function? An obvious approach is to re-run it for every pair of vertices fixed to a particular value, but that ends up with a lot of redundant computation, is there a more efficient way?

Example splitting scheme for grid

beb0s · Answer 1 · 2010-11-15 12:13:01Z

First, what we clam is that our method is the best for arbitrary planar graphs, due to the fact that the treewidth for a planar graph of size N scales a O(N^1/2). For the particular case of the square lattice, our method is not different from the traditional TM, since a strip of width L has a tree decomposition of width L+1 which is a path decomposition.
Second, in the Fortuin Kasteleyn (FK) representation you can't really fix vertices to any particular state since the degrees of freedom sit on the bonds. Nevertheless it's known that the two point function in the state representation equals the probability of the two vertices to be connected in a FK cluster. So what one should do, perhaps, is to give a special mark to connectivity states touching the two vertices.

Andrea Bedini

1) For grids, wouldn't a more general tree decomposition be more efficient (example splitting scheme in edit)? Largest bag size is the same as in path decomposition, but there's a constant number of such bags, independent of N. 2) Computing probability of two vertices being connected for every pair of vertices seems to add an extra factor of N^2 to the computation, what I was wondering if there's a way to reduce that factor

1 Answer