The critical Karp--Sipser core of random graphs

2022/12/05 by Budzinski, Thomas, Contat, Alice, Curien, Nicolas · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.2212.02463

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 ≈ Cst ⋅ ϑ^-2 ⋅ n^3/5 where ϑ is the hitting time of the curve t ↦ \frac1t² 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.

Cited by

• Asymptotic size of the Karp-Sipser Core in Configuration Model

Related

• The critical Karp--Sipser core of Erdős--Rényi random graphs
• Asymptotic size of the Karp-Sipser Core in Configuration Model
• A central limit theorem for the matching number of a sparse random graph
• Critical random graphs: limiting constructions and distributional properties
• Core forging and local limit theorems for the k-core of random graphs