Embedding the diamond graph in \(L_p\) and dimension reduction in \(L_1\) (Q1762655): Difference between revisions

Let \(G_k\) be the \(k\)-th diamond graph. The authors prove that for every \(1<p\leq 2\), any embedding of \(G_k\) into \(L_p\) incurs distortion of at least \(\sqrt{1+(p-1)k}\). This implies that an \(L_1\) analog of the Johnson-Lindenstrauss dimension reduction lemma does not exist. As a corollary, it is also proven that for every \(n\in\mathbb N\), there exists an \(n\)-point subset \(X\subseteq L_1\) such that for every \(D>1\), if \(X\) \(D\)-embeds into \(\ell_1^d\), then \(d\geq n^{\Omega(1/D^2)}\).