FRG: Collaborative Research: Pseudorandomness in Ramsey Theory

点击翻译按钮获取中文摘要

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.