标题： 完全图上的色散 显示英文标题

标题： Dispersion on the Complete Graph

摘要： 我们考虑由 Cooper、McDowell、Radzik、Rivera 和 Shiraga（2018）引入的图$G$上粒子同步移动的过程。最初，$M$个粒子被放置在$G$的一个顶点上。在每个时间步开始时，对于至少有两个粒子占据的每个顶点，这些粒子各自独立地以相等的概率随机移动到一个相邻顶点。当没有顶点被多于一个粒子占据时，过程结束。Cooper 等人表明，当底层图是具有 ~$n$个顶点的完全图时，粒子数量为$M = n/2$时存在相变现象。 他们证明了如果对于某个固定的$\varepsilon>0$满足$M<(1-\varepsilon)n/2$，那么过程将在对数步数内结束，而如果$M>(1+\varepsilon)n/2$成立，则以高概率需要指数步数。 在这里，我们对临界点附近的分散时间进行了彻底的渐近分析，其中$\varepsilon = o(1)$，并描述了从对数时间到指数时间的转变。 作为我们的结果的一个推论，例如，当$|\varepsilon| = O(n^{-1/2})$时，我们确定分散时间以概率和期望意义处于$\Theta(n^{1/2})$中，并提供了尾部行为的定性界限。 显示英文摘要

摘要： We consider a synchronous process of particles moving on the vertices of a graph $G$, introduced by Cooper, McDowell, Radzik, Rivera and Shiraga (2018). Initially, $M$ particles are placed on a vertex of $G$. At the beginning of each time step, for every vertex inhabited by at least two particles, each of these particles moves independently to a neighbour chosen uniformly at random. The process ends at the first step when no vertex is inhabited by more than one particle. Cooper et al. showed that when the underlying graph is the complete graph on~$n$ vertices, then there is a phase transition when the number of particles $M = n/2$. They showed that if $M<(1-\varepsilon)n/2$ for some fixed $\varepsilon>0$, then the process finishes in a logarithmic number of steps, while if $M>(1+\varepsilon)n/2$, an exponential number of steps are required with high probability. Here we provide a thorough asymptotic analysis of the dispersion time around criticality, where $\varepsilon = o(1)$, and describe the transition from logarithmic to exponential time. As a consequence of our results we establish, for example, that the dispersion time is in probability and in expectation in $\Theta(n^{1/2})$ when $|\varepsilon| = O(n^{-1/2})$, and provide qualitative bounds for its tail behavior.