Extremal paths on a random cayley tree

Abstract

We investigate the statistics of extremal path(s) (both the shortest and the longest) from the root to the bottom of a Cayley tree. The lengths of the edges are assumed to be independent identically distributed random variables drawn from a distribution rho(l). Besides, the number of branches from any node is also random. Exact results are derived for arbitrary distribution rho(l). In particular, for the binary 0,1 distribution rho(l)=pdelta(l,1)+(1-p)delta(l, 0), we show that as p increases, the minimal length undergoes an unbinding transition from a "localized" phase to a "moving" phase at the critical value, p=p(c)=1-b(-1), where b is the average branch number of the tree. As the height n of the tree increases, the minimal length saturates to a finite constant in the localized phase (p p(c)) where the velocity v(min)(p) is determined via a front selection mechanism. At p=p(c), the minimal length grows with n in an extremely slow double-logarithmic fashion. The length of the maximal path, on the other hand, increases linearly as v(max)(p)n for all p. The maximal and minimal velocities satisfy a general duality relation, v(min)(p)+v(max)(1-p)=1, which is also valid for directed paths on finite-dimensional lattices.