Physics Stack Exchange is a question and answer site for active researchers, academics and students of physics. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
Have you tried writing to Bedini and Jacobsen? – j.c. Nov 12 '10 at 14:26
yes ''''''''''' – Yaroslav Bulatov Nov 12 '10 at 19:55
  • 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

share|cite|improve this answer
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 – Yaroslav Bulatov Nov 18 '10 at 4:29

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.