The critical Karp--Sipser core of random graphs

MaRDI QIDQ6419611zbMATH OpenFDO

Authors Thomas Budzinski, Alice Contat, Nicolas Curien

Publication date 5 December 2022

Abstract: 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 & Golinelli and prove that at criticality, the Karp--Sipser core has size

a p p r o x m a t h r m C s t c d o t v a r t h e t a^{- 2} c d o t n^{3 / 5}

where

v a r t h e t a

is the hitting time of the curve

t m a p s t o f r a c 1 t^{2}

by a linear Brownian motion started at

0

. Our proof relies on a detailed multi-scale analysis of the Markov chain associated to Karp-Sipser leaf-removal algorithm close to its extinction time.

This page was built for publication: The critical Karp--Sipser core of random graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6419611)