Problems in Combinatorial Functional Analysis

当试图解决Talagrand在偏离中位数的背景下提出的问题时，PI和他的合作者在积图的浓度不等式背景下引入了亚高斯常数的概念。估计亚高斯常数相当于估计某个对数矩生成函数，对于在图上建立紧密集中现象是有用的。Maurey， McDiarmid和其他人的一些已知（经典）结果是使用这个概念推导出来的，但仍然存在一些基本问题，其中一些问题在本提案中得到了解决。除了亚高斯常数，在最近的工作中，PI（与他的合作者）在马尔可夫链和图的离散设置中引入了新的庞加莱和Log sobolev型泛函常数。算法问题，如计算和近似这些和相关的等周常数在这里被考虑。并提出了积图上顶点等周常数的估计及其泛函类比等数学问题。组合分析和泛函分析技术的结合已被证明是卓有成效的，特别是在最近几年，在研究离散等周和建立等周常数和庞加莱型常数之间的紧密不等式方面。这些不等式对于极值组合和概率组合的问题，以及随机和近似算法的设计和分析都是非常宝贵的。在离散情况下，不太容易理解的是所谓的Log-Sobolev不等式，以及它们与等周不等式和浓度不等式的联系。为了更好地理解，在此讨论一些基本问题。综上所述，本建议解决了离散概率和组合学中一些重要的和当前的问题。其中一些问题的动机源于概率论和计算机科学领域出现的问题。

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.