Asymptotic size of the Karp-Sipser Core in Configuration Model
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909755000225792 |
|---|---|
| author | Chatterjee, Arnab Lee, Joon Hyung Zhu, Haodong |
| author_facet | Chatterjee, Arnab Lee, Joon Hyung Zhu, Haodong |
| contents | 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 \cite{BCC}. 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_19453 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Asymptotic size of the Karp-Sipser Core in Configuration Model Chatterjee, Arnab Lee, Joon Hyung Zhu, Haodong Combinatorics Discrete Mathematics Probability 05C80, 60C05, 68W20 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 \cite{BCC}. 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. |
| title | Asymptotic size of the Karp-Sipser Core in Configuration Model |
| topic | Combinatorics Discrete Mathematics Probability 05C80, 60C05, 68W20 |
| url | https://arxiv.org/abs/2508.19453 |