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.