Uniform and minimal essential spanning forests on trees

Abstract

Uniform and minimal random spanning trees for finite graphs are well-known objects. Analogues of these for the nearest-neighbor graph on Zd 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