Questions and Methods in Probabilistic Combinatorics

概率方法是用概率论来证明组合数学中看似非概率的事实的一种强有力的技术。与概率方法一起，另一个迅速发展的研究领域是对随机结构的研究，最著名的是随机图。这两个研究方向统称为概率组合学。这个项目旨在通过研究该领域的具体问题来开发概率组合数学中的新思想和新技术。除了概率和组合学的基本进展外，概率组合学之前的工作还导致了对计算机科学产生巨大影响的工具的开发，这些工具被用于设计和研究随机算法，并了解随机输入和噪声环境下的性能。研究人员计划专注于几个主题。一个主题与Ramsey图有关，Ramsey图是一类重要的图，对于Ramsey定理来说，它是“近似极值的”。研究者计划在Ramsey图中关于边统计的一些先前工作的基础上，自然地导致对所谓的二次Littlewood-Offord问题的研究。另一个主题是“关于随机集的极值定理”。例如，给定一个随机超图的典型结果，生成子图上的什么条件可以确保它有一个完美匹配？为了解决这类问题，研究人员计划应用一些新的见解，非建设性地应用所谓的吸收方法。这一奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

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.