# Algorithms for the 2 Dimensional Planar Ising Model over Directed Graphs

Kastelyn in the 1960's continuing Onsanger's work on the Ising model, found combinatorial solutions to the 2 dimensional planar Ising model. This was for undirected graphs.

Has a similar algorithm been found for planar directed graphs?

To clarify what I mean, although there are several different ways one could generalise the planar Ising model to directed graphs, I have in the mind the following:

The 2-local term in the standard Ising model is the symmetric matrix $J_{ij}$. The directed graph would be represented by unsymmetric matrix $J_{ij}$! So the sum over the partition function would be unsymmetrical. I hope this helps.

• Maybe you could say exactly what the Ising model is for directed graphs. I am only familiar with the Ising model for undirected graphs. Dec 22 '10 at 14:29
• I think many theoretical computer scientists have heard of the Ising model but probably do not remember precisely what it is. It would help if you defined it. Dec 23 '10 at 19:57
• I still don't understand the Ising model for directed graphs. I don't believe this is standard terminology. Please provide some more details. Is there a motivation for your question? According to Wikipedia, the two-local term for the standard Ising model is $-J_{ij}S_iS_j$. (Is this what you mean when you say $J_{ij}$ is the two-local term?) How does an asymmetric $J_{ij}$ make any difference when you plug this term into $-J_{ij}S_iS_j$? Dec 24 '10 at 0:28

If you take the standard Ising model: min $E= -\sum_{i \neq j}J_{ij}S_iS_j$, where $S_k =\pm 1$, and replace $J_{ij}$ with a non-symmetric matrix, it remains the standard Ising model. This is because you can rewrite the terms $- J_{ij}S_i S_j -J_{ji}S_j S_i = - \frac{J_{ij} + J_{ji}}{2} (S_iS_j + S_j S_i)$.
I should note that for planar MAX 2-SAT to be a generalization of the planar Ising model, you need to restrict the Ising model to polynomial-size integers $J_{ij}$. The obvious reduction also requires a planar multigraph, but there's an easy proof that planar MAX 2-SAT on a graph and on a multigraph are equivalent problems.