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.
%0 Journal Article
%1 Nowak2013Accessibility
%A Nowak, S.
%A Krug, J.
%D 2013
%J EPL (Europhysics Letters)
%K accessibility-percolation, percolation biological-networks tree-graphs
%N 6
%P 66004+
%R 10.1209/0295-5075/101/66004
%T Accessibility percolation on n-trees
%U http://dx.doi.org/10.1209/0295-5075/101/66004
%V 101
%X 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.
@article{Nowak2013Accessibility,
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.}},
added-at = {2019-06-10T14:53:09.000+0200},
archiveprefix = {arXiv},
author = {Nowak, S. and Krug, J.},
biburl = {https://www.bibsonomy.org/bibtex/21d0dc9c1cf2d50136dd5b456e8da2aa6/nonancourt},
citeulike-article-id = {12002869},
citeulike-linkout-0 = {http://dx.doi.org/10.1209/0295-5075/101/66004},
citeulike-linkout-1 = {http://arxiv.org/abs/1302.1423},
citeulike-linkout-2 = {http://arxiv.org/pdf/1302.1423},
day = 1,
doi = {10.1209/0295-5075/101/66004},
eprint = {1302.1423},
interhash = {2cbd23c243f4b2c1ec8a56e0135d294f},
intrahash = {1d0dc9c1cf2d50136dd5b456e8da2aa6},
issn = {1286-4854},
journal = {EPL (Europhysics Letters)},
keywords = {accessibility-percolation, percolation biological-networks tree-graphs},
month = mar,
number = 6,
pages = {66004+},
posted-at = {2013-02-07 12:39:48},
priority = {2},
timestamp = {2019-08-01T16:07:48.000+0200},
title = {{Accessibility percolation on n-trees}},
url = {http://dx.doi.org/10.1209/0295-5075/101/66004},
volume = 101,
year = 2013
}