Correlation Problems and Combinatorial Applications of Entropy

这个项目集中在组合学和其他数学领域相遇的两个领域：相关不等式和熵在组合问题中的应用。相关不等式处理概率空间中事件之间的正强化和负强化。知道事件A的发生会如何影响事件B的发生概率？这类问题是概率论和统计力学的基础，在统计学、计算机科学和离散数学等领域也起着重要作用。然而，尽管在过去的45年里进行了大量的活动，但似乎缺乏一些基本的见解，甚至一些最简单的问题仍然没有解决。该项目包含了新旧问题的混合，有些非常具体，有些则更普遍，但所有这些都旨在推动某些缺失的见解的方向。香农熵是1948年为了编码理论的目的而引入的，在过去的10到15年里，它被证明是解决某些组合极值问题的一个有价值的工具。(例如：有多少个独立的集合——即。不跨越任何边的顶点集——在给定顶点数和度数的正则图中可以有顶点集吗？)该项目考虑了许多这类问题，每个问题都被认为是独立的兴趣，并可能推动熵技术的进一步发展。该项目两个部分的一个共同主题是跨越数学边界应用思想和方法的兴趣，这意味着，一方面，将首席研究员的组合观点应用于其他领域的问题，这些问题大多是由这些领域的专家考虑的，另一方面，使用额外的组合思想来解决组合问题。提出的许多问题似乎很难，但也很基本，特别是它们出现在如此多不同的环境中这一事实证明了这一点。（最后一个特别指的是项目的第一部分，但不是全部；例如，尽管最近的应用大多是组合的，但PI对熵方法的最初贡献是为了解决概率和统计力学中的问题而开发的。）同样，这些问题背后的困难似乎也出现在其他地方，例如在现在非常活跃的“马尔可夫链蒙特卡罗”领域，以及在“梅森猜想”中，一个著名的、已有35年历史的问题矩阵理论。因此，目前一些问题的进展似乎可能会产生进一步的影响。

This project focuses on two areas where combinatoricsand other parts of mathematics meet:correlation inequalities, and applications of entropy tocombinatorial problems.Correlation inequalities deal with positive and negativereinforcement among events in a probability space(e.g. how does knowing event A has occurredaffect the probability of event B?).Questions of this type are fundamental for probabilityand statistical mechanics, and also play importantroles in, e.g., statistics, computer scienceand discrete mathematics.Nonetheless, despite a great deal of activity over thelast forty-five years, some basic insights seem to be lacking,and even some of the simplest questions remain open.The project contains a mix of old and new problems,some quite specific, others more general,but all intended to push in the direction of some of thosemissing insights.Shannon entropy, introduced in1948 for coding-theoretic purposes,has, mostly in the last ten or fifteen years,turned out to be a valuable toolfor certain kinds of combinatorial extremal problems.(For example: how many independent sets---i.e. setsof vertices spanning no edges---can one have in a regulargraph with given degree and number of vertices?)The project considers a number of problems of this type,each thought to be both of independent interest andlikely to force further development of entropytechniques. One theme common to the two parts of the project is an interestin applying ideas and methods across mathematical boundaries,meaning, on the one hand, bringing the principal investigator'scombinatorial perspective to bear on problems from other areas that have mostly been considered by specialists in those areas, and,on the other, using extra-combinatorial ideas to attackcombinatorial problems.Many of the problems proposed seem quite hard, but alsoquite fundamental, as evidenced in particular by the fact thatthey arise in so many disparate contexts.(This last refers especially to the first part of the project,but not entirely; for instance, though recent applications havebeen mostly combinatorial, the PI's original contributions toentropy methods were developed to attack problems in probability and statistical mechanics.)It is also true that the difficulties underlying some ofthese problems appear to show up elsewhere, for instance inthe now very active area of "Markov chain Monte Carlo,"and in "Mason's Conjecture," a celebrated, 35-year-old problemin matroid theory. So it seems likely that progress on some ofthe present questions would have further repercussions.