论文标题
完整图上的多源入侵渗透
Multi-source invasion percolation on the complete graph
论文作者
论文摘要
我们考虑在随机加权完整图$ k_n $上的入侵渗透，从某种数字$ k（n）$的不同源顶点开始。该过程的结果是由$ k（n）$树组成的森林，每个树木完全包含一个来源。令$ m_n $为这森林中最大的树的大小。 Logan，Molloy和Pralat（Arxiv：1806.10975）证明，如果$ k（n）/n^{1/3} \ to 0 $ to $ the $ m_n/n \ to $ m_n/n \至1 $。在本文中，我们证明了一个互补的结果：如果$ k（n）/n^{1/3} \ to \ infty $，则$ m_n/n \ to 0 $ to in Boare。这确立了在$ k（n）\ asymp n^{1/3} $左右的入侵渗透森林结构中存在相变的存在。 我们的论点依赖于入侵渗透与临界渗透之间的联系，以及多源入侵渗透与大小不同的源集之间的耦合。证明的很大一部分是专门的，表明，在大可能性上，在大型随机二进制树上的一定碎片过程没有宏观尺寸的组成部分。
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.
