The degree profile of random Pólya trees

DOI10.1016/J.JCTA.2012.04.007zbMATH Open1245.05115OpenAlexW2058208134MaRDI QIDQ439063FDOQ439063

Authors Bernhard Gittenberger, Veronika Kraus 

Publication date 1 August 2012

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

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

zbMATH Keywords

profilelocal timeBrownian excursionnodes of fixed degreeunlabelled trees

Mathematics Subject Classification ID

Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Vertex degrees (05C07)

Abstract: We investigate the profile of random P'olya trees of size $n$ when only nodes of degree $d$ are counted in each level. It is shown that, as in the case where all nodes contribute to the profile, the suitably normalized profile process converges weakly to a Brownian excursion local time. Moreover, we investigate the joint distribution of the number of nodes of degree $d_1$ and $d_2$ in the levels of the tree.

Recommendations

• scientific article; zbMATH DE number 7234299
• scientific article; zbMATH DE number 1222137
• On the profile of random trees
• The profile of unlabeled trees
• Scaling limits of random Pólya trees

Cites work

• scientific article; zbMATH DE number 19286 (Why is no real title available?)
• scientific article; zbMATH DE number 48952 (Why is no real title available?)
• scientific article; zbMATH DE number 140084 (Why is no real title available?)
• scientific article; zbMATH DE number 192908 (Why is no real title available?)
• scientific article; zbMATH DE number 1222137 (Why is no real title available?)
• scientific article; zbMATH DE number 1984549 (Why is no real title available?)
• scientific article; zbMATH DE number 1380604 (Why is no real title available?)
• scientific article; zbMATH DE number 1420950 (Why is no real title available?)
• scientific article; zbMATH DE number 3274494 (Why is no real title available?)
• scientific article; zbMATH DE number 3274518 (Why is no real title available?)
• scientific article; zbMATH DE number 3419161 (Why is no real title available?)
• A functional limit theorem for the profile of \(b\)-ary trees
• A functional limit theorem for the profile of search trees
• An asymptotic evaluation of the cycle index of a symmetric group
• Analytic combinatorics
• Average profiles, from tries to suffix-trees
• Branching processes, random trees, and a generalized scheme of arrangements of particles
• Brownian Excursion, the M/M/1 Queue and Their Occupation Times
• Brownian local times
• Conditional limit theorems for branching processes
• Excursions of Brownian motion and bessel processes
• Geodesics in large planar maps and in the Brownian map
• Laws of large numbers and tail inequalities for random tries and PATRICIA trees
• Martingales and profile of binary search trees
• Nodes of large degree in random trees and forests
• On the Explicit Form of the Density of Brownian Excursion Local Time
• On the covariance of the level sizes in random recursive trees
• On the distribution of the number of vertices in layers of random trees
• On the local time density of the reflecting Brownian bridge
• On the local time of the Brownian motion
• On the occupation time of Brownian excursion
• On the profile of random trees
• Probabilistic and fractal aspects of Lévy trees
• Profiles of Tries
• Profiles of random trees: Limit theorems for random recursive trees and binary search trees
• Profiles of random trees: Plane-oriented recursive trees
• Profiles of random trees: correlation and width of random recursive trees and binary search trees
• Random Trees
• Random real trees
• Scaling limits of Markov branching trees with applications to Galton-Watson and random unordered trees
• Singularity Analysis of Generating Functions
• The Brownian excursion multi-dimensional local time density
• The CRT is the scaling limit of unordered binary trees
• The Distribution of Patterns in Random Trees
• The SDE solved by local times of a Brownian excursion or bridge derived from the height profile of a random tree or forest
• The continuum random tree. I
• The continuum random tree. III
• The distribution of degrees in a large random tree
• The distribution of height and diameter in random non-plane binary trees
• The distribution of nodes of given degree in random trees
• The distribution of time spent by a standard excursion above a given level, with applications to ring polymers near a discontinuity in potential
• The height of random binary unlabelled trees
• The number of trees
• The profile of binary search trees
• The shape of unlabeled rooted random trees
• The topological structure of scaling limits of large planar maps
• Width and mode of the profile for some random trees of logarithmic height

Cited in

(9)

• A note on the scaling limits of random Pólya trees
• Scaling limits of random Pólya trees
• scientific article; zbMATH DE number 7234299 (Why is no real title available?)
• THE DEGREE PROFILE AND GINI INDEX OF RANDOM CATERPILLAR TREES
• Paths vs. stars in the local profile of trees
• The profile of unlabeled trees
• The degree profile and weight in Apollonian networks and \(k\)-trees
• The degree profile in some classes of random graphs that generalize recursive trees
• On the shape of random Pólya structures

This page was built for publication: The degree profile of random Pólya trees

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