Random enriched trees with applications to random graphs

zbMATH Open1393.60013arXiv1504.02006MaRDI QIDQ1658748FDOQ1658748

Authors: Benedikt Stufler 

Publication date: 15 August 2018

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: We establish limit theorems that describe the asymptotic local and global geometric behaviour of random enriched trees considered up to symmetry. We apply these general results to random unlabelled weighted rooted graphs and uniform random unlabelled $k$-trees that are rooted at a $k$-clique of distinguishable vertices. For both models we establish a Gromov--Hausdorff scaling limit, a Benjamini--Schramm limit, and a local weak limit that describes the asymptotic shape near the fixed root.

Full work available at URL: https://arxiv.org/abs/1504.02006

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• Graph limits of random unlabelled k-trees
• Limits of random tree-like discrete structures
• Asymptotic properties of random unlabelled block-weighted graphs
• Limits of random trees
• The continuum random tree is the scaling limit of unlabeled unrooted trees

zbMATH Keywords

symmetriesrandom graphsscaling limitslocal weak limits

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05)

Cites Work

• Recurrence of distributional limits of finite planar graphs
• Graph theory
• Analytic combinatorics
• Combinatorial stochastic processes. Ecole d'Eté de Probabilités de Saint-Flour XXXII -- 2002.
• A course in metric geometry
• Uniform infinite planar triangulations
• Local convergence of large critical multi-type Galton-Watson trees and applications to random maps
• Recurrence of bipartite planar maps
• Graph classes with given 3-connected components: asymptotic enumeration and random graphs
• Asymptotic study of subcritical graph classes
• Random Trees
• The Brownian map is the scaling limit of uniform random plane quadrangulations
• Title not available (Why is that?)
• Extremal Parameters in Sub-Critical Graph Classes
• Asymptotic Enumeration of Spanning Trees
• Percolation on uniform infinite planar maps
• Uniqueness and universality of the Brownian map
• Title not available (Why is that?)
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• Probabilistic and fractal aspects of Lévy trees
• Simply generated trees, conditioned Galton-Watson trees, random allocations and condensation
• Random maps, coalescing saddles, singularity analysis, and Airy phenomena
• Scaling limits of random planar maps with a unique large face
• The topological structure of scaling limits of large planar maps
• \(\Gamma \)-species and the enumeration of \(k\)-trees
• The continuum random tree. III
• Counting unlabeled \(k\)-trees
• Enumerating k-trees
• An asymptotic analysis of labeled and unlabeled \(k\)-trees
• Limiting distribution for distances in \(k\)-trees
• The number of labeled k-dimensional trees
• The number of labeled k-trees
• Scaling limits of Markov branching trees with applications to Galton-Watson and random unordered trees
• The specification of 2-trees
• Asymptotic fringe distributions for general families of random trees
• Random cutting and records in deterministic and random trees
• Enumeration and asymptotic properties of unlabeled outerplanar graphs
• Une théorie combinatoire des séries formelles
• Local limit of labeled trees and expected volume growth in a random quadrangulation
• A view from infinity of the uniform infinite planar quadrangulation
• Title not available (Why is that?)
• The continuum random tree. I
• Scaling limits of random graphs from subcritical classes
• Scaling limits of random trees and planar maps
• Chernoff-type bound for finite Markov chains
• Title not available (Why is that?)
• A limit theorem for the contour process of conditioned Galton-Watson trees
• On the diameter of random planar graphs
• Boltzmann Samplers, Pólya Theory, and Cycle Pointing
• Enumeration of non-separable graphs
• Sub-Gaussian tail bounds for the width and height of conditioned Galton-Watson trees
• A Generalization of the Ballot Problem and its Application in the Theory of Queues
• The CRT is the scaling limit of unordered binary trees
• Counting rooted trees: the universal law \(t(n)\sim C\rho^{-n} n^{-3/2}\)
• Distances between pairs of vertices and vertical profile in conditioned Galton-Watson trees
• Scaling limits of random Pólya trees
• Scaling limits of \(k\)-ary growing trees
• Une nouvelle demonstration combinatoire des formules d'inversion de Lagrange
• Joint convergence of random quadrangulations and their cores
• Title not available (Why is that?)
• Scaling limits for a family of unrooted trees
• The Brownian plane with minimal neck baby universe
• The degree distribution in unlabelled 2-connected graph families
• Vertex Degrees in Planar Maps

Cited In (15)

• Asymptotic properties of random unlabelled block-weighted graphs
• Limits of random tree-like discrete structures
• Scaling Limits of Markov-Branching Trees and Applications
• Graph limits of random unlabelled k-trees
• Rerooting multi-type branching trees: the infinite spine case
• Decorated stable trees
• Exact-Size Sampling of Enriched Trees in Linear Time
• On large‐girth regular graphs and random processes on trees
• A branching process approach to level‐k phylogenetic networks
• Graphon convergence of random cographs
• Simply generated unrooted plane trees
• A decorated tree approach to random permutations in substitution-closed classes
• Graph limits of random graphs from a subset of connected \(k\)-trees
• Speeding up non-Markovian first-passage percolation with a few extra edges
• Asymptotic enumeration and limit laws for multisets: the subexponential case

This page was built for publication: Random enriched trees with applications to random graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1658748)