Extremal combinatorial structures and algorithms

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

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.