标题： 随机图的临界Karp--Sipser核心 显示英文标题

标题： The critical Karp--Sipser core of random graphs

摘要： 我们研究由度数为$1,2$和$3$的顶点组成的配置模型中的 Karp--Sipser 核。 该核是通过递归地移除图中的叶子及其唯一的邻居得到的。 我们解决了 Bauer & Golinelli 的一个猜想，并证明在临界情况下，Karp--Sipser 核的大小为$ \approx \mathrm{Cst} \cdot \vartheta^{-2} \cdot n^{3/5}$，其中$\vartheta$是从$0$出发的线性布朗运动击中曲线$t \mapsto \frac{1}{t^{2}}$的时间。 我们的证明依赖于对与 Karp-Sipser 叶子移除算法相关的马尔可夫链在灭绝时间附近的详细多尺度分析。 显示英文摘要

摘要： 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.