Accessible Percolation with Crossing Valleys on n-ary Trees (2019)
In this paper we study a variation of the accessibility percolation model, this is also motivated by evolutionary biology and evolutionary computation. Consider a tree whose vertices are labeled with random numbers. We study the probability of having a monotone subsequence of a path from the root to a leaf, where any k consecutive vertices in the path contain at least one vertex of the subsequence. An n-ary tree, with height h, is a tree whose vertices at distance at most h − 1 to the root have n children. For the case of n-ary trees, we prove that, as h tends to infinity the probability of having such subsequence: tends to 1, if n grows significantly faster than ek ; and tends to 0, if n grows significantly slower than