Factors in Graphs and Related Combinatorial Structures

University Of South Florida, Tampa FL

Investigators

Abstract

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.