arXiv:2611.00123v1 Announce Type: new Abstract: We study a growing random graph in which each new vertex chooses a uniformly random parent, joins that parent with probability $r\in(0,1]$, and independently joins each of the parent's current neighbors with probability $p\in(0,1)$. Let $p_c$ be the unique solution of $p_c e^{p_c}=1$. For $0<p<p_c$, we prove that the empirical degree distribution converges in probability to the stationary distribution $\pi$ of an explicit reset-and-growth Markov chain. Its upper tail satisfies $\pi((y,\infty))\sim C_{p,r}y^{-\kappa}$, where $C_{p,r}>0$ and $\kappa>0$ solves $p^\kappa+p\kappa=1$. This confirms predictions from physics (Lambiotte, Krapivsky, Bhat and Redner, \textit{Physical Review Letters}, 2016). We further show that for every fixed radius $\ell$ and $p<p_c$, the empirical distribution of induced rooted $\ell$-neighborhoods converges to the invariant law of a graph-valued reset-and-growth Markov process. We give an explicit construction of the limiting graph using a marked ancestral genealogy. Its root component is almost surely finite for $r<1$, and infinite with exactly one end for $r=1$. Moreover, for every $0<p<1$, both the fixed-vertex degrees and the maximum degree grow on the scale $t^p$, and the vertex of maximum degree is eventually unique and persistent.
Continue to arXiv Mathematics →You are being forwarded in 6s — stay on this page