The degree profile of random Pólya trees

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

Authors: Bernhard Gittenberger, Veronika Kraus 

Publication date: 1 August 2012

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

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.

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

Recommendations

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

zbMATH Keywords

profilelocal timeBrownian excursionnodes of fixed degreeunlabelled trees

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (4)

• A note on the scaling limits of random Pólya trees
• THE DEGREE PROFILE AND GINI INDEX OF RANDOM CATERPILLAR TREES
• The profile of unlabeled trees
• Title not available (Why is that?)

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)