Dissertation

Probabilistic Graph Inspections through Forests

This dissertation consists of two parts, each of which describes a distinct implementation of a graph complexity reduction scheme with the help of spanning forests.

Author

V.T. Koperberg

Date

25 June 2026

Links

Thesis in Leiden Repository

The topic of part I, which is the largest of the two parts and contains chapters 2 to 4, is a specific probability measure on the spanning rooted forests of an arbitrary given network. This measure will be referred to as the Kirchhoff forest measure, and can be sampled with Wilson's algorithm by equipping the utilized loop-erased random walks with a random killing time. Particular focus is given to the connectivity properties of Kirchhoff forests, and to the link between Kirchhoff forests and random walk loop soups.

The main contribution of the part II is a novel and elementary proof of Strassen’s theorem on couplings of probability measures for the special case in which both measures are finitely supported. This proof highlights a known connection between Strassen's theorem and Hall's marriage theorem.

• graph laplacian
• hall's marriage theorem
• loop-erased random walk
• random graphs
• random walk loop soup
• spanning rooted forests
• strassen's theorem
• wilson's algorithm