Contributions to Determining Exact Ground-States of Ising Spin-Glasses and to their Physics
Frauke Liers · Kölner Universitäts PublikationsServer (Universität zu Köln) · 2004
In the last decades, much research has focused on a better understanding of so-called spin glasses (e.g., the alloys CuMn and AuFe.) Spin glasses are not yet fully understood. In order to be able to test the different theories that have been proposed for the nature of spin glasses we have to analyze numerically generated data. We consider spin glasses in the Ising model, where the spins (magnetic dipoles) have exactly two possibilities for aligning themselves. We are interested in the low-temperature states of the system, in which the spins are `frozen' and disordered. Determining a state of minimum energy, a ground state, amounts to calculating a maximum cut in a graph. The max-cut problem is a prominent NP-hard problem from combinatorial optimization. Maximum cuts can be determined exactly with a branch-and-cut algorithm. This thesis consists of two parts. In the first part we introduce the max-cut problem and a branch-and-cut algorithm for solving reasonably sized problems. We present several approaches for improving its performance for Ising spin-glass instances. In the second part of this work, we study the physics of spin glasses. We first discuss what is known in the literature. Then we present results for Bethe spin glasses. Finally we study the nature of short-range three-dimensional spin glasses. Results of the former were obtained in collaboration with M. Palassini and A.K. Hartmann, results of the latter in cooperation with M. Palassini and A. Peter Young.