Extremal paths on a random Cayley tree

We investigate the statistics of extremal path(s) (both the shortest and th e longest) from the root to the bottom of a Cayley tree. The lengths of the edges are assumed to be independent identically distributed random variabl es drawn from a distribution rho (I). Besides, the number of branches from any node is also random. Exact results are derived for arbitrary distributi on rho (l). Ln particular, for the binary {0,1} distribution rho (l) = p de lta (l,1) + (1-p)delta (l,0), we show that as p increases, the minimal leng th undergoes an unbinding transition from a "localized'' phase to a ''movin g'' phase at the critical value, p = p(c) = 1 - b(-1), where b is the avera ge branch number of the tree. As the height n of the tree increases, the mi nimal length saturates to a finite constant in the localized phase (p<p(c)) , but increases linearly as v(min)(p)n in the moving phase (p>p(c)) where t he velocity v(min)(p) is determined via a front selection mechanism. At p = p(c), the minimal length grows with II in an extremely slow double-logarit hmic 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 satisf y a general duality relation, v(min)(p) + v(max)(1-p) = 1, Which is also va lid for directed paths on finite-dimensional lattices.