Loop Erasure, Spanning Trees and Combinatorial Maps

We introduce loop-erased random walks and present an extended version of Wilson’s algorithm which yields a loop ensemble of intensity 1 and a spanning forest of the graph. They are shown to be independent. Kirchoff’s theorem is derived from this construction. We finally show how a remarkable distribution on combinatorial maps can be derived from the configuration model introduced in Chap. 7 . Discrete loops ensembles can be constructed as facial contours of this random map.