2
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • 5
    $\begingroup$ Maybe you could say exactly what the Ising model is for directed graphs. I am only familiar with the Ising model for undirected graphs. $\endgroup$ – Peter Shor Dec 22 '10 at 14:29
  • $\begingroup$ 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. $\endgroup$ – Warren Schudy Dec 23 '10 at 19:57
  • $\begingroup$ 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$? $\endgroup$ – Peter Shor Dec 24 '10 at 0:28
6
$\begingroup$

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)$.

A more interesting asymmetric generalization of the planar Ising model is planar MAX 2-SAT (the problem planar MIN 2-SAT is equivalent). This is the problem MAX 2-SAT where the clauses are on the edges of a planar graph. Planar MAX 2-SAT is NP-hard: look at this paper by Guibas, Hershberger, Mitchell and Snoeyink. Thus, it appears that there may be no interesting polynomial-time generalization of the planar Ising model algorithm.

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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ I wonder if it's then a candidate for problems not known to be in P or NPC: cstheory.stackexchange.com/questions/79/… $\endgroup$ – Suresh Venkat Dec 26 '10 at 17:55
  • $\begingroup$ @Suresh: that was quick. I was editing my answer to suggest the same thing myself while you were adding the comment. $\endgroup$ – Peter Shor Dec 26 '10 at 17:57
  • $\begingroup$ oh sorry. didn't realize that. $\endgroup$ – Suresh Venkat Dec 26 '10 at 18:04
  • $\begingroup$ No need to apologize. You couldn't know I had the same idea a few seconds after I hit the post button. $\endgroup$ – Peter Shor Dec 26 '10 at 19:25
  • 1
    $\begingroup$ And it turns out that planar MAX 2-SAT was proved NP-complete in 1991, as a lemma in another paper, and it has remained an obscure result since. See the update to my answer. $\endgroup$ – Peter Shor Feb 25 '11 at 2:39

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.