Extremal Graph Theory and Bootstrap Percolation

极值图论和 Bootstrap 渗滤

• 批准号: 0302804
• 负责人: Jozsef Balog
• 金额: $ 7.85万
• 依托单位: Ohio State University Research Foundation -DO NOT USE
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2003
• 资助国家: 美国
• 起止时间: 2003-06-01 至 2006-01-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0302804&HistoricalAwards=false
• 关键词: Extremal; Graph; Theory; Bootstrap; Percolation

Abstract for award of Balog DMS-0302804The proposed research areas are extremal graph theory and bootstrap percolation. They are not far from each other, as many probabilistic tools are used in the first one, and many combinatorial ideas are needed in the second one. The need of computer science and demands from applications where discrete models play more and more important roles, increase the importance of extremal graph theory and suggests an algorithmic point of view. For about forty years now, percolation theory has been an active area of research at the interface of probability theory, combinatorics and physics. Interest in various aspects of standard percolation remains high, including estimates of critical probabilities. Lately more and more variants of the standard percolation models have been studied, in particular, the family of processes known as bootstrap percolation. Recent applications arise from different aspects, for example from spatio-temporal dynamical systems. Computer experiments performed by physicists have suggested interesting non-trivial large-scale behavior, and many deep mathematical results have been proved about a number of models.The proposer is aiming to study the percolation process at the critical probability.The work of the proposer is an extension of Turan's Theorem into several directions. One direction is to describe graph families which do not contain certain induced subgraphs. The other is to study Turan type of questions on hypergraphs, in particular on triple systems, and to develop general tools like regularity and stability theorems.Bootstrap percolation, a member of the family of random cellular automata, is a process on graphs, where each site is open or closed with a certain probability, and these states are changing with time.Studying bootstrap percolation, the main aim of the proposer is to describe the phase transition, estimate the critical probability, and the size of the window around the critical probability. The plan is to prove that the transitions are sharp, and to investigate different models, whose understanding would be helpful in the applications.

巴洛格DMS-0302804奖摘要建议的研究领域是极值图论和Bootstrap渗流。第一种方法使用了许多概率工具，第二种方法需要许多组合思想，所以它们之间并不遥远。计算机科学的需要和离散模型发挥着越来越重要作用的应用的需求，增加了极值图论的重要性，并提出了算法的观点。近四十年来，渗流理论一直是概率论、组合学和物理学交界的一个活跃研究领域。人们对标准渗流的各个方面仍然很感兴趣，包括对临界概率的估计。最近，越来越多的标准渗流模型的变体被研究，特别是被称为Bootstrap渗流的过程家族。最近的应用来自不同的方面，例如时空动力系统。由物理学家进行的计算机实验表明了一些有趣的非平凡的大尺度行为，许多深刻的数学结果已经在一些模型上得到了证明。一个方向是描述不包含某些导出子图的图族。二是研究超图上的Turan型问题，特别是三元系上的Turan型问题，并发展正则性和稳定性定理等通用工具。Bootstrap渗流是随机细胞自动机家族的成员之一，它是图上的一个过程，其中每个站点以一定的概率打开或关闭，这些状态随时间变化。研究Bootstrap渗流的主要目的是描述相变，估计临界概率，以及临界概率附近的窗口大小。我们的计划是证明转变是尖锐的，并研究不同的模型，这些模型的理解将有助于应用。