NSF-BSF: Extremal and Probablisitic Combinatorics

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

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.