Correlation Problems and Combinatorial Applications of Entropy

熵的相关问题和组合应用

• 批准号: 0701175
• 负责人: Jeffry Kahn
• 金额: $ 45.37万
• 依托单位: Rutgers University New Brunswick
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2007
• 资助国家: 美国
• 起止时间: 2007-06-01 至 2013-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0701175&HistoricalAwards=false
• 关键词: Correlation; Problems; Combinatorial; Applications; Entropy

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.

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