THE CRITICAL KARP-SIPSER CORE OF RANDOM GRAPHS

• 成果类型: Article
• 署名作者: Budzinski, Thomas; Contat, Alice; Curien, Nicolas
• 署名单位: Ecole Normale Superieure de Lyon (ENS de LYON); Centre National de la Recherche Scientifique (CNRS); Universite Paris Saclay
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/24-AAP2133
• 发表日期: 2025
• 页码: 983-1018
• 关键词: differential-equations; k-core; CONVERGENCE; emergence

摘要

We study the Karp-Sipser core of a random graph made of a configuration model with vertices of degree 1, 2 and 3. This core is obtained by recursively removing the leaves as well as their unique neighbors in the graph. We settle a conjecture of Bauer and Golinelli ( (Eur. Phys. J. B 24 (2001) 339-352) and prove that at criticality, the Karp-Sipser core has size approximate to Cst . .theta .theta- .theta-2 . n n3/5 where theta is the hitting time of the curve t -> 1 t t2 by a linear Brownian motion started at 0. Our proof relies on a detailed multi-scale analysis of the Markov chain associated to the Karp-Sipser leaf-removal algorithm close to its extinction time.