Extremal Combinatorics and Applications

极值组合数学是离散数学的一个重要领域。极值组合学中的数学方法现在是组合学中的核心工具，并在其他数学领域以及其他科学领域产生了许多应用，如统计力学、生物学、理论计算机科学和信息与编码理论。中心定理的证明还涉及算法复杂性问题，以及随机化算法和去随机化问题。例如，给定一个网络，一个人可能会询问其故障会导致网络断开的节点的最少数量，以及一个人可以以多高的效率展示这样一组节点--这是图论的中心主题之一。这些问题通常是数字和通信安全、网络搜索、可靠的数据传输、网络动力学和传染病或信息传播等的核心问题。该奖项支持组合学的研究，重点放在极端和概率组合学非常活跃的领域。其目的是研究极值组合学中的特定中心问题，如图和超图的Turan和Ramsey问题，匹配和着色问题，以及这些问题在随机图和超图模型中的推广。近年来，可用于研究这些问题的新工具的数量急剧增加，其中包括图和超图中的伪随机性的各种概念，鞅集中不等式和概率筛选方法，以及正则性引理等。PI建议研究的问题，如二部图的极值问题，仍然是开放的，任何新的进展都可能产生实质性的理论影响和实践后果。虽然这些开放的问题是重要的，显然是困难的，但上面提到的新方法和组合技术以及新的想法对于解决这些问题看起来非常有希望。

Extremal combinatorics is an important area of discrete mathematics. The mathematical methods in extremal combinatorics are now central tools in combinatorics, and give rise to many applications in other areas of mathematics as well as other fields of science, such as statistical mechanics, biology, theoretical computer science and information and coding theory. The proofs of the central theorems are also connected to algorithmic complexity questions, as well as questions on randomized algorithms and derandomization. For instance, given a network one may ask for the minimum number of nodes whose failure would cause the network to disconnect, and how efficiently one can exhibit such a set of nodes -- this is one of the central topics in graph theory. These questions often lie at the heart of digital and communication security, web searching, reliable data transmission, network dynamics, and the spread of infectious disease or information, and so on.This award supports research in combinatorics, focusing on the very active area of extremal and probabilistic combinatorics. The aim is to study specific central problems in extremal combinatorics, such as the Turan and Ramsey problems for both graphs and hypergraphs, matching and coloring problems and the extension of these problems into the context of models of random graphs and hypergraphs. In recent years, there has been a sharp increase in the number of new tools available for studying these problems, including the various notions of pseudorandomness in graphs and hypergraphs, martingale concentration inequalities and probabilistic sieving methods, as well as regularity lemmas, to mention a few. The problems which the PI propose to study, such as the extremal problem for bipartite graphs, remain open, and any new advance is likely to have a substantial theoretical impact and practical consequences. While these open problems are important and clearly difficult, the new methods and combinatorial techniques mentioned above together with new ideas look very promising for the resolution of these problems.