Advances in Metric Ramsey Theory and its Applications
Advances in Metric Ramsey Theory and its Applications
复制标题
度量拉姆齐理论及其应用进展
DOI：
--
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Y. Bartal
中科院分区：
文献类型：
--
作者：
Y. Bartal
度量拉姆齐理论关注的是寻找更复杂度量空间的大的结构良好的子集。对于有限度量空间，这个问题首先由Bourgain、Figiel和Milman cite{bfm}研究，并由Bartal等人进一步深入研究。引用{BLMN 03}。在本文中，我们提供了确定性的结构，这个问题通过一个新的概念？{度量拉姆齐分解}。这种方法产生了几个更多的应用，反映在度量嵌入理论的一些基本结果。应用程序包括各种结果在度量拉姆齐理论，包括第一个确定性建设产生拉姆齐定理与紧界，以及更强的定理和性质，这意味着适当的距离预言的应用。此外，这种分解提供了有限度量空间到欧氏空间的第一个确定性Bourgain型嵌入，以及到超度量的最佳多重嵌入，从而改进了其在近似和在线算法中的应用。这里提出的分解，技术及其后果已经被用于度量嵌入领域的各种应用的最新研究。
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.