Aldous-Broder theorem: extension to the non reversible case and new combinatorial proof

Combinatorics Seminar
Friday, March 26, 2021 - 3:00pm for 1 hour (actually 50 minutes)
Location (To receive the password, please email Lutz Warnke)
Jean-Francois Marckert – University of Bordeaux –
Lutz Warnke

Aldous-Broder algorithm is a famous algorithm used to sample a uniform spanning tree of any finite connected graph G, but it is more general: it states that given a reversible M Markov chain on G started at r, the tree rooted at r formed by the steps of successive first entrance in each node (different from the root) has a probability proportional to $\prod_{e=(e1,e2)∈Edges(t,r)}M_{e1,e2}$ , where the edges are directed toward r. As stated, it allows to sample many distributions on the set of spanning trees. In this paper we extend Aldous-Broder theorem by dropping the reversibility condition on M. We highlight that the general statement we prove is not the same as the original one (but it coincides in the reversible case with that of Aldous and Broder). We prove this extension in two ways: an adaptation of the classical argument, which is purely probabilistic, and a new proof based on combinatorial arguments. On the way we introduce a new combinatorial object that we call the golf sequences.

Based on joint work with Luis Fredes, see