Methods in Extremal Combinatorics

极值组合学方法

• 批准号: 1855635
• 负责人: Jacob Fox
• 金额: $ 30万
• 依托单位: Stanford University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2019
• 资助国家: 美国
• 起止时间: 2019-07-01 至 2022-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1855635&HistoricalAwards=false
• 关键词: Methods; Extremal; Combinatorics

The PI will study fundamental problems in combinatorics. Previous work on these problems has led to a wide range of applications and the development of powerful methods which have been used in many branches of mathematics and computer science. For example, probabilistic methods were developed to estimate Ramsey numbers and have had a tremendous influence on theoretical computer science, such as in the design of randomized algorithms. As another example, the regularity method led to the celebrated Green-Tao theorem on arithmetic progressions in primes. It is expected that further work on these problems will lead to new methods and applications.The PI will focus on using and further developing methods to solve problems in extremal combinatorics. Examples of these techniques are the regularity method, the polynomial method, dependent random choice, and embedding techniques. The first area of focus in this project concerns Szemeredi's regularity method. Within this area, one of the main goals of this project is to obtain new bounds on the triangle removal lemma and its variants. The second area of focus in this project is estimating Ramsey numbers.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

PI将研究组合学中的基本问题。以前的工作对这些问题已经导致了广泛的应用和强大的方法，已被用于数学和计算机科学的许多分支的发展。例如，概率方法被用来估计拉姆齐数，并对理论计算机科学产生了巨大的影响，例如在随机算法的设计中。另一个例子是，正则性方法导致了著名的关于素数算术级数的格林-陶定理。预计对这些问题的进一步研究将导致新的方法和应用。PI将专注于使用和进一步开发方法来解决极值组合学中的问题。这些技术的例子是正则性方法，多项式方法，相关随机选择和嵌入技术。本项目的第一个重点领域涉及Szemeredi的正则性方法。在这一领域，该项目的主要目标之一是获得新的边界上的三角形删除引理及其变种。该项目的第二个重点领域是估算拉姆齐数。该奖项反映了NSF的法定使命，并被认为值得通过使用基金会的知识价值和更广泛的影响审查标准进行评估来支持。

项目成果

Towards the linear arboricity conjecture

走向线性树木性猜想

• DOI: 10.1016/j.jctb.2019.08.009
• 发表时间: 2020
• 期刊: Series B
• 作者: Ferber, Asaf;Fox, Jacob;Jain, Vishesh
• 通讯作者: Jain, Vishesh

Approximating the rectilinear crossing number

近似直线交叉数

• DOI: 10.1016/j.comgeo.2019.04.003
• 发表时间: 2019
• 期刊: Computational Geometry
• 作者: Fox, Jacob;Pach, János;Suk, Andrew
• 通讯作者: Suk, Andrew

The Schur-Erdős problem for semi-algebraic colorings

半代数着色的 Schur-ErdÅs 问题

• DOI: 10.1007/s11856-020-2042-8
• 发表时间: 2020
• 期刊: Israel Journal of Mathematics
• 影响因子: 1
• 作者: Fox, Jacob;Pach, János;Suk, Andrew
• 通讯作者: Suk, Andrew

Triforce and corners

三角力和角点

• DOI: 10.1017/s0305004119000173
• 发表时间: 2020
• 期刊: Mathematical Proceedings of the Cambridge Philosophical Society
• 影响因子: 0.8
• 作者: FOX, JACOB;SAH, ASHWIN;SAWHNEY, MEHTAAB;STONER, DAVID;ZHAO, YUFEI
• 通讯作者: ZHAO, YUFEI

Anti-concentration for subgraph counts in random graphs

• DOI: 10.1214/20-aop1490
• 发表时间: 2019-05
• 期刊: The Annals of Probability
• 作者: J. Fox;Matthew Kwan;Lisa Sauermann