Extremal Combinatorics and Applications

极值组合学及其应用

• 批准号: 1362650
• 负责人: Jacques Verstraete
• 金额: $ 30万
• 依托单位: University of California-San Diego
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2014
• 资助国家: 美国
• 起止时间: 2014-06-01 至 2019-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1362650&HistoricalAwards=false
• 关键词: Extremal; Combinatorics; Applications

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.

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