Correlation Problems and Combinatorial Applications of 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.