Problems in Extremal and Geometric Combinatorics

Carnegie Mellon University, Pittsburgh PA

Investigators

Abstract

The development of extremal and geometric combinatorics has been informed by questions in a number of areas of mathematics, computer science and other disciplines. The aim of the project is both to develop general combinatorial tools of wide applicability and to solve specific combinatorial problems. Graduate and undergraduate students will be trained during this project. The specific problems to be tackled include algebraic and geometric questions related to Turan problems and Ramsey theory. Particular attention will be devoted to algebraic constructions. The aim here is to understand the apparent rigidity of many known constructions in the area, and develop more general techniques. It is expected that this will result in forging the connections between finite geometry and extremal combinatorics closer, enriching both areas. The project also considers several topics related to words and subsequences, as well as discrepancy theory. The potential impact includes better error-correcting codes and numerical algorithms. 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.