Domination between trees and application to an explosion problem (Q1323289)

The authors introduce the notion of stochastic ordering of rooted trees. Such a tree \(\Gamma\) dominates another \(\Gamma'\), if in any case i.i.d. random variables are attached to the vertices of the trees, the probability of the existence of a non-selfintersecting path starting from the root with any prescribed property is for \(\Gamma\) at least as big as for \(\Gamma'\). For a spherically symmetric tree \(\Gamma\), i.e. each vertex of \(\Gamma\) with distance \((n-1)\) from the root has the same number \(f(n)\) of offsprings, a necessary and sufficient condition of domination stating a corresponding relation between the sizes of the generations is proved. This criterion is applied to first-passage percolation on a tree. It is shown for symmetric trees with nondecreasing growth function \(f\) and exponentially distributed passage times, that explosion occurs, i.e. infinitely many vertices are reached in finite time, if and only if \(\sum f(n)^{-1} < \infty\). The condition for domination is used to treat also the case of general growth functions \(f\).