English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

The minimum spanning tree (MST) is a combinatorial optimization problem:given a connected graph with a real weight ("cost") on each edge, find thespanning 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) independentrandom variables. There is a strongly-disordered spin-glass model due to Newmanand Stein [Phys. Rev. Lett. 72, 2286 (1994)], which maps precisely onto therandom MST. We study scaling properties of random MSTs using a relation betweenKruskal's greedy algorithm for finding the MST, and bond percolation. We solvethe random MST problem on the Bethe lattice (BL) with appropriate wiredboundary conditions and calculate the fractal dimension D=6 of the connectedcomponents. Viewed as a mean-field theory, the result implies that on a latticein Euclidean space of dimension d, there are of order W^{d-D} large connectedcomponents 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 Newmanand Stein. We also critique the original argument for 8, and provide animproved scaling argument that again yields d_c=6. The result implies that thestrongly-disordered spin-glass model has many ground states for d>6, and onlyof order one below six. The results for MSTs also apply on the Poisson-weightedinfinite tree, which is a mean-field approach to the continuum model of MSTs inEuclidean space, and is a limit of the BL. In a companion paper we develop anepsilon=6-d expansion for the random MST on critical percolation clusters.

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