Global Structures in Graphs and Directed Graphs

许多自然问题被认为是计算机不可能在合理的时间内可靠地解决的。为了提高我们对算法本质的理解，我们对这类问题进行了深入的研究。这个项目的目标在于极值组合学的数学领域，它与这类问题有许多联系。除了与计算机科学的紧密联系外，在过去的几十年里，极值组合数学已经成为一个越来越有影响力的数学分支，其结果涉及到数论、分析和几何。只要有可能，与这个项目相关的工作将与研究生一起完成，以支持他们的专业发展。这个项目的主要重点是优化当地条件，迫使特定的全局结构在图、有向图和其他相关的组合对象中。要确定这种全局结构是否存在于任意图中通常是NP-困难的。这项工作将广泛使用概率方法，包括Rödl，Ruciński和Szemerédi的概率吸收技术，以及由阿贝尔奖获得者Endre Szemerédi发明的正则性方法，它对数学的许多分支产生了巨大的影响，在其最初发展40多年后，仍然在继续探索。这些技术使研究人员能够处理以前难以理解的猜想，并促进了许多令人惊讶的普遍结果的产生。该项目的目标之一是参与这些强大方法的进一步开发。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

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.