Extremal Graph Theory and Bootstrap Percolation

极值图论和 Bootstrap 渗滤

• 批准号: 0603769
• 负责人: Jozsef Balog
• 金额: --
• 依托单位: University of Illinois at Urbana-Champaign
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2005
• 资助国家: 美国
• 起止时间: 2005-08-15 至 2007-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0603769&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.

BALOG DMS-0302804奖励摘要拟议的研究领域是极端图理论和引导程序渗透。它们彼此之间并不遥远，因为第一个概率工具都使用了许多概率工具，并且在第二个工具中使用了许多组合想法。对计算机科学的需求以及从离散模型扮演越来越重要的角色，提高极端图理论的重要性并提出算法的观点的应用程序中的需求。大约四十年来，渗透理论一直是概率理论，组合学和物理学界面的积极研究领域。对标准渗滤的各个方面的兴趣仍然很高，包括估计关键概率。最近，已经研究了越来越多的标准渗滤模型的变体，尤其是被称为自举渗透的过程家族。最近的应用来自不同的方面，例如时空动力学系统。 物理学家进行的计算机实验提出了有趣的非平凡的大规模行为，并且已经证明了许多模型的许多深度数学结果。提议者的目的是在关键概率上研究渗透过程。建议者的工作是将Turan定理扩展到多个方向。一个方向是描述不包含某些感应子图的图形家族。另一个是研究Turan关于超图的问题，尤其是在三重系统上，并开发诸如规律性和稳定性定理等通用工具。Bootstrappercolation是随机蜂窝自动机的家族的成员，是图形上的一个过程，每个站点都在某些概率上开放或封闭，并且这些概率随着时间的范围而随着时间的流逝而变化。估计关键概率和关键概率周围窗口的大小。该计划是证明过渡是敏锐的，并调查了不同的模型，这些模型的理解将有助于应用程序。