Hostname: page-component-7b7567c8c-wxvwp Total loading time: 0 Render date: 2026-11-17T19:24:48.987Z Has data issue: false hasContentIssue false

Convergence of directed random graphs to the Poisson-weighted infinite tree

Published online by Cambridge University Press:  21 June 2016

Katja Gabrysch*
Affiliation:
Uppsala University
*
* Postal address: Department of Mathematics, Uppsala University, PO Box 480, 751 06 Uppsala, Sweden. Email address: katja.gabrysch@math.uu.se
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We consider a directed graph on the integers with a directed edge from vertex i to j present with probability n-1, whenever i < j, independently of all other edges. Moreover, to each edge (i, j) we assign weight n-1(j - i). We show that the closure of vertex 0 in such a weighted random graph converges in distribution to the Poisson-weighted infinite tree as n → ∞. In addition, we derive limit theorems for the length of the longest path in the subgraph of the Poisson-weighted infinite tree which has all vertices at weighted distance of at most ρ from the root.

Information

Type
Research Papers
Copyright
Copyright © Applied Probability Trust 2016