NSF-BSF: Extremal and Probablisitic Combinatorics

在这个项目中，研究者和合作者研究了极值和概率组合学中的各种问题。极值组合学处理的是大型离散结构（如图、超图、置换或整数集）的各种性质之间的相互作用，而概率组合学处理的是这些性质之间的典型关系。在过去的几十年里，这两个领域在深度和广度上都有了巨大的发展。他们提供了许多惊人的结果，影响了数学的其他各个领域，如数论、群论、概率论、信息论和理论计算机科学。此外，为了解决极值组合学中的一些核心问题而开发的许多关键见解后来被导出到其他领域。这个项目的一个主要目标，除了回答正在研究的问题，是开发新的工具和技术，将适用于其他领域的离散数学。本项目为研究生提供研究训练机会。研究者和他的合作者打算研究的问题属于当前极值和概率组合学中最活跃的研究主题，它们之间有许多明确和隐含的类比和联系。第一组问题处理经典的极值问题，如二部图的图兰数和不包含某些固定线性方程解的前n个整数的子集的数目。第二组问题处理随机矩阵，并解决诸如“随机对称矩阵奇异的概率是多少？”和“典型矩阵的秩有多大弹性？”第三组问题处理反集中不等式，并解决诸如“当从超图中采样固定数量的顶点时，看到给定数量边的概率是多少？”最后一组问题处理排列，并解决随机排列的Stanley-Wilf极限和大偏差不等式的顺序。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

In this project the investigator and collaborators study a variety of questions in extremal and probabilistic combinatorics. While extremal combinatorics deals with the interplay between various properties of large discrete structures (e.g. graphs, hypergraphs, permutations, or sets of integers), probabilistic combinatorics deals with the typical relations between such properties. Both areas have grown tremendously in the past few decades both in depth and in breadth. They supplied many spectacular results that affected various other areas of mathematics, such as number theory, group theory, probability theory, information theory, and theoretical computer science. Furthermore, many key insights that were developed in order to solve some of the core questions in extremal combinatorics were later exported to other areas. A major goal of this project, besides answering the questions under study, is to develop new tools and techniques that will be applicable to other areas of discrete mathematics. The project provides research training opportunities for graduate students. The questions the investigator and his collaborators intend to study belong to some of the most actively studied topics in current extremal and probabilistic combinatorics, with many explicit and implicit analogies and connections between them. The first set of questions deals with classical extremal problems such as the Turan-number of bipartite graphs and the number of subsets of the first n integers not containing a solution to some fixed linear equations. The second set of problems deals with random matrices and addresses questions such as "what is the probability that a random symmetric matrix is singular?" and "how resilient is the rank of a typical matrix?" The third set of problems deals with anti-concentration inequalities and addresses questions such as "what is the probability of seeing a given number of edges when sampling a fixed number of vertices from a hypergraph?" The last set of problems deals with permutations and address the order of Stanley-Wilf limits and large deviation inequalities for random permutations.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.