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.