Interlacements and the wired uniform spanning forest
- Creators
- Hutchcroft, Tom
Abstract
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
Name | Size | Download all |
---|---|---|
md5:f55519d0e455e708c3425b448f04fe56
|
329.3 kB | Preview Download |
md5:985400f14a1900c66cbc382c1b011845
|
586.4 kB | Preview Download |
Additional details
- Eprint ID
- 111025
- Resolver ID
- CaltechAUTHORS:20210924-190634891
- Microsoft Research
- Created
-
2021-09-27Created from EPrint's datestamp field
- Updated
-
2021-09-27Created from EPrint's last_modified field