Limits of random trees

DOI10.1007/S10474-013-0321-0MaRDI QIDQ2250844zbMATH OpenOpenAlexFDO

Authors A. Deák

Publication date 21 July 2014

Published in Acta Mathematica Hungarica (Search for Journal in Brave)

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

zbMATH Keywords

random treesparse graph limit

Mathematics Subject Classification ID

Trees (05C05) Density (toughness, etc.) (05C42) Random graphs (graph-theoretic aspects) (05C80)

Abstract: Local convergence of bounded degree graphs was introduced by Benjamini and Schramm. This result was extended further by Lyons to bounded average degree graphs. In this paper, we study the convergence of a random tree sequence where the probability of a given tree is proportional to $pro{d}_{v_{i}inV(T)}d(v_i)!$. We show that this sequence is convergent and describe the limit object, which is a random infinite rooted tree.

Review text

There has been much recent interest in limit objects for sequences of graphs, with the case of sparse graphs tending to be more technically problematic than the dense cases. In the paper under review, the author considers the case where an \(n\)-vertex tree \(T_{n}\) is chosen at random, with any particular \(n\)-vertex tree \(T\) with degrees \((d_{i})\) having probability \[ \mathbb{P}(T_{n}=T) =\frac{\prod_{i=1}^{n} d_{i}!}{(n-2)!{3n-3\choose n-2}} \] (the normalising constant is justified in the paper). The author shows that this sequence is convergent and describes the limit object. The proofs proceed by estimating the expected maximum degree of a tree from this model -- it is about \(\log_{3}(n)\) -- and some detailed estimates on the density of various labelled subgraphs. The approach taken is different from that in some earlier articles on the topic.

Recommendations

• Limits of random trees. II
• Tree limits and limits of random trees
• The maximum degree in a random tree and related problems
• The continuum random tree. I
• Limit theorems for random trees.

Cites work

• Asymptotic Enumeration of Spanning Trees
• Recurrence of distributional limits of finite planar graphs
• The continuum random tree. III

Cited in

(20)

• Limit distribution for the maximum degree of a random recursive tree
• Random enriched trees with applications to random graphs
• Trees and generalised inverse limits on intervals
• Limit distributions and random trees derived from the birthday problem with unequal probabilities
• Random tree-weighted graphs
• On a tail bound for analyzing random trees
• Limits of random tree-like discrete structures
• Limits of random trees. II
• Limit laws for functions of fringe trees for binary search trees and random recursive trees
• Modeling limits in hereditary classes: reduction and application to trees
• Convergence and limits of finite trees
• Limit theorems for random trees.
• And/or trees: A local limit point of view
• Probability bounds given by hypercherry trees
• Normal Limit Law for Protected Node Profile of Random Recursive Trees
• Graph limits of random graphs from a subset of connected k-trees
• Tree limits and limits of random trees
• scientific article; zbMATH DE number 7703245 (Why is no real title available?)
• On the limit of large girth graph sequences
• Precise logarithmic asymptotics for the right tails of some limit random variables for random trees

This page was built for publication: Limits of random trees

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