Abstract
Local convergence of bounded degree graphs was introduced by Benjamini and Schramm. This result was extended further by Lyons to bounded average degree graphs. In this paper we study the convergence of random tree sequences with given degree distributions. Denote by \({\mathcal{D}_n}\) the set of possible degree sequences of a labeled tree on n nodes. Let D n be a random variable on \({\mathcal{D}_n}\) and T(D n ) be a uniform random labeled tree with degree sequence D n . We show that the sequence T(D n ) converges in probability if and only if \({{\bf D}_n \rightarrow {\bf D} = ({\bf D}(i))^{\infty}_{i=1}}\), where \({{\bf D}(i) \sim {\bf D}(j), \mathbb{E}({\bf D}(1)) = 2}\) and D(1) is a random variable on \({\mathbb{N}^+}\).
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Aldous D., (1993) The continuum random tree III, Ann. Probab. 21, 248–289
D. Aldous, Exchangeability and Related Topics, Ecole d’Ete St Flour 1983. Springer Lecture Notes in Math 1117 (1985).
Benjamini I., Schramm O., (2001) Recurrence of distributional limits of finite planar graphs, Electronic J. Probab. 6, 1–13
I. Benjamini, O. Schramm and A. Shapira, Every minor-closed property of sparse graphs is testable, in: 40th Ann. ACM Symp. on Th. Comp. (2008), pp. 393–402.
B. Bollobás, Random Graphs, 2nd edition, Academic Press (1998).
C. Borgs, J. T. Chayes, L. Lovász, V. T. Sós and K. Vesztergombi, Counting graph homomorphisms, in: Topics in Discrete Mathematics (ed. M. Klazar, J. Kratochvil, M. Loebl, J. Matousek, R. Thomas, P. Valtr), Springer (2006), pp. 315–371.
S. Chatterjee, P. Diaconis and A. Sly, Random graphs with a given degree sequence, Ann. of Appl. Probab., 21 (2011), 1400–1435.
A. Deák, Limits of random trees, Acta Math. Hungar., 141 (2013), 185–201.
G. Elek, On limits of finite graphs, Combinatorica, 27 (2007), 503–507.
G. Elek and G. Tardos, Limits of Trees, Oberwolfach Report No. 11/2010, 566–568.
E. Hewitt and L. J. Savage, Symmetric measures on Cartesian products, Trans. Amer. Math. Soc., 80 (1955), 470–501.
L. Lovász and B. Szegedy, Limits of dense graph sequences, J. Combin. Theory Ser. B, 96 (2004), 933–957.
Lyons R., (2005) Asymptotic enumeration of spanning trees, Combinatorics. Probability and Computing 14, 491–522
Author information
Authors and Affiliations
Corresponding author
Additional information
Research was partially supported by the ERC Grant Nr.: 227701.
Rights and permissions
About this article
Cite this article
Deák, A. Limits of Random Trees. II. Acta Math. Hungar. 145, 205–219 (2015). https://doi.org/10.1007/s10474-014-0463-8
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10474-014-0463-8