Some low distortion metric Ramsey problems (Q1764172): Difference between revisions

The {distortion} of an embedding \(f:M\to X\) between two metric spaces is defined as \[ \text{dist}(f) = \sup_{x,y\in M,x\not=y} \frac{d_X(f(x),f(y))}{d_M(x,y)} \cdot \sup_{x,y\in M,x\not=y} \frac{d_M(x,y)}{d_X(f(x),f(y))}. \] The least distortion required to embed \(M\) in \(X\) is denoted by \(c_X(M)\). When \(c_X(M)\leq\alpha\) we say that \(M\) \(\alpha\)-embeds in \(X\). The ``metric Ramsey function'' \(R_X(\alpha,n)\) is then defined to be the largest integer \(m\) such that every \(n\)-point metric space has a subspace of size \(m\) that \(\alpha\)-embeds into \(X\). The main result of this note is to refine the study of the behavior of \(R_X(\alpha,n)\) for \(\alpha\) in the neighborhood of \(2\), where a ``phase-transition'' occurs, in the important special case \(X=\ell_p\), \(p\in[1,\infty]\) (the asymptotic behavior of \(R\) as \(n\to\infty\) changes as \(\alpha\) crosses the \(\alpha=2\) line, as the same authors proved in [Ann. Math. 162 (2) (2005)]. Specifically, the authors prove that there is an absolute constant \(c>0\) such that for every \(0<\delta<1\): (1) for \(1\leq p<2\), \(R_{\ell_p}(2-\delta,n)\leq e^{c/\delta^2}\log n\); and (2) for \(2<p<\infty\), \(R_{\ell_p}(2^{2/p}-\delta,n)\leq e^{c/p^2\delta^2}\log n\).