Sparse Discrete Structures

组合结构的极值和概率理论影响了数学的几个领域，包括数论、组合学和逻辑，以及其他领域，如信息论、编码论和理论计算机科学。近年来，随机结构和随机化算法的研究变得尤为重要，因为它们已被证明是处理许多已经出现并正在积极研究的大型现实世界网络的有用工具。开发研究这些复杂系统的新技术是一项可能会持续多年的主要任务，稀疏组合结构理论可能会为理解它们的大规模行为提供理论基础。该理论中的各种新方法将在本项目中得到应用。一个方向是在稀疏环境中证明经典定理的类似性。另一个方向是将这些方法应用于各种枚举问题。在更高的层面上，大多数将被调查的问题都试图理解大系统的局部和全局行为之间的数量关系。此外，这些方法在渗流中也有很好的适用性，渗流与统计物理有关。这些工作的大部分将与研究生一起完成，一些工作可能被整合到课程中，以帮助学生进入这一令人兴奋的研究领域。在过去的20年里，组合学中最重要的趋势之一是引入和证明极值图论、拉姆齐理论和加性组合学中著名定理的各种随机类似。最近，PI帮助发展的强大的一般迁移定理被用来解决这些问题。尽管这些工具已经被证明在解决几个中心猜想方面很有用，但它们的许多潜在应用还没有得到充分的探索。例如，这些方法似乎适用于许多枚举问题。研究人员将解决几个这类问题，他们还预计这个项目将带来新的令人兴奋的问题和方向。特别是，研究人员将研究以下相关领域：(I)稀疏结构中的极值问题；(Ii)稀疏随机图和伪随机图的子图中的嵌入；(Iii)Ramsey-Turan问题；(Iv)标志代数的应用；以及(V)Bootstrap渗流问题。

The extremal and probabilistic theory of combinatorial structures impacts several areas of mathematics, including number theory, combinatorics, and logic, as well as other fields such as information theory, coding theory, and theoretical computer science. The study of random structures and randomized algorithms has gained particular importance in recent years since they have proved to be useful tools in dealing with the many large real world networks that have emerged and are being actively investigated. Developing new techniques to study these complex systems is a major task that will likely continue for many years, and the theory of sparse combinatorial structures may form a theoretical foundation for understanding their large scale behavior. Various new methods in this theory will be applied in this project. One direction is to prove analogues of classical theorems in the sparse environment. Another direction is to apply the methods to various enumeration problems. At a high level, most of the problems that will be investigated seek to understand the quantitative relationship between the local and global behavior of a large system. Additionally, the methods are well-applicable in percolation, which is connected to statistical physics. Much of this work will be done with graduate students, and some of the work may be integrated into courses to help bring students into this exciting area of research.One of the most important trends in combinatorics over the past twenty years has been the introduction and proof of various random analogues of well-known theorems in extremal graph theory, Ramsey theory, and additive combinatorics. Recently, powerful general transference theorems, which the PI has helped to develop, have been used to attack such questions. Even though these tools have proved useful in resolving several central conjectures, many of their potential applications have not been fully explored. For example, these methods seem to be applicable to many enumeration problems. The investigators will address several problems of this type, and they also expect that this project will lead to new exciting questions and directions. In particular, the investigators will investigate the following related areas: (i) Extremal questions in sparse structures; (ii) Embedding in subgraphs of sparse random and pseudo-random graphs; (iii) Ramsey-Turan questions; (iv) Applications of flag algebras; and (v) Problems in bootstrap percolation.