Local limits of one-sided trees

Abstract: A finite emph{one-sided tree} of height

h

is defined as a rooted planar tree obtained by grafting branches on one side, say the right, of a spine, i.e. a linear path of length

h

starting at the root, such that the resulting tree has no simple path starting at the root of length greater than

h

. We consider the distribution

a u_{N}

on the set of one-sided trees

T

of fixed size

N

, such that the weight of

T

is proportional to

e^{- m u h (T)}

, where

m u

is a real constant and

h (T)

denotes the height of

T

. We show that, for

N

large,

a u_{N}

has a weak limit as a probability measure supported on infinite one-sided trees. The dependence of the limit measure

a u

on

m u

shows a transition at

m u_{0} = - l n 2

from a single spine phase for

m u l e q m u_{0}

to a multi-spine phase for

m u > m u_{0}

. Correspondingly, there is a transition in the volume growth rate of balls around the root as a function of radius from linear growth for

m u < m u_{0}

, to quadratic growth at

m u = m u_{0}

, and to qubic growth for

m u > m u_{0}

.

Recommendations

Cites work

Cited in

(1)

This page was built for publication: Local limits of one-sided trees