A strongly disordered spin glass and minimum spanning trees

We investigate the ground state structure of a strongly disordered spin glass model proposed by Newman and Stein (NS). In the strong disorder limit, frustration is negligible and the problem of identifying ground states is equivalent to the minimum spanning tree (MST) problem in combinatorial optimization: given an edge-weighted graph, the MST is the subset of edges that connects all vertices, has no cycles, and minimizes the total edge weight. Here the weights are quenched random variables, and we use a relation between Kruskal's greedy algorithm for finding the MST and percolation. We solve this random MST on the Bethe lattice with appropriate boundary conditions, which defines a mean-field theory valid above $d_c=6$ (NS proposed $d_c=8$). Above $d_c$, NS showed that the spin glass model has infinitely many ground states, but only a single pair below $d_c$. For $d6$).