REPLICA SYMMETRY-BREAKING IN THE SPIN-GLASS MODEL ON LATTICES WITH FINITE CONNECTIVITY - APPLICATION TO GRAPH PARTITIONING

A systematic way to construct replica symmetry-breaking solutions of the spin glass on random lattices with finite (fixed or average) connectivity is presented. The method generalizes Parisis scheme to the case of infinitely many-order parameters q,q,.... A systematic expansion in inverse powers of the connectivity (=M+1) is performed. At finite temperatures the expansion is in powers of 1/M, and at zero temperature in powers of 1/M. The qs with larger number of indices contribute at higher orders in the expansion parameter. At zero temperature the results apply to the graph bipartitioning problem and are compared with numerical simulation. The agreement is of the order of 1%, for the range 9M20, much closer than the replica symmetric solution. © 1990 The American Physical Society.