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.