Accessibility percolation

点击翻译按钮获取中文摘要

Accessibility percolation was introduced by Nowak and Krug as a model for evolution. In this model, a graph represents possible genotypes or phenotypes, with each vertex assigned a fitness value. The objective is to identify paths of vertices whose fitness values increase, signifying viable evolutionary pathways. In the 'House of Cards' model, fitness values are independently and identically distributed. In the 'Rough Mount Fuji' model, fitness values exhibit some form of drift as well as an independent and identically distributed component. The primary aim is to obtain theoretical insights into the asymptotic behaviour of the House of Cards and Rough Mount Fuji models across various settings, including on trees, the hypercube, random graphs, or even the integer lattice. Our first priority will be to investigate trees, since the lack of cycles reduces dependencies between different parts of the graph. In this case much is already known for the House of Cards model, so we will concentrate on the Rough Mount Fuji model. We can use a coupling with Bernoulli percolation, introduced by Hegarty and Martinsson on the hypercube but equally applicable to trees, to show that there is accessibility percolation for the RMF model on regular trees when the drift parameter is sufficiently large. The aim then is to show that there is no accessibility percolation when the drift parameter is small; we have an argument to do this by splitting paths into a fixed number of segments of equal length, and using the negative correlation of the segments. Next we aim to show that the critical value of the drift parameter, when the probability of percolation goes from zero to something strictly positive, is of order 1/n, where n is the number of children of each vertex of the tree. A hands-on combinatorial argument, where we bound the probability of labels being ordered by the probability that 0, 1, 2 or more i.i.d. random variables are out of order but still within close proximity, appears promising.Once we have established this result for the tree we aim to generalise it to the hypercube, which is a more complicated graph but can be viewed to a certain extent like a pair of non-regular trees glued together.The idea for Erdos-Rényi graphs is to use the second-moment method, similar to how it was applied to regular trees in the HoC setting scenario. Instead of only focusing on paths above the diagonal as in Roberts and Zhao paper, the analysis will now include paths between two diagonals. This is because in Erdos-Rényi graphs, there is added complexity where paths can repeatedly join and split. To address this, the approach is to consider paths within two diagonals, by doing so, we not only eliminate k-forks kind of paths, but we also account for situations where paths were initially separate and then joined at generation k'. There is also the possibility of paths can repeatedly join and split multiple times but, we expect that this type of increasing path is rare.