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.

该提案涉及组合学的研究，重点关注极端结构和相关算法。 该领域目前非常活跃，这些方法对于其他数学学科以及其他科学领域（例如统计力学，理论计算机科学和信息以及编码理论）的许多应用至关重要。 该提议者旨在研究极端组合制剂中的特定主要问题，包括Turan问题，图表中的周期，图形和超图着色问题以及随机图中的阈值。这些问题的核心是来自数学各个领域的数学技术，以及图形和超图中的伪随身杂音的新概念，量度集中的不平等以及martingales。 对于许多这些主题，主要定理的证据也与算法复杂性问题以及有关随机算法和降低的问题有关。长期以来，提出的许多问题，例如即使是循环的极端问题，也已经开放。任何新的进步都可能产生实质性的理论影响，至少有一些实际的后果。尽管这些开放问题很重要，而且很困难，但是新的方法和标准组合技术与一些新想法相结合为解决方案提供了新的希望。 极端组合学是对数学结构的研究，这些数学结构对其可能包含的子结构有限制。极端结构是满足这些约束的一种，并且相对于某种密度度量是最佳的。例如，可以要求在纠正给定数量的位错误时可以安全地传输消息的最小尺寸。 这些极端结构自然出现在许多科学领域。作为另一个示例，给定一个网络可能会要求最小数量的节点数量会导致网络断开连接。这些问题通常位于数字和通信安全，网络搜索，可靠的数据传输，网络动态以及传染病或信息的传播的核心；因此，他们在理论计算机科学，信息理论和统计力学上都有应用，以提及三个领域。 进一步的具体示例包括用于定性网络搜索的大量数字数量的乘法 - 这些矩阵往往具有数十亿的行和列； RSA加密系统是基于现代数字安全的大部分基础的，并强烈地基于认为会使整数很困难。这导致了算法复杂性的问题，该问题与极端结构有关：给定网络，有效地找到了断开网络连接的最小节点。或给出的代码，有效地解码收到的消息。研究人员计划使用现代组合和概率技术来解决该领域的一些核心问题，并研究这些方法产生的实际算法。 他将与博士生合作，并就这些主题教授高级课程。