Paperlane

no. 6 · Monday 2 November 2026

Transition in the asymptotics of the joint degree distribution of uniform recursive directed acyclic graphs

Rafael Engel

math.PR · v2 · 11 pp

Abstract

We study the asymptotic joint degree distribution of uniformly chosen vertices in uniform recursive directed acyclic graphs, a natural generalization of random recursive trees. Here, a graph is built by adding vertices one-by-one and connecting each new vertex to $m\in\mathbb{N}$ uniformly selected vertices already present. Using a representation based on Kingman's coalescent, we establish a transition in the joint degree distribution at the threshold $(m+1)\log n$, arising from the interplay between geometric degree asymptotics and fluctuations in the coalescent construction. Our results extend previously known asymptotics toward this threshold and provide a unified description of the transition, including mixed regimes where prescribed degrees lie on different scales.

comments
11 pages. The present version and arXiv:2606.09386 supersede the first submission
fields
Probability
pdf ↗ page arXiv:2503.05829 ↗