Questions and Methods in Probabilistic Combinatorics

Stanford University, Stanford CA

Investigators

Abstract

The probabilistic method is a powerful technique for using probability theory to prove seemingly non-probabilistic facts in combinatorics. Together with the probabilistic method, a second line of study that has grown rapidly is the study of random structures, most famously random graphs. These two lines of research are collectively known as probabilistic combinatorics. This project aims to develop new ideas and techniques in probabilistic combinatorics by studying concrete questions in the field. In addition to fundamental advances in probability and combinatorics, previous work on probabilistic combinatorics has led to development of tools that have had enormous impacts in computer science, where they are used to design and study randomized algorithms and to understand performance on random inputs and in noisy environments. The investigator plans to focus on several topics. One topic concerns Ramsey graphs, which are an important class of graphs that are “approximately extremal” for Ramsey’s theorem. The investigator plans to build on some previous work regarding edge statistics in Ramsey graphs, which also naturally leads to the study of the so-called quadratic Littlewood-Offord problem. Another topic is the subject of extremal theorems “relative to a random set.” For example, given a typical outcome of a random hypergraph, what conditions on a spanning subgraph ensure that it has a perfect matching? To approach questions of this type, the investigator plans to apply some new insights for applying the so-called absorption method non-constructively. 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.