Probabilistic graph inspections through forests

Koperberg, V.T.

Koperberg, V.T. (2026)

Probabilistic graph inspections through forests

Doctoral Thesis

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.
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.

Spanning rooted forests

Random graphs

Wilson's algorithm

Graph Laplacian

Loop-erased random walk

Random walk loop soup

Strassen's theorem

Hall's marriage theorem