Sparse Discrete Structures

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

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.