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.

该专业将研究组合学中的基本问题。以前在这些问题上的工作已经导致了广泛的应用和强大的方法的发展，这些方法已经被用于数学和计算机科学的许多分支。例如，概率方法被开发来估计Ramsey数，并对理论计算机科学产生了巨大的影响，例如在随机算法的设计中。作为另一个例子，正则性方法导致了著名的关于素数算术级数的格林-陶定理。期望在这些问题上的进一步工作将带来新的方法和应用。PI将专注于使用和进一步发展方法来解决极值组合数学中的问题。这些技术的例子有正则性方法、多项式方法、相依随机选择和嵌入技术。这个项目的第一个焦点领域是关于Szmeredi的正则性方法。在这一领域内，这个项目的主要目标之一是获得关于三角形去掉引理及其变体的新的界。该项目的第二个重点领域是估计拉姆齐数字。这一奖项反映了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