zbMATH — the first resource for mathematics

Limits of random trees. (English) Zbl 1299.05289
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.

05C80 Random graphs (graph-theoretic aspects)
05C05 Trees
05C42 Density (toughness, etc.)
Full Text: DOI arXiv
[1] Aldous, D., The continuum random tree III, Ann. Probab., 21, 248-289, (1993) · Zbl 0791.60009
[2] Benjamini, I.; Schramm, O., Recurrence of distributional limits of finite planar graphs, Electronic J. Probab., 6, 1-13, (2001) · Zbl 1010.82021
[3] G. Elek and G. Tardos, Limits of Trees, Oberwolfach Report No. 11/2010, 566-568. · Zbl 1010.82021
[4] Lyons, R., Asymptotic enumeration of spanning trees, Combinatorics, Probability and Computing, 14, 491-522, (2005) · Zbl 1076.05007
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.