Accessibility percolation

无障碍渗透

• 批准号: 2751521
• 金额: --
• 依托单位: University of Bath
• 依托单位国家: 英国
• 项目类别: Studentship
• 财政年份: 2022
• 资助国家: 英国
• 起止时间: 2022 至 无数据
• 项目状态: 未结题
• 来源: https://gtr.ukri.org/projects?ref=studentship-2751521
• 关键词: 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.

可及性渗透是由Nowak和Krug作为进化模型引入的。在这个模型中，一个图表示可能的基因型或表型，每个顶点分配一个适应度值。目标是识别适应度值增加的顶点路径，表明可行的进化路径。在“纸牌屋”模型中，适应度值是独立且相同分布的。在“粗糙的富士山”模型中，适应度值表现出某种形式的漂移，以及独立和相同分布的成分。主要目的是获得关于纸牌屋和粗糙富士山模型在各种设置下的渐近行为的理论见解，包括在树，超立方体，随机图，甚至整数格上。我们的首要任务是研究树，因为缺少循环减少了图中不同部分之间的依赖关系。在这种情况下，关于《纸牌屋》的模型我们已经知道了很多，所以我们将集中讨论粗糙的富士山模型。我们可以使用与伯努利渗透的耦合，伯努利渗透是由Hegarty和Martinsson在超立方体上引入的，但同样适用于树，以表明当漂移参数足够大时，RMF模型在规则树上存在可达性渗透。结果表明，当渗流参数较小时，不存在可达性渗流；我们可以通过将路径分成固定数量的等长段，并使用段之间的负相关来实现这一点。接下来，我们的目标是证明，当渗透的概率从0到严格正的某个值时，漂移参数的临界值是1/n阶，其中n是树的每个顶点的子节点数。一个实际的组合论证，我们通过0、1、2或更多i.i.d随机变量无序但仍然接近的概率来约束标签有序的概率，看起来很有希望。一旦我们为树建立了这个结果，我们的目标是将其推广到超立方体，这是一个更复杂的图，但在某种程度上可以看作是一对不规则的树粘在一起。erdos - r<s:1>尼图的思想是使用第二矩方法，类似于在HoC设置场景中应用于常规树的方法。与Roberts和Zhao的论文中只关注对角线以上的路径不同，现在的分析将包括两条对角线之间的路径。这是因为在erdos - r<s:1>尼图中，路径可以重复地连接和分裂，从而增加了复杂性。为了解决这个问题，我们的方法是考虑两条对角线内的路径，通过这样做，我们不仅消除了k叉类型的路径，而且我们还考虑了路径最初是分开的，然后在第k代连接的情况。也有可能路径可以多次重复连接和分裂，但我们预计这种类型的增加路径是罕见的。