10h30: Louigi Addario-Berry, McGill University.

Prim's algorithm and self-organized criticality, in the complete graph.

Let G=(V,E) be a graph with weights {w_e : e in E}, and assume all weights are distinct. If G is finite, then the well-known Prim's algorithm constructs its minimum spanning tree in the following manner. Starting from a single vertex v, add the smallest weight edge connecting v to any other vertex. More generally, at each step add the smallest weight edge joining some vertex that has already been "explored" to some unexplored vertex. If G is infinite, however, Prim's algorithm does not necessarily construct a spanning tree (consider, for example, the case when the underlying graph is the two-dimensional lattice Z^2, all weights on horizontal edges are strictly less than 1/2 and all weights on vertical edges are strictly greater than 1/2). The behaviour of Prim's algorithm for *random* edge weights is an interesting and challenging object of study, even when the underlying graph is extremely simple. This line of research was initiated by McDiarmid, Johnson and Stone (1996), in the case when the underlying graph is the complete graph K_n. Recently Angel et. al. (2006) have studied Prim's algorithm on regular trees with uniform random edge weights. We study Prim's algorithm on K_n and on its infinitary analogue Aldous' Poisson-weighted infinite tree. Along the way, we uncover two new descriptions of the Poisson IIC, the critical Poisson Galton-Watson tree conditioned to survive forever. This is joint work with Simon Griffiths and Ross Kang.