Hostname: page-component-78c5997874-t5tsf Total loading time: 0 Render date: 2024-11-17T10:16:19.993Z Has data issue: false hasContentIssue false
  • English
  • Français

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

Part of: Combinatorial probability Graph theory Limit theorems

Published online by Cambridge University Press:  21 June 2016

Katja Gabrysch
Katja Gabrysch*
Affiliation:
Uppsala University
*
* Postal address: Department of Mathematics, Uppsala University, PO Box 480, 751 06 Uppsala, Sweden. Email address: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

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.

Keywords

Directed random graphPoisson-weighted infinite treerooted geometric graph

MSC classification

Primary: 05C80: Random graphs
Secondary: 60F05: Central limit and other weak theorems 60C05: Combinatorial probability
Type
Research Papers
Information
Journal of Applied Probability , Volume 53 , Issue 2 , June 2016 , pp. 463 - 474
Copyright
Copyright © Applied Probability Trust 2016 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Addario-Berry, L. and Ford, K. (2013).Poisson–Dirichlet branching random walks.Ann. Appl. Prob. 23, 283–307.Google Scholar
[2]Addario-Berry, L. and Reed, B. (2009).Minima in branching random walks.Ann. Prob. 37, 1044–1079.CrossRefGoogle Scholar
[3]Aldous, D. (1992).Asymptotics in the random assignment problem.Prob. Theory Relat. Fields 93, 507–534.CrossRefGoogle Scholar
[4]Aldous, D. and Steele, J. M. (2004).The objective method: probabilistic combinatorial optimization and local weak convergence. In Probability on Discrete Structures (Encyclopaedia Math. Sci.110), Springer, Berlin, pp.1–72.Google Scholar
[5]Athreya, K. B. and Ney, P. E. (2004).Branching Processes.Dover, Mineola, NY.Google Scholar
[6]Bachmann, M. (2000).Limit theorems for the minimal position in a branching random walk with independent logconcave displacements.Adv. Appl. Prob. 32, 159–176.Google Scholar
[7]Barak, A. B. and Erdős, P. (1984).On the maximal number of strongly independent vertices in a random acyclic directed graph.SIAM J. Algebraic Discrete Methods 5, 508–514.Google Scholar
[8]Billingsley, P. (1999).Convergence of Probability Measures, 2nd edn.John Wiley, New York.CrossRefGoogle Scholar
[9]Bollobás, B. and Brightwell, G. (1997).The structure of random graph orders.SIAM J. Discrete Math. 10, 318–335.Google Scholar
[10]Bramson, M. and Zeitouni, O. (2009).Tightness for a family of recursion equations.Ann. Prob. 37, 615–653.Google Scholar
[11]Chauvin, B. and Drmota, M. (2006).The random multisection problem, travelling waves and the distribution of the height of m-ary search trees.Algorithmica 46, 299–327.Google Scholar
[12]Denisov, D., Foss, S. and Konstantopoulos, T. (2012).Limit theorems for a random directed slab graph.Ann. Appl. Prob. 22, 702–733.Google Scholar
[13]Foss, S. and Konstantopoulos, T. (2003).Extended renovation theory and limit theorems for stochastic ordered graphs.Markov Process. Related Fields 9, 413–468.Google Scholar
[14]Itoh, Y. and Krapivsky, P. L. (2012).Continuum cascade model of directed random graphs: traveling wave analysis.J. Phys. A 45, 455002.Google Scholar
[15]Newman, C. M. (1992).Chain lengths in certain random directed graphs.Random Structures Algorithms 3, 243–253.Google Scholar