Problems in Combinatorial Functional Analysis

Georgia Tech Research Corporation, Atlanta GA

Investigators

Abstract

While attempting to solve a problem raised by Talagrand in the context of deviations from a median, the PI and his collaborators introduced the notion of the subgaussian constant in the context of concentration inequalities on product graphs. Estimating the subgaussian constant amounts to estimating a certain log-moment generating function, and is useful in establishing tight concentration phenomenon on graphs. Some known (classical) results of Maurey, McDiarmid, and others are derived using this notion, leaving open still some fundamental problems, a few of which are addressed in this proposal. Besides the subgaussian constant, in recent work the PI (with his collaborators) has introduced new Poincare- and Log Sobolev-type functional constants in the discrete setting of Markov chains and graphs. Algorithmic problems such as computing and approximating these and related isoperimetric constants are considered here. Mathematical problems such as estimating the vertex isoperimetric constant and its functional analog on product graphs are also proposed. The combination of combinatorial and functional-analytic techniques has proved quite fruitful, especially in the last few years, in investigating discrete isoperimetry, and in establishing tight inequalities between isoperimetric and Poincare-type constants. These inequalities in turn were invaluable to problems in extremal and probabilistic combinatorics, and to the design and analysis of randomized and approximation algorithms. Not as well understood, in the discrete setting, are the finer so-called Log-Sobolev inequalities, and their connection to isoperimetric and concentration inequalities. Some fundamental problems are addressed here with a view towards a better understanding. In summary, this proposal addresses some important and current problems in discrete probability and combinatorics. The motivation for some of these problems stems from questions which arose in the fields of probability theory and computer science.