Factors in Graphs and Related Combinatorial Structures

在过去的几十年里，极值组合学已经成为一个越来越有影响力的数学分支，其结果涉及数论，分析和几何。这个项目属于极值图论，福尔斯，并在狄拉克，Hajnal和Szemeredi的经典结果的根源。此外，这项工作与计算机科学有着重要的交叉，因为许多有趣的算法问题将被探索。只要有可能，这项工作将与研究生一起完成，并可能在他们的专业发展中发挥重要作用。该项目的主要重点是优化局部条件，迫使图，有向图和其他相关组合对象中的特定全局结构。这项研究将广泛使用概率方法，包括Rodl，Rucinski和Szemeredi的概率吸收技术，以及由Abel奖赢家Endre Szemeredi发明的正则性方法，并以基本的方式对数学的许多分支产生了巨大的影响，这些方法在最初发展40多年后仍在继续探索。这些技术使研究人员能够处理以前无法处理的问题，并促进了许多令人惊讶的一般性结果的产生。该项目的目标之一是参与这些强大方法的进一步发展。该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Over the last several decades, extremal combinatorics has become an increasingly influential branch of mathematics, with results touching number theory, analysis, and geometry. This project falls under extremal graph theory, and has roots in classical results of Dirac, Hajnal, and Szemeredi. In addition, this work has a significant intersection with computer science, because many interesting algorithmic questions will be explored. Whenever possible, this work will be done with graduate students, and may play an important role in 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. The research will make extensive use of probabilistic methods, including the probabilistic absorbing technique of Rodl, Rucinski, and Szemeredi, and the regularity method, which was invented by Abel prize winner Endre Szemeredi, 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.