Limits of random tree-like discrete structures

Stufler, Benedikt (2020): Limits of random tree-like discrete structures. In: Probability Surveys, Vol. 17: pp. 318-477

Abstract

Many random recursive discrete structures may be described by a single generic model. Adopting this perspective allows us to elegantly prove limits for these structures as instances of general underlying principles, and describe their phase diagrams using a unified terminology. We illustrate this by a selection of examples. We consider random outer-planar maps sampled according to arbitrary weights assigned to their inner faces, and classify in complete generality distributional limits for both the asymptotic local behaviour near the root-edge and near a uniformly at random drawn vertex. We consider random connected graphs drawn according to weights assigned to their blocks and establish a local weak limit. We also apply our framework to recover in a probabilistic way a central limit theorem for the size of the largest 2-connected component in random graphs from planar-like classes. We prove local convergence of random k-dimensional trees and establish both scaling limits and local weak limits for random planar maps drawn according to Boltzmann-weights assigned to their 2-connected components.

• Item Type: Journal article
• Faculties: Mathematics, Computer Science and Statistics > Mathematics
• Subjects: 500 Science > 510 Mathematics
• ISSN: 1549-5787
• Language: English