Accessibility percolation on n-trees

Abstract

Accessibility percolation is a new type of percolation problem inspired by evolutionary biology. To each vertex of a graph a random number is assigned and a path through the graph is called accessible if all numbers along the path are in ascending order. For the case when the random variables are independent and identically distributed, we derive an asymptotically exact expression for the probability that there is at least one accessible path from the root to the leaves in an $n$-tree. This probability tends to 1 (0) if the branching number is increased with the height of the tree faster (slower) than linearly. When the random variables are biased such that the mean value increases linearly with the distance from the root, a percolation threshold emerges at a finite value of the bias.

6 pages, 4 figures

References in corpus (6)

• Quantitative analyses of empirical fitness landscapes
• Evolutionary accessibility of mutational pathways
• The pace of evolution across fitness valleys
• Records and sequences of records from random variables with a linear trend
• Evolutionary accessibility in tunably rugged fitness landscapes
• Retention capacity of random surfaces

Cited by in corpus (12)

• Adaptation in tunably rugged fitness landscapes: The Rough Mount Fuji Model
• Universality classes of interaction structures for NK fitness landscapes
• Evolutionary accessibility of modular fitness landscapes
• Analysis of adaptive walks on NK fitness landscapes with different interaction schemes
• The number of accessible paths in the hypercube
• Phase transition in random adaptive walks on correlated fitness landscapes
• Multidimensional epistasis and the transitory advantage of sex
• Increasing paths in regular trees
• Accessibility Percolation on Cartesian Power Graphs
• Evolutionary accessibility of random and structured fitness landscapes
• On the existence of accessibility in a tree-indexed percolation model
• RMF accessibility percolation on oriented graphs