On the ground states of the frustration model of a spin glass by a matching method of graph theory

Abstract

The ground states of a quenched random Ising spin system with variable concentration of mixed nearest-neighbour exchange couplings +or-J on a square lattice (frustration model) are studied by a new method of graph theory. The search for ground states is mapped into the problem of perfect matching of minimum weight in the graph of frustrated plaquettes, a problem which can be solved by the algorithm of Edmonds. A pedestrian presentation of this elaborated algorithm is given with a discussion of the condition of validity.