Let $\mathcal{X}= \{1,-1\}^n$, $E$ the set of edges and $J$ some real-valued matrix. Van der Waerden's theorem gives constant $c$ and set of edge weights such that

$$\sum_\mathbf{x\in \mathcal{X}} \exp \sum_{ij \in E} J_{ij} x_i x_j = c \sum_{A\in C} f(A) $$

Where $C$ consists of Eulerian subgraphs over $E$, $f(A)$ is the weight of $A$ defined as the product of weights of edges in $A$

Edge weights are strictly below 1 in magnitude. Suppose only a small number of self-avoiding loops on the graph have non-negligible weight. We can approximate the sum by only considering Eulerian subgraphs including these loops. However, a small number of such loops can give a large number of Eulerian subgraphs. Is there a more efficient way?

  • $\begingroup$ Is J symmetric? It seems like it should be for the Ising model, but maybe I've misunderstood. $\endgroup$ – Joe Fitzsimons Feb 4 '11 at 10:09
  • $\begingroup$ The term inside exp is a quadratic form so it doesn't matter if J is symmetric. If J is not symmetric, it can be rewritten in terms of another matrix which is -- cstheory.stackexchange.com/questions/3931/… $\endgroup$ – Yaroslav Bulatov Feb 5 '11 at 21:56
  • $\begingroup$ Ah, I see. Sorry, I should have picked up on that. $\endgroup$ – Joe Fitzsimons Feb 6 '11 at 9:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.