Extremal Problems Related to Cycles and Spanning Structures in Graphs and Hypergraphs

University Of South Carolina At Columbia, Columbia SC

Investigators

Abstract

The basic problem of extremal combinatorics asks how large a combinatorial structure can be while avoiding some forbidden property. This project studies extremal problems in graph theory and hypergraph theory, specifically those related to long paths and cycles. Of particular interest are Hamiltonian cycles--cycles that visit every vertex in a graph, and other related structures. These problems are fundamental in graph and hypergraph theory, and have applications to operations research, circuit design, optical network design, and more. Graduate students will also be advised as part of this project. Determining if a given graph has a Hamiltonian cycle is a well-known NP-complete problem. Proving sufficient conditions for the existence of such cycles is among the most well-studied topics in combinatorics. This project will explore classical extremal problems for Hamiltonian cycles and related topics such as pancyclicity, long cycles, and other spanning substructures. The PI will also study analogous problems for Berge cycles and other Berge structures in hypergraphs, utilizing tools from graph theory to prove new results in hypergraph theory. 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.