Extremal combinatorics studies how large or how small a collection of combinatorial objects satisfying certain restrictions can be. This branch of mathematics has witnessed spectacular development in the last few decades, and grown into a rich field with a wide variety of its own approaches and methodology. The main focus of this award is to develop new algebraic methods to solve extremal combinatorial problems, and further our understanding of the independence number and induced substructures of graphs and hypergraphs. This project involves and aims to establish connections across numerous areas, including algebra, combinatorics, probability, and discrete geometry. An integral part of this project is its educational component, which includes organizing junior research workshops and summer REU programs. The long-term education goal of this award is to actively engage undergraduate students in STEM research, provide opportunities for early-career researchers to publicize their works, and enhance the research collaboration between the Mathematics and Computer Science communities.
The PI will study several fundamental mathematical questions, including: (i) For which results in extremal combinatorics one can expect a degree strenthening? (ii) To what extent the spectrum of the (pseudo-)adjacency matrix of a graph or hypergraph describes the independence number or induced substructures of a graph? (iii) Is there a quantitative version of Cauchy's Interlace Theorem? Techniques developed from these projects will open the possibility of attacking some of the most important and challenging open problems in combinatorics: Chvatal's Conjecture on intersecting subfamilies, Tomaszewski's Conjecture on signed sums, and the Erdos hypergraph matching conjecture.
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.
