Hostname: page-component-cd9895bd7-hc48f Total loading time: 0 Render date: 2024-12-23T10:28:59.447Z 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: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

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

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

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