The distance profile of rooted and unrooted simply generated trees

Berzunza Ojeda, Gabriel ORCID: 0000-0002-7924-8775 and Janson, Svante (2022) The distance profile of rooted and unrooted simply generated trees. COMBINATORICS PROBABILITY & COMPUTING, 31 (3). pp. 368-410.

Access the full-text of this item by clicking on the Open Access link.

Official URL: http://dx.doi.org/10.1017/s0963548321000304

Abstract

It is well-known that the height profile of a critical conditioned Galton-Watson tree with finite offspring variance converges, after a suitable normalization, to the local time of a standard Brownian excursion. In this work, we study the distance profile, defined as the profile of all distances between pairs of vertices. We show that after a proper rescaling the distance profile converges to a continuous random function that can be described as the density of distances between random points in the Brownian continuum random tree. We show that this limiting function a.s. is H\"older continuous of any order $\alpha<1$, and that it is a.e. differentiable. We note that it cannot be differentiable at $0$, but leave as open questions whether it is Lipschitz, and whether is continuously differentiable on the half-line $(0,\infty)$. The distance profile is naturally defined also for unrooted trees contrary to the height profile that is designed for rooted trees. This is used in our proof, and we prove the corresponding convergence result for the distance profile of random unrooted simply generated trees. As a minor purpose of the present work, we also formalize the notion of unrooted simply generated trees and include some simple results relating them to rooted simply generated trees, which might be of independent interest.

Item Type:	Article
Additional Information:	58 pages
Uncontrolled Keywords:	Random trees, Brownian excursion, Local time, Profiles, Holder continuity
Divisions:	Faculty of Science and Engineering > School of Physical Sciences
Depositing User:	Symplectic Admin
Date Deposited:	04 Mar 2022 11:32
Last Modified:	18 Jan 2023 21:11
DOI:	10.1017/S0963548321000304
Open Access URL:	https://doi.org/10.1017/S0963548321000304
Related URLs:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3150106