Dispersion on the Complete Graph

Thời gian: 14h00-15h00 thứ năm, ngày 11/12/2025

Địa điểm: Phòng 507 nhà A6

Tóm tắt: We consider a synchronous process of particles moving on the vertices of a graph G, introduced by Cooper, McDowell, Radzik, Rivera and Shiraga (2018). At the start of the process, M particles are placed on one vertex of G. At the beginning of every (discrete) time step, each particle located at a vertex inhabited by two or more particles moves independently to a neighbouring vertex 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=M(n) passes n/2. More precisely they showed that, if M0, then the process finishes in a logarithmic number of steps, while if M>(1+ε)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 ε=o(1), and describe the transition from logarithmic to exponential time. As a consequence of our results we establish, for example, that when |ε|=O(n^{-1/2}) the dispersion time is of order n^{1/2} both in probability and in expectation; we also provide qualitative bounds for its tail behavior. This is based on joint work with T. Makai and K. Panagiotou.