Correlation Problems and Combinatorial Applications of Entropy

Rutgers University New Brunswick, New Brunswick NJ

Investigators

Abstract

This project focuses on two areas where combinatorics and other parts of mathematics meet: correlation inequalities, and applications of entropy to combinatorial problems. Correlation inequalities deal with positive and negative reinforcement among events in a probability space (e.g. how does knowing event A has occurred affect the probability of event B?). Questions of this type are fundamental for probability and statistical mechanics, and also play important roles in, e.g., statistics, computer science and discrete mathematics. Nonetheless, despite a great deal of activity over the last 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 those missing insights. Shannon entropy, introduced in 1948 for coding-theoretic purposes, has, mostly in the last ten or fifteen years, turned out to be a valuable tool for certain kinds of combinatorial extremal problems. (For example: how many independent sets---i.e. sets of vertices spanning no edges---can one have in a regular graph 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 and likely to force further development of entropy techniques. One theme common to the two parts of the project is an interest in applying ideas and methods across mathematical boundaries, meaning, on the one hand, bringing the principal investigator's combinatorial 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 attack combinatorial problems. Many of the problems proposed seem quite hard, but also quite fundamental, as evidenced in particular by the fact that they 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 have been mostly combinatorial, the PI's original contributions to entropy methods were developed to attack problems in probability and statistical mechanics.) It is also true that the difficulties underlying some of these problems appear to show up elsewhere, for instance in the now very active area of "Markov chain Monte Carlo," and in "Mason's Conjecture," a celebrated, 35-year-old problem in matroid theory. So it seems likely that progress on some of the present questions would have further repercussions.