Problems in Combinatorial Functional Analysis

在试图解决TALAGRAND在偏离中位数的情况下提出的问题时，PI和他的合作者在乘积图上浓度不等的情况下引入了次高斯常数的概念。估计次高斯常数相当于估计某个对数矩母函数，这对于建立图上的紧集中现象是有用的。Maurey、McDiarmid和其他人的一些已知(经典)结果是使用这个概念推导出来的，仍然留下了一些基本问题，其中一些问题在本提案中得到了解决。除了次高斯常数，在最近的工作中，PI(和他的合作者)在马尔可夫链和图的离散设置中引入了新的Poincare-and Log Sobolev型函数常数。算法问题，如计算和近似这些和相关的等周常数在这里被考虑。组合和泛函分析技术的结合已被证明是相当有成效的，特别是在最近几年，在研究离散等周常数以及在等周常数和庞加莱类型常数之间建立紧不等式方面，特别是在最近几年，已经被证明是相当有效的。这些不等式反过来对极值和概率组合学中的问题以及随机化和近似算法的设计和分析都是无价的。在离散的情况下，更精细的所谓的Log-Sobolv不等式，以及它们与等周和浓度不等的联系，并没有被很好地理解。这里讨论了一些基本问题，以期更好地理解。总而言之，这项建议解决了离散概率和组合学中的一些重要和当前的问题。其中一些问题的动机源于概率论和计算机科学领域中出现的问题。

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.