<p>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</p>

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

<p>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$</p>

<p>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?</p>

CC BY-SA 2.5
2011-02-04T10:09:57.493Z
Is J symmetric? It seems like it should be for the Ising model, but maybe I've misunderstood.
Joe Fitzsimons
CC BY-SA 2.5
2011-02-05T21:56:20.553Z
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  -- http://cstheory.stackexchange.com/questions/3931/algorithms-for-the-2-dimensional-planar-ising-model-over-directed-graphs/3980#3980
Yaroslav Bulatov
CC BY-SA 2.5
2011-02-06T09:38:36.697Z
Ah, I see. Sorry, I should have picked up on that.
Joe Fitzsimons
<ds.algorithms><graph-theory><co.combinatorics><statistical-physics>
Ising Model and Eulerian Subgraphs
Yaroslav Bulatov
# Ising Model and Eulerian Subgraphs

(Asked by: username_0 on 2010-12-28)

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?

**Tags:** ds.algorithms, graph-theory, co.combinatorics, statistical-physics
> **Comments:**
> **username_1**: Is J symmetric? It seems like it should be for the Ising model, but maybe I've misunderstood.  
> **username_0**: 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  -- http://cstheory.stackexchange.com/questions/3931/algorithms-for-the-2-dimensional-planar-ising-model-over-directed-graphs/3980#3980  
> **username_1**: Ah, I see. Sorry, I should have picked up on that.  

---

## 0 answers

