FRG : Collaborative Research : Pseudorandomness in Ramsey Theory

FRG：协作研究：拉姆齐理论中的伪随机性

• 批准号: 1952786
• 负责人: Jacques Verstraete
• 金额: $ 62.16万
• 依托单位: University of California-San Diego
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2020
• 资助国家: 美国
• 起止时间: 2020-07-01 至 2024-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1952786&HistoricalAwards=false
• 关键词: FRG; Collaborative; Research; Pseudorandomness; Ramsey; FRG; Collaborative; Research; Pseudorandomness; Ramsey

Ramsey theory refers to a large body of deep results in mathematics which have a common theme: find uniform substructures in large combinatorial structures. It is now one of the most central areas in modern combinatorics. The subject was founded by Frank Ramsey in 1930 while studying the decidability of logical systems and his foundational result is now known as Ramsey’s theorem. His theorem was rediscovered in 1935 by Paul Erdos and George Szekeres while studying a seemingly unrelated geometric question. Given these diverse origins, it is not surprising that Ramsey’s theorem has had a wide range of applications in other areas of mathematics including logic, geometry, number theory, and theoretical computer science.The goal of this focused research group is to obtain new bounds for classical Ramsey numbers. The group will use a wide range of tools and techniques in the area including the probabilistic method, the stepping-up lemma, and the theory of pseudorandom graphs. Very recently, Mubayi and Verstraete established a surprising connection between the Ramsey numbers and pseudorandom graphs based on the work of Alon and Rodl, thus moving the emphasis of the field from random graphs to pseudorandom graphs. Moreover, substantial progress has recently been made on hypergraph Ramsey numbers, where we now know the tower growth rate for many of these numbers. It is expected that further work on these problems will lead to new methods and applications as well. Finally, a substantial number of students and early-career researchers will be trained and supported, and the collaborative results arising from the research will be disseminated widely at conferences, workshops and via publications.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.

拉姆西理论是指具有共同主题的数学深度结果：在大型组合结构中找到统一的子结构。现在，它是现代组合学中最中心的地区之一。该主题是由弗兰克·拉姆齐（Frank Ramsey）于1930年研究的，同时研究了逻辑系统的可决定性，而他的基本结果现在被称为拉姆齐（Ramsey）的定理。在研究一个看似无关的几何问题时，保罗·埃多斯（Paul Erdos）和乔治·塞克雷斯（George Szekeres）于1935年重新发现了他的定理。鉴于这些潜水员的起源，Ramsey的定理在其他数学领域都有广泛的应用并不奇怪，包括逻辑，几何，数字，数量理论和理论计算机科学。这个重点研究小组的目标是为经典的Ramsey数字获得新的界限。该小组将在该区域中使用各种工具和技术，包括概率方法，加速引理和伪图理论。最近，Mubayi和Verstraete基于Alon和Rodl的工作建立了Ramsey数字和伪数图之间的惊喜联系，从而将田地的重点从随机图移到了伪随机图。此外，最近在Hypergraph Ramsey数字上取得了巨大进展，我们现在知道许多此类数字的塔楼增长率。预计这些问题的进一步工作也将导致新的方法和应用。最后，将对许多学生和早期研究人员进行培训和支持，而研究所带来的协作结果将在会议，研讨会和通过出版物中广泛传播。该奖项反映了NSF的法定任务，并通过评估该基金会的知识分子功能和广泛的影响来评估NSF的法定任务，并被认为是诚实的支持。