Asymptotic size of the Karp-Sipser Core in Configuration Model

2025/08/26 by Chatterjee, Arnab, Lee, Joon Hyung, Zhu, Haodong
#05C80 #60C05 #68W20 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.2508.19453

Abstract

We study the asymptotic size of the Karp-Sipser core in the configuration model with arbitrary degree distributions. The Karp-Sipser core is the induced subgraph obtained by iteratively removing all leaves and their neighbors through the leaf-removal process, and finally discarding any isolated vertices \citeBCC. Our main result establishes the convergence of the Karp-Sipser core size to an explicit fixed-point equation under general degree assumptions.The approach is based on analyzing the corresponding local weak limit of the configuration model - a unimodular Galton-Watson tree and tracing the evolution process of all vertex states under leaf-removal dynamics by use of the working mechanism of an enhanced version of Warning Propagation along with Node Labeling Propagation.

Citations

• The asymptotic rank of adjacency matrices of weighted configuration models over arbitrary fields
• Belief Propagation Guided Decimation on Random k-XORSAT
• The rank of sparse symmetric matrices over arbitrary fields
• The critical Karp--Sipser core of random graphs
• Warning Propagation: stability and subcriticality
• The sparse parity matrix
• Core forging and local limit theorems for the k-core of random graphs
• How does the core sit inside the mantle?
• Maximum Weight Independent Sets and Matchings in Sparse Random Graphs. Exact Results using the Local Weak Convergence Method
• Recurrence of Distributional Limits of Finite Planar Graphs

Related

• The critical Karp--Sipser core of random graphs
• The critical Karp--Sipser core of Erdős--Rényi random graphs
• Component structure of the configuration model: barely supercritical\n case
• The Contact Process on Random Graphs and Galton-Watson Trees
• Critical window for connectivity in the Configuration Model