Exact ground states of 2D planar Ising spin glass

From Cophy
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

Figure 1: 4x4 grid graph

or ring graphs

Figure 2: 4x4 ring graph

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 30002, cf. [Pardella and Liers (2008)].

Personal tools