Sparse Discrete Structures

稀疏离散结构

• 批准号: 1500121
• 负责人: Jozsef Balog
• 金额: $ 30万
• 依托单位: University of Illinois at Urbana-Champaign
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-06-15 至 2019-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1500121&HistoricalAwards=false
• 关键词: Sparse; Discrete; Structures

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.

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