Uniform duplication-divergence random graphs I: Degrees and Local Limits
Abstract
We study a growing random graph in which each new vertex chooses a uniformly random parent, joins that parent with probability r∈(0,1], and independently joins each of the parent's current neighbors with probability p∈(0,1). Let pc be the unique solution of pc epc=1. For 0<p<pc, we prove that the empirical degree distribution converges in probability to the stationary distribution π of an explicit reset-and-growth Markov chain. Its upper tail satisfies π((y,∞))∼ Cp,ry−κ, where Cp,r>0 and κ>0 solves pκ+pκ=1. This confirms predictions from physics (Lambiotte, Krapivsky, Bhat and Redner, \textit{Physical Review Letters}, 2016). We further show that for every fixed radius ℓ and p<pc, the empirical distribution of induced rooted ℓ-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 tp, and the vertex of maximum degree is eventually unique and persistent.
Related
- Edge universality of random regular graphs of growing degrees
- Central Limit Theorem of Maximum Weight Matching on Random Graphs with Prescribed Degrees
- Sharp detection thresholds for random geometric graphs with polynomial average degrees
- Uniform Stability of Scott-Vogelius Elements on Three-Dimensional Freudenthal Meshes in Degrees Four and Five: Resolving the Farrell-Mitchell-Scott Conjecture
- Approximating Distributions on Vertex Degrees in Random Hypergraphs via Stein's Method
BibTeX
@misc{dey2026uniform,
title = {{Uniform duplication-divergence random graphs I: Degrees and Local Limits}},
author = {Partha S. Dey and Neeladri Maitra and Jaya M. Manthripragada and Grigory Terlov},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.00123},
eprint = {2611.00123},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.00123},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Uniform duplication-divergence random graphs I: Degrees and Local Limits
AU - Partha S. Dey
AU - Neeladri Maitra
AU - Jaya M. Manthripragada
AU - Grigory Terlov
PY - 2026
DA - 2026/11/01
PB - arXiv
DO - 10.48550/arxiv.2611.00123
UR - https://arxiv.org/abs/2611.00123
AB - We study a growing random graph in which each new vertex chooses a uniformly random parent, joins that parent with probability r∈(0,1], and independently joins each of the parent's current neighbors with probability p∈(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 π of an explicit reset-and-growth Markov chain. Its upper tail satisfies π((y,∞))∼ C_p,ry^−κ, where C_p,r>0 and κ>0 solves p^κ+pκ=1. This confirms predictions from physics (Lambiotte, Krapivsky, Bhat and Redner, \textit{Physical Review Letters}, 2016). We further show that for every fixed radius ℓ and p<p_c, the empirical distribution of induced rooted ℓ-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.
ER -