This project focuses on topics in Extremal Combinatorics, which investigate the relationships between useful parameters of discrete systems, and characterizes their extreme values over various families of those systems. Such problems often have applications in Computer Science and other areas of Mathematics, but are also elegant and interesting in their own right. The goal of this project is to further develop the toolbox of available approaches for attacking Combinatorial problems. This goal will be achieved by studying certain families of problems which can be organized according to the methods used in their solutions. First, we examine applications of analytical (continuous) arguments to discrete problems. Second, we study extremal problems related to set systems. Finally, we explore the application of probabilistic methods to purely deterministic problems.

The field of combinatorics encompasses the rigorous mathematical study of discrete structures and processes, such as sets, networks, and even algorithms. In the past, combinatorial problems were often solved by pure ingenuity. Today, however, a variety of powerful methods have emerged, which draw elements from many other branches of the mathematical sciences. At the same time, the rapid development of Computer Science has substantially increased the demand for foundational results on discrete systems--these can provide the theoretical basis for future work. The overarching objective of this project is to use a problem-driven philosophy to inspire innovations in the development of new techniques in Combinatorics. Unifying the problems in this study is a theme of simple, elegant statements that inspire approaches which arise from across the mathematical spectrum. Consequently, these problems also serve well as a platform for bringing young people into research.

Agency
National Science Foundation (NSF)
Institute
Division of Mathematical Sciences (DMS)
Application #
1201380
Program Officer
Tomek Bartoszynski
Project Start
Project End
Budget Start
2012-07-01
Budget End
2015-06-30
Support Year
Fiscal Year
2012
Total Cost
$197,886
Indirect Cost
Name
Carnegie-Mellon University
Department
Type
DUNS #
City
Pittsburgh
State
PA
Country
United States
Zip Code
15213