Discrete Mathematics and Optimization Seminar
Jan. 25th, 2010
Exponential growth of ponds in invasion percolation on regular trees
Jesse Goodman
In invasion percolation, the edges of a graph are assigned i.i.d. edge weights, and an infinite cluster is grown by recursively adding the boundary edge of minimal weight. By considering the edges whose weight is larger than all subsequently accepted weights, the invasion cluster is divided into a chain of \emph{ponds} linked by \emph{outlets}.

Working on the regular tree, we show that the sizes of the ponds grow exponentially, with law of large numbers, central limit theorem and large deviation results, and also give asymptotics for the size of a fixed pond.

We compare with known results for Z^2 and explore why these results should be expected on more general graphs.