The critical Karp–Sipser core of random graphs

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 ≈Cst·ϑ−2·n3/5 where ϑ is the hitting time of the curve t↦1t2 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.