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 Parisi’s scheme to the case of infinitely many-order parameters $q_{\alpha \beta }$,$q_{\alpha \beta \gamma \delta }$,.... 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 q’s 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 9≤M≤20, much closer than the replica symmetric solution.