PARKING ON CAYLEY TREES AND FROZEN ERDOS-RENYI

• 成果类型: Article
• 署名作者: Contat, Alice; Curien, Nicolas
• 署名单位: Universite Paris Saclay
• 刊物名称: ANNALS OF PROBABILITY
• ISSN/ISSBN: 0091-1798
• DOI: 10.1214/23-AOP1632
• 发表日期: 2023
• 页码: 1993-2055
• 关键词: multiplicative coalescent; growth-fragmentation; Scaling Limit; Random graphs; percolation; CONSTRUCTION; asymptotics; excursions; MAPS; sums

摘要

Consider a uniform rooted Cayley tree T-n with n vertices and let m cars arrive sequentially, independently, and uniformly on its vertices. Each car tries to park on its arrival node, and if the spot is already occupied, it drives towards the root of the tree and parks as soon as possible. Lackner and Panholzer (J. Combin. Theory Ser. A 142 (2016) 1-28) established a phase transition for this process when m approximate to n/2. In this work, we couple this model with a variant of the classical Erdos-Renyi random graph process. This enables us to describe the phase transition for the size of the components of parked cars using a modification of the multiplicative coalescent which we name the frozen multiplicative coalescent. The geometry of critical parked clusters is also studied. Those trees are very different from Bienayme-Galton-Watson trees and should converge towards the growth-fragmentation trees canonically associated to the 3/2-stable process that already appeared in the study of random planar maps.