Problems in Combinatorial Functional Analysis

在试图解决Talagrand在偏离中位数的背景下提出的问题时，PI和他的合作者在产品图上的浓度不等式的背景下引入了亚高斯常数的概念。 估计次高斯常数相当于估计一个特定的对数矩母函数，并有助于建立图上的紧集中现象。一些已知的（经典的）结果Maurey，McDiarmid，和其他人都是使用这个概念，仍然留下开放的一些基本问题，其中一些是解决这个建议。 除了亚高斯常数，在最近的工作中，PI（与他的合作者）在马尔可夫链和图的离散设置中引入了新的Poincare和Log Sobolev型函数常数。这里考虑了计算和近似这些和相关等周常数的数学问题。 组合技术和泛函分析技术的结合在研究离散等周性、建立等周性常数与Poincare型常数之间的紧不等式等方面取得了丰硕的成果，特别是近几年来. 这些不等式对极值和概率组合学的问题，以及随机和近似算法的设计和分析都是非常宝贵的。在离散的情况下，人们还不太了解所谓的对数-索伯列夫不等式，以及它们与等周不等式和浓度不等式的联系。这里讨论一些基本问题，以便更好地理解。总之，这个建议解决了离散概率和组合学中一些重要的和当前的问题。其中一些问题的动机源于概率论和计算机科学领域出现的问题。

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.