The critical Karp--Sipser core of random graphs
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2022
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866912495228157952 |
|---|---|
| author | Budzinski, Thomas Contat, Alice Curien, Nicolas |
| author_facet | Budzinski, Thomas Contat, Alice Curien, Nicolas |
| contents | 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 $ \approx \mathrm{Cst} \cdot \vartheta^{-2} \cdot n^{3/5}$ where $\vartheta$ is the hitting time of the curve $t \mapsto \frac{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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2212_02463 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | The critical Karp--Sipser core of random graphs Budzinski, Thomas Contat, Alice Curien, Nicolas Probability Combinatorics 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 $ \approx \mathrm{Cst} \cdot \vartheta^{-2} \cdot n^{3/5}$ where $\vartheta$ is the hitting time of the curve $t \mapsto \frac{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. |
| title | The critical Karp--Sipser core of random graphs |
| topic | Probability Combinatorics |
| url | https://arxiv.org/abs/2212.02463 |