TY - JOUR

T1 - Scaling limits for minimal and random spanning trees in two dimensions

AU - Aizenman, Michael

AU - Burchard, Almut

AU - Newman, Charles M.

AU - Wilson, David B.

N1 - Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.

PY - 1999

Y1 - 1999

N2 - A general formulation is presented for continuum scaling limits of stochastic spanning trees. A spanning tree is expressed in this limit through a consistent collection of subtrees, which includes a tree for every finite set of endpoints in ℝd. Tightness of the distribution, as δ → 0, is established for the following two-dimensional examples: the uniformly random spanning tree on δℤ2, the minimal spanning tree on δSℤ2 (with random edge lengths), and the Euclidean minimal spanning tree on a Poisson process of points in ℝ2 with density δ-2. In each case, sample trees are proven to have the following properties, with probability 1 with respect to any of the limiting measures: (i) there is a single route to infinity (as was known for δ > 0); (ii) the tree branches are given by curves which are regular in the sense of Hölder continuity; (iii) the branches are also rough, in the sense that their Hausdorff dimension exceeds 1; (iv) there is a random dense subset of ℝ2, of dimension strictly between 1 and 2, on the complement of which (and only there) the spanning subtrees are unique with continuous dependence on the endpoints; (v) branching occurs at countably many points in ℝ2; and (vi) the branching numbers are uniformly bounded. The results include tightness for the loop-erased random walk in two dimensions. The proofs proceed through the derivation of scale-invariant power bounds on the probabilities of repeated crossings of annuli.

AB - A general formulation is presented for continuum scaling limits of stochastic spanning trees. A spanning tree is expressed in this limit through a consistent collection of subtrees, which includes a tree for every finite set of endpoints in ℝd. Tightness of the distribution, as δ → 0, is established for the following two-dimensional examples: the uniformly random spanning tree on δℤ2, the minimal spanning tree on δSℤ2 (with random edge lengths), and the Euclidean minimal spanning tree on a Poisson process of points in ℝ2 with density δ-2. In each case, sample trees are proven to have the following properties, with probability 1 with respect to any of the limiting measures: (i) there is a single route to infinity (as was known for δ > 0); (ii) the tree branches are given by curves which are regular in the sense of Hölder continuity; (iii) the branches are also rough, in the sense that their Hausdorff dimension exceeds 1; (iv) there is a random dense subset of ℝ2, of dimension strictly between 1 and 2, on the complement of which (and only there) the spanning subtrees are unique with continuous dependence on the endpoints; (v) branching occurs at countably many points in ℝ2; and (vi) the branching numbers are uniformly bounded. The results include tightness for the loop-erased random walk in two dimensions. The proofs proceed through the derivation of scale-invariant power bounds on the probabilities of repeated crossings of annuli.

UR - http://www.scopus.com/inward/record.url?scp=0033415760&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0033415760&partnerID=8YFLogxK

U2 - 10.1002/(sici)1098-2418(199910/12)15:3/4<319::aid-rsa8>3.0.co;2-g

DO - 10.1002/(sici)1098-2418(199910/12)15:3/4<319::aid-rsa8>3.0.co;2-g

M3 - Article

AN - SCOPUS:0033415760

VL - 15

SP - 319

EP - 367

JO - Random Structures and Algorithms

JF - Random Structures and Algorithms

SN - 1042-9832

IS - 3-4

ER -