Metric Ramsey理论及其应用的进展 (Advances in Metric Ramsey Theory and its Applications)

from arxiv, This is paper is still in stages of preparation, this version is not intended for distribution. A preliminary version of this article was written by the author in 2006, and was presented in the 2007 ICMS Workshop on Geometry and Algorithms. The basic result on constructive metric Ramsey decomposition and metric Ramsey theorem has also appeared in the author's lectures notes

Metric Ramsey theory is concerned with finding large well-structured subsets of more complex metric spaces. For finite metric spaces this problem was first studies by Bourgain, Figiel and Milman \cite{bfm}, and studied further in depth by Bartal et. al \cite{BLMN03}. In this paper we provide deterministic constructions for this problem via a novel notion of \emph{metric Ramsey decomposition}. This method yields several more applications, reflecting on some basic results in metric embedding theory. The applications include various results in metric Ramsey theory including the first deterministic construction yielding Ramsey theorems with tight bounds, a well as stronger theorems and properties, implying appropriate distance oracle applications. In addition, this decomposition provides the first deterministic Bourgain-type embedding of finite metric spaces into Euclidean space, and an optimal multi-embedding into ultrametrics, thus improving its applications in approximation and online algorithms. The decomposition presented here, the techniques and its consequences have already been used in recent research in the field of metric embedding for various applications.

翻译：Ramsey 理论涉及寻找大量结构完善的更复杂指标空间子集。对于有限指标空间,这一问题是Bourgain、Figigiel和Milman 和 Milman 的首次研究,Bartal 等人的深入研究 {BLMN03}。在本文中,我们通过一种新型概念,即 \ emph{ 参数Ramsey 分解概念,为这一问题提供了决定性的构造。这个方法产生了更多的应用,反映了指标嵌入理论的一些基本结果。应用包括Ramsey 标准理论的各种结果,包括首次确定性建筑产生带紧线的Ramsey理论,以及更强的理论和特性,意味着适当的距离或触角应用。此外,这种分解提供了第一个确定性布尔加宽类型,将有限的指标空间嵌入欧洲大陆空间,以及最佳的多重组合,从而改进了其在近似和在线算法中的应用。在这里介绍的脱钩式定位,技术及其后果已经用于最近各种指标领域研究的嵌入。