Lower bounds for local versions of dimension reductions (Q1017913)

The paper is devoted to the following problem: given a graph \(G = (V ,E)\) on \(V = [n] = {1, 2, \dots, n}\), \(\varepsilon > 0\) and vectors \(x_1,\dots , x_n\in\mathbb{R}^n\), what is the minimal \(k\in \mathbb{N}\) such that there are vectors \(y_1,\dots, y_n\in \mathbb{R}^k\) satisfying \((1-\varepsilon)\| x_i -x_j\| \leq \| y_i -y_j\| \leq (1+\varepsilon)\| x_i-x_j\| \) for every \((i,j)\in E\)? In the case when \(G\) is the complete graph \(K_n\) on \(n\) vertices, this problem is addressed by the well-known result of \textit{W.\,B.\thinspace Johnson} and \textit{J.\,Lindenstrauss} [Contemp.\ Math.\ 26, 189--206 (1984; Zbl 0539.46017)] which asserts that in this case \(k\) can be taken to be \(O(\log n/(\varepsilon^2))\) and an example due to \textit{N.\,Alon} [Combin.\ Probab.\ Comput.\ 18, No.\,1--2, 3--15 (2009; doi:10.1017/S0963548307008917)] which shows that, for \(K_n\), this is basically the best possible; in this example, \(k\) must be \(\Omega(\log n/(\varepsilon^2 \log(1/\varepsilon)))\). The authors are mostly interested in the case when \(G\) is the graph induced by the \(m\) nearest neighbors of \(x_1,\dots , x_n\). That is, \((i,j)\in E\) if and only if \(x_j\) is among the \(m\) nearest neighbors to \(x_i\) or \(x_i\) is among the \(m\) nearest neighbors to \(x_j\). The problem in this case was suggested by [\textit{I.\,Abraham, Y.\,Batal} and \textit{O.\,Neiman}, in: Proceedings of the 39th annual ACM symposium on theory of computing (STOC'07), San Diego, June 11--13, 2007, 631--640 (2007; Zbl 1232.68160)], it is motivated by several applications discussed in their paper. The authors find an example (with \(m = 3\)) such that for each sufficiently small \(\varepsilon > 0\), \(k\) still needs to be \(\Omega(\log n)\). The authors do not obtain good dependence on \(\varepsilon\). More precise results are obtained in the case when we additionally require that the mapping \(x_i\mapsto y_i\) preserves the set of nearest neighbors.