MULTISOURCE INVASION PERCOLATION ON THE COMPLETE GRAPH

• 成果类型: Article
• 署名作者: Addario-Berry, Louigi; Barrett, Jordan
• 署名单位: McGill University
• 刊物名称: ANNALS OF PROBABILITY
• ISSN/ISSBN: 0091-1798
• DOI: 10.1214/23-AOP1641
• 发表日期: 2023
• 页码: 2131-2157
• 关键词: minimum spanning tree; SCALING LIMITS; network

摘要

We consider invasion percolation on the 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 (2018) proved that if k(n)/n(1/3)-> 0 then M-n/n -> 1 in probability. In this paper, we prove a complementary result: if k(n)/n(1/3)-> infinity, then M-n/n -> 0 in probability. This establishes the existence of a phase transition in the structure of the invasion percolation forest around k(n) asymptotic to n(1/3).Our arguments rely on the connection between invasion percolation and critical percolation, and on a coupling between multisource 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.