Random graphs and percolation processes

随机图和渗透过程

• 批准号: RGPIN-2016-05949
• 负责人: Gunderson, Karen
• 金额: $ 1.46万
• 依托单位: University of Manitoba
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2019
• 资助国家: 加拿大
• 起止时间: 2019-01-01 至 2020-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=677265
• 关键词: Random; graphs; percolation; processes

The topics of this research proposal are random graphs, probabilistic combinatorics, and extremal combinatorics with regard to diffusion or activation processes on graphs. The study of such diffusion processes on graphs is often motivated by real-world phenomena in complex networks or statistical physics including rumour or information-spreading and the dynamics of ferromagnetism. As processes on graphs, they provide theoretical problems of interest in their own right. In these cellular automata, vertices of a graph are in one of two states, 'inactive' or 'active', and state updates occur by a local and homogeneous rule. Generally, these updates are repeated and the initial set of active vertices is said to percolate if all vertices are eventually active. For infinite graphs and for large finite graphs, the central question is the behaviour of a typical initially activated set of a particular density and whether there is a critical threshold for the density of a randomly chosen initially activated set to percolate. ***Much is known about the critical thresholds for percolation in processes where once activated, a vertex remains so forever. In particular, such critical probabilities for grid graphs, infinite trees, some Cayley graphs, and many models of random graphs and geometric graphs have been studied extensively. Most such results rely heavily on the monotone nature of the processes and on the properties of the underlying graph. I propose to investigate a more general class of problems where either the process is not constrained by monotonicity or those where the graph contains both highly structured and also random parts. Of particular interest are those non-monotone models with update rules for which the configurations witnessing the 'deactivation' of a vertex are fewer in number than those witnessing an activation. In some such cases, the effects of deactivation are local and the aim shall be to show that the model behaves, with high probability, in an 'essentially monotone' fashion. To shed light on the relationship between the structure of these graphs and the growth of the activation processes, I intend to address how small perturbations in the underlying graph change a diffusion process and its critical probability.***The planned outcome of this research is the development of tools and of a cohesive theory to study these processes in the greatest generality that can encompass those local update rules in which some vertices can be deactivated and can account for random changes to the underlying graph. In the past, rigorous threshold results for these types of graph processes have been found to differ hugely from those predicted by experiments, indicating a need to have precise results to guarantee a solid understanding of the large-scale behaviour of these activation processes.**

这项研究的主题是关于图上扩散或激活过程的随机图、概率组合学和极值组合学。对图上这种扩散过程的研究往往受到复杂网络或统计物理中的真实世界现象的推动，包括谣言或信息传播以及铁磁性的动力学。作为图上的过程，它们本身就提供了感兴趣的理论问题。在这些元胞自动机中，图的顶点处于两种状态之一，不活动的或活动的，状态更新按照局部的同构规则进行。通常，这些更新是重复的，如果所有顶点最终都处于活动状态，则初始活动顶点集被认为是渗流的。对于无限图和大型有限图，中心问题是特定密度的典型初始激活集的行为，以及随机选择的初始激活集的密度是否存在渗流的临界阈值。*对过程中渗流的临界阈值有很多了解，在这些过程中，一旦激活，顶点将永远保持这样的状态。特别是对格图、无限树、某些Cayley图以及许多随机图和几何图模型的临界概率进行了广泛的研究。大多数这样的结果在很大程度上依赖于过程的单调性质和基础图的性质。我建议研究一类更一般的问题，其中要么过程不受单调性约束，要么图既包含高度结构化的部分又包含随机部分。特别令人感兴趣的是那些具有更新规则的非单调模型，对于这些模型，见证顶点“停用”的配置在数量上少于见证激活的配置。在某些这样的情况下，停用的影响是局部的，其目的应该是显示模型以一种“基本上单调”的方式以高概率的方式运行。为了阐明这些图的结构和激活过程的增长之间的关系，我打算解决底层图中的微小扰动如何改变扩散过程及其临界概率。*这项研究的计划结果是开发工具和内聚理论来最大限度地研究这些过程，该工具可以包括局部更新规则，其中一些顶点可以被停用，并且可以解释底层图的随机变化。在过去，这些类型的图形过程的严格阈值结果被发现与实验预测的结果有很大的不同，这表明需要有准确的结果来保证对这些激活过程的大规模行为的可靠理解。