CAREER: Extremal Combinatorics: Methods, Problems, and Challenges

职业：极值组合学：方法、问题和挑战

• 批准号: 1352121
• 负责人: Jacob Fox
• 金额: $ 40万
• 依托单位: Massachusetts Institute of Technology
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2014
• 资助国家: 美国
• 起止时间: 2014-04-01 至 2015-10-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1352121&HistoricalAwards=false
• 关键词: CAREER; Extremal; Combinatorics; Methods; Problems

This research project considers a variety of problems related to Szemerédi's regularity method and Ramsey theory. In tackling these problems, the PI will use a range of combinatorial methods that have recently led to substantial progress on related problems. Examples include probabilistic methods, density increment arguments, transference arguments, analytic tools, and embedding techniques. The first area in this project concerns Szemerédi's regularity method. Within this area, one of the main goals of the project is to obtain new bounds on the triangle removal lemma and its various extensions and variants. The triangle removal lemma states that any graph with a subcubic number of triangles can be made triangle-free by removing a subquadratic number of edges. Another major goal of the project is to further push the regularity method to sparse graphs and other combinatorial structures, and to obtain new applications. Specific problems include optimizing the pseudorandomness conditions needed to obtain sparse counting lemmas, proving analogous sparse regularity results in other combinatorial structures such as cubes, and providing new applications in number theory and discrete geometry such as extensions of the Green-Tao theorem on long arithmetic progressions in the primes. The second area in this project is estimating Ramsey numbers. The PI will work on proving new bounds for classical (complete) graph and hypergraph Ramsey numbers, and to prove linear bounds for Ramsey numbers of sparse graphs.This project studies fundamental problems in combinatorics related to the structure of large networks. Examples of large networks include the Internet, Facebook, the brain, imperfect crystals, and designed chips. The structure of these networks can be critical in understanding how the networks function. Previous work has shown that the subjects under study in this project have a wide range of applications. Furthermore, this work has led to the development of powerful methods that have been used in many branches of mathematics and computer science. For example, previous progress on estimating Ramsey numbers led to the development of probabilistic techniques that have had a tremendous influence on computer science, such as in the design of randomized algorithms. It is expected that further work on these problems will lead to new methods and applications.

本研究项目考虑了与Szemerédi正则性方法和Ramsey理论相关的各种问题。在解决这些问题时，PI将使用一系列组合方法，这些方法最近在相关问题上取得了实质性进展。例子包括概率方法、密度增量论证、迁移论证、分析工具和嵌入技术。这个项目的第一个领域是关于Szemerédi的正则性方法。在这一领域内，该项目的主要目标之一是在三角形去掉引理及其各种扩展和变体上获得新的界。三角形移除引理指出，任何具有次三次数个三角形的图都可以通过移去次二次数的边来使其不含三角形。该项目的另一个主要目标是进一步将正则性方法推广到稀疏图和其他组合结构，并获得新的应用。具体问题包括优化获得稀疏计数引理所需的伪随机性条件，在其他组合结构(如立方体)中证明类似的稀疏正则性结果，以及在数论和离散几何中提供新的应用，例如在素数中关于长算术级数的Green-Tao定理的推广。这个项目的第二个领域是估计拉姆齐数。PI将致力于证明经典(完全)图和超图Ramsey数的新的界，并证明稀疏图的Ramsey数的线性界。本项目研究与大型网络结构相关的组合学的基本问题。大型网络的例子包括互联网、Facebook、大脑、不完美的水晶和设计的芯片。这些网络的结构对于了解网络的运行方式至关重要。前人的工作表明，本课题所研究的课题具有广泛的应用前景。此外，这项工作还导致了强大的方法的发展，这些方法已经在数学和计算机科学的许多分支中使用。例如，以前在估计Ramsey数方面的进展导致了概率技术的发展，这些技术对计算机科学产生了巨大的影响，例如在随机算法的设计方面。预计在这些问题上的进一步工作将导致新的方法和应用。