论文标题
随机图的关键karp-副手核心
The critical Karp--Sipser core of random graphs
论文作者
论文摘要
我们研究了由配置模型制成的随机图的KARP-sipper核心，其顶点为$ 1,2 $和$ 3 $。该核心是通过递归去除叶子及其独特邻居来获得的。我们解决了Bauer＆Golinelli的猜想，并证明，在关键时期，karp-sipser核心的尺寸$ \ of Mathrm {cst} \ cdot \ cdot \ vartheta^{ - 2} \ cdot n^{3/5} $ wery $ \ vartheta $ \ frac {1} {t^{2}} $通过线性布朗运动开始于$ 0 $。我们的证明依赖于对与karp sipper叶拆卸算法相关的马尔可夫链的详细多尺度分析，接近其灭绝时间。
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.
