Accessibility percolation

可达性渗透是由Nowak和Krug作为进化模型引入的。在这个模型中，一个图表示可能的基因型或表型，每个顶点都分配了一个适应度值。我们的目标是确定路径的顶点，其健身值增加，标志着可行的进化途径。在“纸牌屋”模型中，适应度值是独立同分布的。在“粗糙富士山”模型中，适应值表现出某种形式的漂移以及独立和同分布的组件。主要目的是获得理论上的见解，在不同的设置，包括树木，超立方体，随机图，甚至整数格的纸牌屋和粗糙富士山模型的渐近行为。我们的首要任务是研究树，因为缺少圈会减少图的不同部分之间的依赖性。在这种情况下，很多人已经知道了纸牌屋模型，所以我们将集中在粗糙富士山模型。我们可以使用Hegarty和Martinsson在超立方体上引入的Bernoulli渗流的耦合，但同样适用于树，以表明当漂移参数足够大时，规则树上的RMF模型存在可达性渗流。然后，我们的目的是表明，有没有可达性渗流时，漂移参数是小的，我们有一个参数来做到这一点，通过分裂成一个固定数量的等长段的路径，并使用负相关的部分。接下来，我们的目标是表明，漂移参数的临界值，当渗透的概率从零到严格的积极的东西，是为了1/n，其中n是每个顶点的树的孩子的数量。一个动手组合的论点，我们将标签的概率按0，1，2或更多i.i.d.随机变量是无序的，但仍然非常接近，似乎是有希望的。一旦我们建立了树的这个结果，我们的目标是将其推广到超立方体，这是一个更复杂的图，但在一定程度上可以看作是一对非正则树粘在一起。Erdos-Rényi图的想法是使用二阶矩方法，类似于它如何应用于HoC设置场景中的常规树。与Roberts和Zhao论文中只关注对角线上方的路径不同，该分析现在将包括两条对角线之间的路径。这是因为在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.