Random walks and uniform spanning trees.
Sousi, Perla
Random walks and uniform spanning trees. - Rio de Janeiro: IMPA, 2020. - video online
Mini course (Webinar) - 5 lectures.
Abstract: Spanning trees in a connected graph are basic objects of great interest in combinatorics and computer science. In this course we will study what a typical spanning tree looks like and we will discuss elegant sampling algorithms using random walks due to Aldous, Broder and Wilson from the 1990's. We will then explain how we can sample a uniform spanning tree (or forest) of $\mathbb^d$ for $d\geq 2$. Using the connection with random walks and a recent algorithm due to Hutchcroft we will obtain results on the fine geometry of uniform spanning trees .
Matematica.
cs
Random walks and uniform spanning trees. - Rio de Janeiro: IMPA, 2020. - video online
Mini course (Webinar) - 5 lectures.
Abstract: Spanning trees in a connected graph are basic objects of great interest in combinatorics and computer science. In this course we will study what a typical spanning tree looks like and we will discuss elegant sampling algorithms using random walks due to Aldous, Broder and Wilson from the 1990's. We will then explain how we can sample a uniform spanning tree (or forest) of $\mathbb^d$ for $d\geq 2$. Using the connection with random walks and a recent algorithm due to Hutchcroft we will obtain results on the fine geometry of uniform spanning trees .
Matematica.
cs