Extremal combinatorial structures and algorithms

极值组合结构和算法

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

This proposal concerns research in combinatorics, focussing on extremal structures and related algorithms. This area is currently very active, and the methods are central to many applications in other mathematical disciplines as well as other fields of science, such as statistical mechanics, theoretical computer science and information and coding theory. The proposer aims to study specific central problems in extremal combinatorics including the Turan problem, cycles in graphs, graph and hypergraph coloring problems, and thresholds in random graphs. Central to these problems are well-established mathematical techniques from various areas of mathematics as well as newly developed notions of pseudorandomness in graphs and hypergraphs, inequalities of concentration of measure, and martingales. For many of these topics, the proofs of the main theorems are also connected to algorithmic complexity questions, and questions about randomized algorithms and derandomization. Many of the problems proposed, such as the extremal problem for even cycles, have long been open; any new advance is likely to have a substantial theoretical impact and at least some practical consequences. While these open problems are important and clearly difficult, new methods and standard combinatorial techniques combined with some new ideas offer new hope for solving them. Extremal combinatorics is the study of mathematical structures which have constraints placed on the substructures they may contain. An extremal structure is one which satisfies those constraints, and is optimal with respect to some measure of density. For instance, one may ask for the smallest size of a code that can securely transmit a message while correcting a given number of bit errors. These extremal structures arise naturally in many areas of science. As another example, given a network one may ask for the minimum number of nodes whose failure would cause the network to disconnect. 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; as such, they have applications to theoretical computer science, information theory and statistical mechanics, to mention three areas. Further concrete examples include multiplication of large arrays of numbers for qualitative web searches -- these matrices tend to have billions of rows and columns; the RSA cryptosystem, which underpins much of modern digital security and is based strongly on the belief that factoring integers is difficult. This leads to the question of algorithmic complexity, which is related to the extremal structures: given a network, efficiently find the smallest set of nodes which disconnect the network; or given a code, efficiently decode a received message. The researcher plans to use modern combinatorial and probabilistic techniques to approach some central problems in the area and to study the practical algorithms which these methods generate. He will collaborate with PhD students and teach advanced courses on these topics.

该建议涉及组合学的研究，重点是极值结构和相关算法。 这一领域目前非常活跃，这些方法是其他数学学科以及其他科学领域（如统计力学、理论计算机科学、信息和编码理论）中许多应用的核心。 该提议者旨在研究极值组合学中的特定中心问题，包括图兰问题，图中的圈，图和超图着色问题以及随机图中的阈值。这些问题的核心是完善的数学技术，从各个领域的数学，以及新开发的概念，伪随机的图形和超图，不等式浓度的措施，和鞅。 对于这些主题中的许多主题，主要定理的证明也与算法复杂性问题，以及关于随机算法和去随机化的问题有关。提出的许多问题，如偶数循环的极值问题，长期以来一直是公开的;任何新的进展都可能产生重大的理论影响，至少会产生一些实际后果。虽然这些开放的问题是重要的，显然是困难的，新的方法和标准的组合技术结合一些新的想法提供了新的希望，解决他们。 极值组合学是研究数学结构的学科，这些数学结构对它们可能包含的子结构有约束。极值结构是满足这些约束的结构，并且相对于某种密度度量是最优的。例如，可以要求在纠正给定数量的比特错误的同时能够安全地传输消息的最小码长。 这些极端结构在许多科学领域中自然出现。作为另一示例，给定网络，可以要求其故障将导致网络断开的节点的最小数量。这些问题通常是数字和通信安全、网络搜索、可靠的数据传输、网络动态以及传染病或信息传播的核心;因此，它们在理论计算机科学、信息论和统计力学等三个领域都有应用。 更具体的例子包括用于定性网络搜索的大型数字数组的乘法-这些矩阵往往有数十亿的行和列; RSA密码系统，它支撑了现代数字安全的大部分，并且强烈地基于对整数进行因子分解是困难的信念。这导致了算法复杂性的问题，这与极值结构有关：给定一个网络，有效地找到断开网络的最小节点集;或者给定一个代码，有效地解码接收到的消息。研究人员计划使用现代组合和概率技术来解决该领域的一些中心问题，并研究这些方法产生的实用算法。 他将与博士生合作，教授有关这些主题的高级课程。