Multi-source invasion percolation on the complete graph

Abstract

We consider invasion percolation on the randomly-weighted complete graph $K_n$, started from some number $k(n)$ of distinct source vertices. The outcome of the process is a forest consisting of $k(n)$ trees, each containing exactly one source. Let $M_n$ be the size of the largest tree in this forest. Logan, Molloy and Pralat (arXiv:1806.10975) proved that if $k(n)/n^{1/3}\to 0$ then $M_n/n\to 1$ in probability. In this paper we prove a complementary result: if $k(n)/n^{1/3}\to \infty$ then $M_n/n\to 0$ in probability. This establishes the existence of a phase transition in the structure of the invasion percolation forest around $k(n)\asymp n^{1/3}$. Our arguments rely on the connection between invasion percolation and critical percolation, and on a coupling between multi-source invasion percolation with differently-sized source sets. A substantial part of the proof is devoted to showing that, with high probability, a certain fragmentation process on large random binary trees leaves no components of macroscopic size.

35 pages