Global Structures in Graphs and Directed Graphs

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

Many natural problems are believed to be impossible for a computer to reliably solve in a reasonable amount of time. These types of problems are studied intensely in an effort to improve our understanding of the nature of algorithms. This project's goals lie in the mathematical field of extremal combinatorics which has many ties to questions of this type. In addition to its strong connection to computer science, over the last several decades, extremal combinatorics has become an increasingly influential branch of mathematics, with results touching number theory, analysis, and geometry. Whenever possible, work related to this project will be done with graduate students to support their professional development.This project's main focus is on optimizing local conditions that force a specific global structure in graphs, directed graphs, and other related combinatorial objects. It is often NP-hard to determine if such global structures exist in arbitrary graphs. This work will make extensive use of probabilistic methods, including the probabilistic absorbing technique of Rödl, Ruciński, and Szemerédi, and the regularity method, which was invented by Abel prize winner Endre Szemerédi, and has dramatically impacted numerous branches of mathematics in fundamental ways that continue to be explored, even now, more than forty years after its initial development. These techniques have allowed researchers to tackle formerly inaccessible conjectures and have facilitated the creation of many surprisingly general results. One of the goals of this project is to participate in the further development of these powerful methods.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.