DMTCS Proceedings, Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities

Font Size:  Small  Medium  Large

On the spectral dimension of random trees

Bergfinnur Durhuus, Thordur Jonsson, John Wheater

Abstract


We determine the spectral dimensions of a variety of ensembles of infinite trees. Common to the ensembles considered is that sample trees have a distinguished infinite spine at whose vertices branches can be attached according to some probability distribution. In particular, we consider a family of ensembles of combs, whose branches are linear chains, with spectral dimensions varying continuously between 1 and 3/2. We also introduce a class of ensembles of infinite trees, called generic random trees, which are obtained as limits of ensembles of finite trees conditioned to have fixed size N, as N→ ∞. Among these ensembles is the so-called uniform random tree. We show that generic random trees have spectral dimension ds=4/3.

Full Text: PDF

Valid XHTML 1.0 Transitional