Physics – Condensed Matter – Statistical Mechanics
Scientific paper
2009-02-20
Phys. Rev. E 81, 021130 (2010)
Physics
Condensed Matter
Statistical Mechanics
18 pages, 3 figures; [v2] figures changed to EPS; [v3] minor changes and section III.H added in response to referee
Scientific paper
10.1103/PhysRevE.81.021130
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.
Jackson Stephen T.
Read Nicholas
No associations
LandOfFree
Theory of minimum spanning trees I: Mean-field theory and strongly disordered spin-glass model does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Theory of minimum spanning trees I: Mean-field theory and strongly disordered spin-glass model, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Theory of minimum spanning trees I: Mean-field theory and strongly disordered spin-glass model will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-370170