Limits of random tree-like discrete structures

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 outerplanar 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.