Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published March 2018 | Submitted + Published
Journal Article Open

Interlacements and the wired uniform spanning forest


We extend the Aldous–Broder algorithm to generate the wired uniform spanning forests (WUSFs) of infinite, transient graphs. We do this by replacing the simple random walk in the classical algorithm with Sznitman's random interlacement process. We then apply this algorithm to study the WUSF, showing that every component of the WUSF is one-ended almost surely in any graph satisfying a certain weak anchored isoperimetric condition, that the number of 'excessive ends' in the WUSF is nonrandom in any graph, and also that every component of the WUSF is one-ended almost surely in any transient unimodular random rooted graph. The first two of these results answer positively two questions of Lyons, Morris and Schramm [Electron. J. Probab. 13 (2008) 1702–1725], while the third extends a recent result of the author. Finally, we construct a counterexample showing that almost sure one-endedness of WUSF components is not preserved by rough isometries of the underlying graph, answering negatively a further question of Lyons, Morris and Schramm.

Additional Information

© 2018 Institute of Mathematical Statistics. Received December 2015; revised May 2017. This work was carried out while the author was an intern at Microsoft Research, Redmond. We thank Omer Angel, Ori Gurel-Gurevich, Ander Holroyd, Russ Lyons, Asaf Nachmias and Yuval Peres for useful discussions. We also thank Tyler Helmuth for his careful reading of an earlier version of this manuscript, thank Perla Sousi for finding several typos, and thank both Russ Lyons and the anonymous referee for suggesting many corrections and improvements to the initial preprint.

Attached Files

Published - 17-AOP1203.pdf

Submitted - 1512.08509.pdf


Files (915.6 kB)
Name Size Download all
329.3 kB Preview Download
586.4 kB Preview Download

Additional details

August 19, 2023
October 23, 2023