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

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

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