Back to Search
Start Over
A reverse Aldous/Broder algorithm
- Publication Year :
- 2019
-
Abstract
- The Aldous--Broder algorithm provides a way of sampling a uniformly random spanning tree for finite connected graphs using simple random walk. Namely, start a simple random walk on a connected graph and stop at the cover time. The tree formed by all the first-entrance edges has the law of a uniform spanning tree. Here we show that the tree formed by all the last-exit edges also has the law of a uniform spanning tree. This answers a question of Tom Hayes and Cris Moore from 2010. The proof relies on a bijection that is related to the BEST theorem in graph theory. We also give other applications of our results, including new proofs of the reversibility of loop-erased random walk, of the Aldous--Broder algorithm itself, and of Wilson's algorithm.<br />Comment: 14 pages, 1 figure
- Subjects :
- Mathematics - Probability
Mathematics - Combinatorics
60J10, 05C81, 05C05
Subjects
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.1907.10196
- Document Type :
- Working Paper