L_1 embeddings of the Heisenberg group and fast estimation of graph isoperimetry
L_1 embeddings of the Heisenberg group and fast estimation of graph isoperimetry
复制标题
海森堡群的 L_1 嵌入和图等周法的快速估计
DOI：
10.1142/9789814324359_0110
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
A. Naor
中科院分区：
文献类型：
--
作者：
A. Naor
我们考察了双Lipschitz嵌入理论与组合优化中的最稀疏割问题之间的联系。最稀疏切割问题的故事是分析、几何和概率与离散数学中的计算问题之间深度相互作用的一个显著例子。我们解释了关键思想是如何在过去20年中演变的，重点是与Banach空间论、几何测度论和几何群论的相互作用。作为一个重要的例证，我们将检查最近建立的与海森堡群的结构的联系，以及它的卡诺-卡拉斯几何与勒贝格空间的几何L_1的不相容。
We survey connections between the theory of bi-Lipschitz embeddings and the Sparsest Cut Problem in combinatorial optimization. The story of the Sparsest Cut Problem is a striking example of the deep interplay between analysis, geometry, and probability on the one hand, and computational issues in discrete mathematics on the other. We explain how the key ideas evolved over the past 20 years, emphasizing the interactions with Banach space theory, geometric measure theory, and geometric group theory. As an important illustrative example, we shall examine recently established connections to the the structure of the Heisenberg group, and the incompatibility of its Carnot-Carath\'eodory geometry with the geometry of the Lebesgue space $L_1$.