Exact ground states of 2D planar Ising spin glass

From cophywiki
Revision as of 08:29, 24 March 2010 by Pardella (talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

2D planar Ising spin glasses

Determination of exact ground states in 2D planar Ising spin glasses without an external magnetic field is a special case of ground state calculations in spin glasses. It is equivalent to max-cut on planar graphs, and can be solved in polynomial time.

Being more exact, the problem can be reduced to a minimum weighted perfect matching problem in a planar graph. In doing so the planar max-cut problem reduces to the calculation of optimum Eulerian subgraphs in the dual graph. This is due to the nice one-to-one correspondence between cuts in the primal graph and cycles in its dual graph.

Often one considers grid graphs

Error creating thumbnail: File missing

or ring graphs

Error creating thumbnail: File missing
.

Here we describe how to model the determination of ground states as a maximum cut problem. For 2d spin glasses with open boundaries in at least one direction, the resulting graph of interactions is planar.

Being NP-hard in general, max-cut can be solved in polynomial time for planar graphs, cf. planar max-cut article.

Thus the determination of exact ground states for 2D planar Ising spin glasses can be done very quickly.

With our fast implementation we solve grid graph instances of size up to 3000^2, cf. [Pardella and Liers (2008)].