MathOverflow is a question and answer site for professional mathematicians. 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

I first asked this on cstheory.SE but got no reply.

Let $P(X_i=x)$ represent probability that randomly chosen proper $q$-coloring of an $L\times L$ square grid contains color $x$ at position $i$. How do you efficiently compute $P(X_{i}=X_{j})$ for every pair $(i,j)$?

Fastest known method for counting $q$-proper colorings on grids uses tree decomposition. To extend it to this problem, one needs a set of tree decompositions so that every pair of vertices is contained in some bag. Is anything known about this problem?

Motivation: this is essentially two-point correlation function of Potts model, but also correlation function of self-avoiding walks and few other "all-pairs" problems face the same issue

share|cite|improve this question

Your Answer


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

Browse other questions tagged or ask your own question.