𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Uniform and minimal essential spanning forests on trees

✍ Scribed by Olle Häggström

Publisher
John Wiley and Sons
Year
1998
Tongue
English
Weight
252 KB
Volume
12
Category
Article
ISSN
1042-9832

No coin nor oath required. For personal study only.

✦ Synopsis

Uniform and minimal random spanning trees for finite graphs are well-known objects. Analogues of these for the nearest-neighbor graph on Z d have been studied by Pemantle and Alexander. Here we propose analogous definitions of uniform resp. minimal essential spanning forests for an infinite tree ⌫, and initiate a study of these random objects. Most results are confined to the case when ⌫ is a regular tree of order n G 2, where the two Ž . models share the properties that each edge is present with probability 2r n q 1 , and every vertex a.s. has exactly one self-avoiding path to infinity. Despite these similarities, the distributions are different. The uniform essential spanning forest admits a simple description in terms of a Galton᎐Watson process and also arises as a limit of random-cluster measures.

📜 SIMILAR VOLUMES

Minimal ratio spanning trees
Minimal ratio spanning trees
✍ R. Chandrasekaran 📂 Article 📅 1977 🏛 John Wiley and Sons 🌐 English ⚖ 323 KB
Random minimal spanning tree and percola
Random minimal spanning tree and percolation on the N-cube
✍ Mathew D. Penrose 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 251 KB 👁 1 views

The N-cube is a graph with 2 N vertices and N 2 Ny1 edges. Suppose indepen- dent uniform random edge weights are assigned and let T be the spanning tree of minimal Ž . y 1 N ϱ y3 total weight. Then the weight of T is asymptotic to N 2 Ý i as N ª ϱ. Asymp-is1 totics are also given for the local stru

Scaling limits for minimal and random sp
Scaling limits for minimal and random spanning trees in two dimensions
✍ Michael Aizenman; Almut Burchard; Charles M. Newman; David B. Wilson 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 469 KB

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 establi

Inapplicability of Asymptotic Results on
Inapplicability of Asymptotic Results on the Minimal Spanning Tree in Statistical Testing
✍ C. Caroni; P. Prescott 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 62 KB

Penrose has given asymptotic results for the distribution of the longest edge of the minimal spanning tree and nearest neighbour graph for sets of multivariate uniformly or normally distributed points. We investigate the applicability of these results to samples of up to 100 points, in up to 10 dime

Independent spanning trees on folded hyp
Independent spanning trees on folded hyper-stars
✍ Jinn-Shyong Yang; Jou-Ming Chang 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 302 KB

## Abstract Fault‐tolerant broadcasting and secure message distribution are important issues for numerous applications in networks. It is a common idea to design multiple independent spanning trees (ISTs) as a broadcasting scheme or a distribution protocol for receiving high levels of fault‐toleran