The critical Karp--Sipser core of Erdős--Rényi random graphs

2024/12/05 by Budzinski, Thomas, Contat, Alice
#Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.2412.04328

Abstract

The Karp--Sipser algorithm consists in removing recursively the leaves as well their unique neighbours and all isolated vertices of a given graph. The remaining graph obtained when there is no leaf left is called the Karp--Sipser core. When the underlying graph is the classical sparse Erdős--Rényi random graph G[n, λ/n], it is known to exhibit a phase transition at λ= e. We show that at criticality, the Karp--Sipser core has size of order n^3/5, which proves a conjecture of Bauer and Golinelli. We provide the asymptotic law of this renormalized size as well as a description of the distribution of the core as a graph. Our approach relies on the differential equation method, and builds up on a previous work on a configuration model with bounded degrees.

Related

• The critical Karp--Sipser core of random graphs
• A phase transition in Erdős-Barak random graphs
• Asymptotic size of the Karp-Sipser Core in Configuration Model
• On the Rank, Kernel, and Core of Sparse Random Graphs
• A central limit theorem for the matching number of a sparse random graph