×

Scaling limits for minimal and random spanning trees in two dimensions. (English) Zbl 0939.60031

A general formulation for continuum scaling limits of stochastic spanning trees is presented. The paper is organized in eight sections. Section 1 is an introduction. In Section 2 the space of immersed trees is introduced. Section 3 contains a summary of some pertinent results as two criteria for systems of random curves, which permit one to deduce regularity and roughness statements (as in Theorem 1.1). The criteria require certain scale-invariant bounds on the probabilities of multiple traversals of annuli and of lengthwise traversals of rectangles by curves in the given random family. These criteria admit a conformally invariant formulation. In Sections 4 and 5 some auxiliary results are presented. Section 4 deals with a very useful free-wired bracketing principle, while in Section 5 preliminary results on the crossing probabilities for annuli with various boundary conditions are presented. In the next section the regularity criterion is verified, treating the three models separately. Then, in Section 7 the roughness criterion is verified by means of an argument that applies to all the models just discussed. Finally, in the last section the scale-invariant bounds derived in the previous two sections are used to prove the Theorems 1.1 and 1.2. Some further comments on the geometry of scaling limits are made, too. The discussion of crossing exponents is supplemented in the Appendix by deriving a quadratic lower bound \([\lambda(k)\geq\text{const}.(k-1)^2]\) for the rate of growth of the exponent associated with the probability of \(k\)-fold traversals.
The paper offers to the reader a varied, rigorous and very good study, which can be successfully continued.
Reviewer: G.Orman (Braşov)

MSC:

60G50 Sums of independent random variables; random walks
05C80 Random graphs (graph-theoretic aspects)

References:

[1] Langlands, Bull Amer Math Soc 30 pp 1– (1994)
[2] Cardy, J Phys A 25 pp l201– (1992)
[3] Scaling limit for the incipient spanning clusters, Mathematics of Multiscale Materials, IMA Volumes in Mathematics and its Applications, and (Editors), Springer, Berlin, (Editors), 1998; available at .
[4] Cohn, Duke Math J 85 pp 117– (1996)
[5] Conformal invariance of domino tiling, 1997 preprint; available at .
[6] Aizenman, Duke Math J 99 pp 419– (1999)
[7] Pemantle, Ann Probab 19 pp 1559– (1991)
[8] Häggström, Stochastic Process Appl 59 pp 267– (1995)
[9] and Uniform spanning forests, preprint, 1998; available at .
[10] Alexander, Ann Probab 23 pp 87– (1995)
[11] Chayes, Comm Math Phys 101 pp 383– (1985)
[12] Alexander, Ann Probab 6 pp 466– (1996)
[13] Generating random spanning trees more quickly than the cover time, Proc 28th Annual ACM Symp on the Theory of Computing, 1996, p. 296-303. · Zbl 0946.60070
[14] Alexander, J Statist Phys 77 pp 627– (1994)
[15] Newman, Phys Rev Lett 72 pp 2286– (1994)
[16] Newman, J Statist Phys 82 pp 1113– (1996)
[17] Aizenman, Nucl Phy B 485 pp 551– (1997)
[18] Nienhuis, J Phys A 15 pp 199– (1982)
[19] Duplantier, Phys Rev Lett 58 pp 2325– (1987)
[20] Aizenman, Phys Rev Lett 83 pp 1359– (1999)
[21] Fortuin, Physica 57 pp 536– (1972)
[22] Duplantier, J Statist Phys 49 pp 411– (1987)
[23] Large scale degrees and the number of spanning clusters for the uniform spanning tree, Perplexing Probability Problems: Papers in Honor of Harry Kesten, and (Editors), Progress in Probability Series, Birkhäuser, Boston, 1999, pp. 175-183. · Zbl 0941.60029 · doi:10.1007/978-1-4612-2168-5_10
[24] Scaling limits of loop-erased random walks and random spanning trees, preprint, 1999.
[25] Redmond, Ann Appl Probab 4 pp 1057– (1994)
[26] Aizenman, J Stat Phys 50 pp 1– (1998)
[27] Kesten, Comm Math Phys 74 pp 41– (1980)
[28] Russo, Z Wahrsch Verw Gebiete 43 pp 39– (1978)
[29] and ? Percolation probabilities on the square lattice,? Advances in Graph Theory, Annals of Discrete Mathematics, (Editor), North-Holland, Amsterdam, 1978, Vol. 3. · Zbl 0405.60015 · doi:10.1016/S0167-5060(08)70509-0
[30] van den Berg, J Appl Probab 22 pp 556– (1985)
[31] and Computational Geometry: An Introduction, Springer, New York, 1985. · doi:10.1007/978-1-4612-1098-6
[32] Burton, Comm Math Phys 121 pp 501– (1989)
[33] On the method of bounded differences, Surveys in Combinatorics, 1989 ( Norwich, 1989), pp. 148-188.
[34] London Math Soc Lect Note Ser 141 (Cambridge Univ. Press 1989).
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.