Probabilistic and Extremal Combinatorics

Carnegie Mellon University, Pittsburgh PA

Investigators

Abstract

This research project is an investigation of discrete mathematical objects like networks and codes. Extremal combinatorics is focused on developing a better understanding of discrete mathematical objects that optimize interesting or desirable properties, while probabilistic combinatorics studies discrete mathematical objects that are generated by a series of random choices. These two research directions are intimately related as randomized algorithms are a remarkably powerful tool for the construction of interesting discrete mathematical objects. Furthermore, randomness is a major theme of the work on extremal problems for discrete structures as a deep understanding of the ways in which deterministic objects mimic their randomized counterparts often leads to major progress. This research has the potential to benefit society through the development of new algorithms for computational problems on large networks, new methods for analyzing existing network algorithms, and new codes and communication protocols. The project also provides training opportunities at both the undergraduate and graduate level. This research is in the broad areas of probabilistic and extremal combinatorics. The work in probabilistic combinatorics is focused on very sharp concentration of global parameters of the binomial random graph and problems regarding the decomposition of the edge set of the uniform random graph into cliques or bicliques. The work on sharp concentration in the binomial random graph is motivated by a recent result of the investigator and a doctoral student that establishes 2-point concentration of the independence number of the binomial random graph over a broad range of the probability parameter. The comprehensive understanding of the extent of concentration of the independence number of the binomial random graph is one of the goals of this part of the research program. This project also includes further study of the fascinating lonely runner conjecture and some problems on Ramsey numbers for hypergraphs and posets. While the structures that we consider in these two contexts are not necessarily random, we expect the interplay of structure and randomness (i.e. pseudorandom properties of discrete structures) to play a major role. The ultimate goal of this research is to find new methods that are broadly applicable in discrete mathematics. 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.