Mathematical Sciences: Behavior of Large Combinatorial Systems

该奖项为主要关注各种类型组合系统的长距离行为的项目提供资金，特别是图、固定边大小的超图和拟阵。一个常见的主题是，这样的行为在重要方面出奇地好，这通常是因为在与所讨论的系统相关的适当概率空间中存在大量的近似独立性。因此，该项目旨在了解概率空间的性质及其对组合问题的影响。项目的核心是关注渐近正态性和相关问题。粗略地说，研究者试图表明，各种组合定义的随机变量总是近似正态分布，没有琐碎的阻碍这种行为。研究人员最近的工作表明，在一些令人惊讶的普遍和非结构化的情况下，这种现象可能存在。希望对这些问题中的一些，包括所谓的“规范”或“核心”分布的满意答案，将支持强大的组合概率方法发展的新方向，该方法寻求应用概率思想来解决非随机组合问题。这项工作也为概率与整数规划问题及其相关线性松弛之间的关系之间的相互作用开辟了新的可能性。我们可以把整数和线性最优的渐近一致作为一个好的“远程行为”的定义，因为线性规划问题在计算上是可处理的，而整数规划通常是难以处理的。然后，非常粗略地说，一个问题的线性版本的好解给出了一个“规范分布”，它可以用来随机生成或证明原始问题的一个好解的存在性。这个想法被认为具有相当大的潜力。这项研究属于组合学的一般范畴。组合学的目标之一是寻找有效的方法来研究如何排列离散的对象集合。离散系统的行为对现代通信极为重要。例如，大型网络的设计，比如那些出现在电话系统中的网络，以及计算机科学中处理离散对象集的算法设计，这就利用了组合研究。

This award provides funding for a project concerned primarily with long range behavior of various types of combinatorial systems, especially graphs, hypergraphs of fixed edge size, and matroids. A common theme is that such behavior is surprisingly nice in important ways, and that this is often because there is a substantial amount of approximate independence in appropriate probability spaces associated with the system in question. The project thus seeks to understand both properties of said probability spaces and their consequences for combinatorial problems.The heart of the project is concerned with asymptotic normality and related issues. Roughly, the investigator seeks to show that various combinatorially-defined random variables are always approximately normally distributed in the absence of trivial obstructions to such behavior. Recent work of the investigator suggests the possibility of such a phenomenon in some surprisingly general and unstructured situations. It is hoped that satisfactory answers to some of these questions, involving so-called "canonical" or "hard-core" distributions, will support new directions in the development of the powerful probabilistic method of combinatorics, which seeks to apply probabilistic ideas to resolve non-random combinatorial problems. This work also opens new possibilities for the interplay between probability and questions about the relation between integer programming problems and their associated linear relaxations. We may take asymptotic agreement of integer and linear optima as a definition of nice "long range behavior" since linear programming problems are computationally tractable and integer programs are generally intractable. Then, very roughly, a good solution to the linear version of a problem gives a "canonical distribution" which can be used to randomly generate or prove existence of a good solution to the original problem. This idea is thought to have considerable potential. This research is in t he general area of Combinatorics. One of the goals of Combinatorics is to find efficient methods to study how discrete collections of objects can be arranged. The behavior of discrete systems is extremely important to modern communications. For example, the design of large networks, such as those occurring in telephone systems, and the design of algorithms in computer science deal with discrete sets of objects, and this makes use of combinatorial research.