FRG : Collaborative Research : Pseudorandomness in Ramsey Theory

拉姆齐理论（Ramsey theory）是指数学中大量深奥的结果，它们都有一个共同的主题：在大型组合结构中找到一致的子结构。它现在是现代组合学中最核心的领域之一。这门学科是弗兰克·拉姆齐在1930年研究逻辑系统的可决性时创立的，他的基本结果现在被称为拉姆齐定理。1935年，保罗·埃尔多斯（Paul Erdos）和乔治·塞克斯（George Szekeres）在研究一个看似无关的几何问题时，重新发现了他的定理。考虑到这些不同的起源，拉姆齐定理在数学的其他领域有广泛的应用就不足为奇了，包括逻辑、几何、数论和理论计算机科学。本研究小组的目标是获得经典拉姆齐数的新边界。该小组将在该领域使用广泛的工具和技术，包括概率方法、递进引理和伪随机图理论。最近，Mubayi和Verstraete在Alon和Rodl的工作基础上建立了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.