Accessibility percolation

可及性渗流是由Nowak和Krug作为演化模型引入的。在这个模型中，一个图代表可能的基因类型或表型，每个顶点都分配了一个适应值。目标是确定适应值增加的顶点的路径，这意味着可行的进化路径。在“纸牌屋”模型中，适应值是独立且均匀分布的。在“粗糙的富士山”模型中，适应值表现出某种形式的漂移，以及一个独立且相同分布的分量。主要目的是获得对纸牌屋和粗糙富士山模型在各种设置下的渐近行为的理论见解，包括在树、超立方体、随机图，甚至整数格上。我们的首要任务将是研究树，因为没有圈减少了图的不同部分之间的依赖。在这种情况下，很多人已经知道了纸牌屋的模式，所以我们将集中在粗糙的富士山模式。我们可以使用Hegarty和Martinsson在超立方体上引入的与Bernoulli渗流的耦合，证明了当漂移参数足够大时，RMF模型在规则树上存在可达渗流。然后，我们的目标是证明当漂移参数很小时不存在可访问性渗流；我们有一个论据来做到这一点，方法是将路径拆分成固定数量的相等长度的段，并使用段的负相关性。接下来，我们的目标是证明当渗流概率从零变为某个严格正数时，漂移参数的临界值是1/n阶的，其中n是树的每个顶点的子代的数目。一种实际操作的组合论证，其中我们定义了标签被排序的概率为0，1，2或更多I.I.D.的概率。随机变量是无序的，但仍然很接近，这似乎很有希望。一旦我们为树建立了这个结果，我们的目标是将其推广到超立方体，这是一个更复杂的图，但在一定程度上可以被视为一对粘合在一起的非规则树。Erdos-Rényi图的思想是使用二阶矩方法，类似于它在特殊情况下应用于规则树的方法。现在的分析将包括两条对角线之间的路径，而不是像Roberts和赵的论文中那样只关注对角线上方的路径。这是因为在Erdos-Rényi图中，路径可以重复连接和分裂，这就增加了复杂性。为了解决这个问题，方法是考虑两条对角线内的路径，通过这样做，我们不仅消除了k-forks类型的路径，而且还考虑了路径最初是分开的，然后在第k代连接的情况。路径也有可能重复连接和分割多次，但我们预计这种类型的递增路径很少见。

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.