# 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. – Peter Shor 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. – Warren Schudy 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$? – Peter Shor 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.