Invasion percolation and minimal spanning trees on spatial graphs

Summary Invasion percolation on a connected graph is defined as follows. Assign random weights to the edges of the graph, drawn independently from the uniform distribution on [0,1]. Grow a cluster by invading a given vertex, and successively invading neighbouring vertices in a greedy manner: always choose the edge with the smallest weight among all the edges out of the set of vertices already invaded.

We plan to investigate invasion percolation on finite graphs, where it leads to  the minimal spanning tree by Prim’s algorithm, and its asymptotics are closely related to critical percolation on such graphs. The first graph we would like to attack is the Cartesian product of two complete graphs. We plan to investigate both the weight of this object, as well as its distance structure. We further aim to investigate invasion percolation on Z^d with d large.

Supervisors Remco van der Hofstad (TU/e) and Frank den Hollander (UL)
PhD Student Lorenzo Frederico
Location Eindhoven University of Technology (TU/e)