Premium
Uniform and minimal essential spanning forests on trees
Author(s) -
Häggström Olle
Publication year - 1998
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/(sici)1098-2418(199801)12:1<27::aid-rsa2>3.0.co;2-v
Subject(s) - spanning tree , combinatorics , mathematics , random graph , vertex (graph theory) , shortest path tree , minimum spanning tree , limit (mathematics) , path (computing) , tree (set theory) , random walk , discrete mathematics , struct , random tree , graph , computer science , mathematical analysis , statistics , robot , motion planning , artificial intelligence , programming language
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 ≥2, where the two models share the properties that each edge is present with probability 2/( n +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. © 1998 John Wiley & Sons, Inc. Random Struct. Alg. , 12, 27–50, 1998