Theory of minimum spanning trees I: Mean-field theory and strongly disordered spin-glass model

Abstract

The minimum spanning tree (MST) is a combinatorial optimization problem: given a connected graph with a real weight ("cost") on each edge, find the spanning tree that minimizes the sum of the total cost of the occupied edges. We consider the random MST, in which the edge costs are (quenched) independent random variables. There is a strongly-disordered spin-glass model due to Newman and Stein [Phys. Rev. Lett. 72, 2286 (1994)], which maps precisely onto the random MST. We study scaling properties of random MSTs using a relation between Kruskal's greedy algorithm for finding the MST, and bond percolation. We solve the random MST problem on the Bethe lattice (BL) with appropriate wired boundary conditions and calculate the fractal dimension D=6 of the connected components. Viewed as a mean-field theory, the result implies that on a lattice in Euclidean space of dimension d, there are of order W^{d-D} large connected components of the random MST inside a window of size W, and that d = d_c = D = 6 is a critical dimension. This differs from the value 8 suggested by Newman and Stein. We also critique the original argument for 8, and provide an improved scaling argument that again yields d_c=6. The result implies that the strongly-disordered spin-glass model has many ground states for d>6, and only of order one below six. The results for MSTs also apply on the Poisson-weighted infinite tree, which is a mean-field approach to the continuum model of MSTs in Euclidean space, and is a limit of the BL. In a companion paper we develop an epsilon=6-d expansion for the random MST on critical percolation clusters.

18 pages, 3 figures; [v2] figures changed to EPS; [v3] minor changes and section III.H added in response to referee

References in corpus (8)

• Transport in weighted networks: Partition into superhighways and roads
• Optimal Path and Minimal Spanning Trees in Random Weighted Networks
• Minimal spanning forests
• Winding angle variance of Fortuin-Kasteleyn contours
• Current Flow in Random Resistor Networks: The Role of Percolation in Weak and Strong Disorder
• Theory of minimum spanning trees II: exact graphical methods and perturbation expansion at the percolation threshold
• Possible Connection between the Optimal Path and Flow in Percolation Clusters
• Minimum spanning trees and random resistor networks in d dimensions

Cited by in corpus (17)

• Spatial Networks
• Disappearance of the de Almeida-Thouless line in six dimensions
• Networking - A Statistical Physics Perspective
• Fracturing ranked surfaces
• Uniqueness of Ground States for Short-Range Spin Glasses in the Half-Plane
• Short-range Ising spin glasses: the metastate interpretation of replica symmetry breaking
• Theory of minimum spanning trees II: exact graphical methods and perturbation expansion at the percolation threshold
• Clustering with minimum spanning trees: How good can it be?
• Finite-size critical scaling in Ising spin glasses in the mean-field regime
• Fractal dimension of interfaces in Edwards-Anderson spin glasses for up to six space dimensions
• The Fractal Dimension of Interfaces in Edwards-Anderson and Long-range Ising Spin Glasses: Determining the Applicability of Different Theoretical Descriptions
• Tracing the Evolution of Physics on the Backbone of Citation Networks
• Critical Point Scaling of Ising Spin Glasses in a Magnetic Field
• Ground State Stability and the Nature of the Spin Glass Phase
• Minimal spanning trees at the percolation threshold: a numerical calculation
• Diffusion of a particle in the spatially correlated exponential random energy landscape: transition from normal to anomalous diffusion
• Large Deviation Properties of Minimum Spanning Trees for Random Graphs