Hostname: page-component-745bb68f8f-v2bm5 Total loading time: 0 Render date: 2025-02-11T09:23:48.823Z Has data issue: false hasContentIssue false
  • English
  • Français

Small trees in supercritical random forests

Part of: Graph theory Combinatorial probability

Published online by Cambridge University Press:  29 September 2020

Tao Lei
Tao Lei*
Affiliation:
Department of Mathematics and Statistics, McGill University, 805 Sherbrooke Street West, Montréal, QCH3A 0B9, Canada URL: http://www.math.mcgill.ca/~tlei/
*
e-mail: tao.lei@mail.mcgill.ca
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 study the scaling limit of a random forest with prescribed degree sequence in the regime that the largest tree consists of all but a vanishing fraction of nodes. We give a description of the limit of the forest consisting of the small trees, by relating a plane forest to a marked cyclic forest and its corresponding skip-free walk.

Keywords

Random forestscontinuum random treesdegree sequenceGHP convergence

MSC classification

Primary: 60C05: Combinatorial probability
Secondary: 05C05: Trees 05C80: Random graphs
Type
Article
Information
Canadian Mathematical Bulletin , Volume 64 , Issue 3 , September 2021 , pp. 605 - 623
Check for updates
Copyright
© Canadian Mathematical Society 2020

References

Abraham, R., Delmas, J.-F., and Hoscheit, P., A note on the Gromov–Hausdorff–Prokhorov distance between (locally) compact metric measure spaces . Electron. J. Probab. 18(2013), no. 14, 21. http://dx.doi.org/10.1214/EJP.v18-2116 CrossRefGoogle Scholar
Aldous, D., The continuum random tree. I . Ann. Probab. 19(1991), 1–28.CrossRefGoogle Scholar
Aldous, D., The continuum random tree. II. an overview . In: Stochastic analysis (Durham, 1990), London Mathematical Society Lecture Note Series, 167, Cambridge University Press, Cambridge, UK, 1991, pp. 23–70. http://dx.doi.org/10.1017/CB9780511662980.003 CrossRefGoogle Scholar
Aldous, D., The continuum random tree. III . Ann. Probab. 21(1993), 248–289.10.1214/aop/1176989404CrossRefGoogle Scholar
Aldous, D. J., Exchangeability and related topics . In: École d’été de probabilités de Saint-Flour, XIII—1983, Lecture Notes in Mathematics, 1117, Springer, Berlin, Germany, 1985, pp.1–198. http://dx.doi.org/10.1007/BFb0099421 CrossRefGoogle Scholar
Broutin, N. and Marckert, J.-F., Asymptotics of trees with a prescribed degree sequence and applications . Random Struct. Algor. 44(2014), 290–316. http://dx.doi.org/10.1002/rsa.20463 CrossRefGoogle Scholar
Cheplyukova, I. A., The emergence of a giant tree in a random forest . Discrete Math. Appl. 8(1998), 17–33. http://dx.doi.org/10.1515/dma.1998.8.1.17 CrossRefGoogle Scholar
Diaconis, P. and Freedman, D., Finite exchangeable sequences . Ann. Probab. 8(1980), 745–764.CrossRefGoogle Scholar
Durrett, R., Probability: theory and examples. 4th ed., Cambridge Series in Statistical and Probabilistic Mathematics, 31, Cambridge University Press, Cambridge, UK, 2010. http://dx.doi.org/10.1017/CB09780511779398 CrossRefGoogle Scholar
Evans, S. N., Probability and real trees . Lecture Notes in Mathematics, 1920, Springer, Berlin, Germany, 2008. http://dx.doi.org/10.1007/978-3-540-74798-7 CrossRefGoogle Scholar
Le Gall, J.-F., Random trees and applications . Probab. Surv. 2(2005), 245–311. http://dx.doi.org/10.1214/154957805100000140 CrossRefGoogle Scholar
Lei, T., Scaling limit of random forests with prescribed degree sequences . Bernouilli 25(2019), 2409–2438.CrossRefGoogle Scholar
McDiarmid, C., Concentration . In: Probabilistic methods for algorithmic discrete mathematics, Algorithms Combinations, 16, Springer, Berlin, Germany, 1998, pp. 195–248. http://dx.doi.org/10.1007/978-3-662-12788-9-6 CrossRefGoogle Scholar
Mörters, P. and Peres, Y., Brownian motion . Cambridge Series in Statistical and Probabilistic Mathematics, 30, Cambridge University Press, Cambridge, UK, 2010. http://dx.doi.org/10.1017/CBO9780511750489 Google Scholar
Pavlov, Y. L., Random forests . VSP, Utrecht, 2000.10.1515/9783110941975CrossRefGoogle Scholar
Pitman, J., Combinatorial stochastic processes . Lecture Notes in Mathematics, 1875, Springer-Verlag, Berlin, Germany, 2006.Google Scholar
Schilling, R. L. and Partzsch, L., Brownian motion . De Gruyter, Berlin, Germany, 2012. http://dx.doi.org/10.1515/9783110278989 CrossRefGoogle Scholar