13 Metric embedding
A set \(X\) with \(d:X\times X\to \mathbb {R}^+\) symmetric, vanishing only on the diagonal, and satisfying the triangle inequality.
For \(f:X\to (\mathbb {R}^n,\ell _2)\), \(\mathrm{distortion}(f)= \mathrm{expansion}(f)\cdot \mathrm{contraction}(f)\), the product of the largest ratios \(\| f(x)-f(y)\| /d(x,y)\) and \(d(x,y)/\| f(x)-f(y)\| \).
The \(4\)-point metric with one centre at distance \(1\) and the others at distance \(2\) has no isometric Euclidean embedding.
Each leaf–centre–leaf triple would be collinear, forcing all four points onto a line, contradicting the mutual distance \(2\) of the leaves.
\(c_2(X,d)\) is the least distortion of an embedding of \((X,d)\) into Euclidean space (achievable with \(n\le |X|\)).
Every \(n\)-point metric embeds into Euclidean space with distortion \(O(\log n)\).
An \(\ell _2\) (\(\ell _1\)) metric is one isometric to a finite subset of \((\mathbb {R}^n,\ell _2)\) (resp. \(\ell _1\)).
Any \(n\)-point \(\ell _2\) metric embeds into \(O(\log n/\epsilon ^2)\) dimensions with distortion \(\le 1+\epsilon \).
\(c_2(X,d)\) is computable in polynomial time by semidefinite programming.
Scaling contraction to \(1\), \(\mathrm{distortion}\le \gamma \) iff there is a PSD Gram matrix \(Z\) with \(d(x_i,x_j)^2\le z_{ii}+z_{jj}-2z_{ij}\le \gamma ^2 d(x_i,x_j)^2\); this feasibility problem is solved by the ellipsoid method.
\(Z\) is PSD iff \(\sum _{ij}q_{ij}z_{ij}\ge 0\) for every PSD \(Q\).
(\(\Leftarrow \)) take \(Q=vv^\top \) to get \(v^\top Zv\ge 0\). (\(\Rightarrow \)) every PSD \(Q\) is a sum of rank-one PSD matrices \(vv^\top \), on each of which the inequality holds.
\(c_2(X,d)=\max _{P\in \mathrm{PSD},\, P\mathbf1=0} \sqrt{\frac{\sum _{p_{ij}{\gt}0}p_{ij}d(x_i,x_j)^2}{-\sum _{p_{ij}{\lt}0}p_{ij}d(x_i,x_j)^2}}\).
Dualizing the feasibility problem of Theorem 245: a contradicting nonnegative combination selects a PSD \(P\) with \(P\mathbf1=0\) (to cancel diagonal terms), yielding \(0\ge \sum _{p_{ij}{\gt}0}p_{ij}d^2+\gamma ^2 \sum _{p_{ij}{\lt}0}p_{ij}d^2\), contradictory exactly below the stated ratio.
\(c_2(G)=c_2(V(G),d_G)\) for the shortest-path metric.
\(c_2(Q_r)=\sqrt r\).
The identity embedding gives distortion \(\sqrt r\). For the lower bound take \(P\) with \(P(x,x)=r-1\), \(P(x,y)=-1\) for edges, \(+1\) for antipodes; then \(P\mathbf1=0\), \(P\) is PSD, and Theorem 247 gives \(\sqrt{2^rr^2/(2^rr)}=\sqrt r\).
A graph on \(n\) vertices with minimum degree \(\ge n/2\) has a Hamiltonian cycle.
For \(k\)-regular \(G\) of even order \(n\), the graph \(H\) joining vertices at \(G\)-distance \(\ge \lfloor \log _kn\rfloor \) has a perfect matching.
At most \(n/2\) vertices lie within distance \(\lfloor \log _kn\rfloor -1\), so \(H\) has minimum degree \(\ge n/2\); by Dirac’s theorem \(H\) has a Hamiltonian cycle, hence (even \(n\)) a perfect matching.
If \(G\) is an \((n,k)\)-graph with \(\lambda _2\le k-\epsilon \), then \(c_2(G)=\Omega (\log n)\).
Let \(B\) be a perfect matching of the far-graph \(H\) (Lemma 251) and \(P=kI-A_G+\tfrac \epsilon 2(B-I)\). Then \(P\mathbf1=0\), and for \(x\perp \mathbf1\), \(x^\top (kI-A_G)x\ge \epsilon \| x\| ^2\) while \(x^\top (B-I)x\ge -2\| x\| ^2\), so \(P\) is PSD. In Theorem 247, \(-\sum _{p_{ij}{\lt}0}d^2p_{ij}=kn\) and \(\sum _{p_{ij}{\gt}0}d^2p_{ij}\ge \tfrac \epsilon 2n\lfloor \log _kn\rfloor ^2\), giving \(c_2(G)=\Omega (\log n)\).
For \(k\)-regular \(G\) and any \(f:V\to \mathbb {R}^n\), \(\mathbb {E}_{u,v}\| f(u)-f(v)\| ^2\le \tfrac k{k-\lambda _2}\mathbb {E}_{(u,v)\in E}\| f(u)-f(v)\| ^2\).
Reduce to scalar zero-average \(f\) (both sides additive over coordinates and shift-invariant); the inequality is then the variational characterization of \(\lambda _2\).
Computing \(h(G)\) is co-\(\mathbf{NP}\)-hard; up to a constant it reduces to the sparsest cut \(\min _S|E(S,\overline S)|/(|S|(n-|S|))\).
Ship \(\delta \) units between every pair under unit edge capacities; \(\delta _{\max } (G)\) is the maximum feasible \(\delta \) (a linear program).
The cut cone is the convex cone of \(\ell _1\) metrics; its extreme rays are the cut metrics \(d_S(x,y)=\mathbf1[|\{ x,y\} \cap S|=1]\).
\(\delta _{\max }(G)\le \min _S\frac{|E(S,\overline S)|}{|S|(n-|S|)}\le O(\delta _{\max }(G)\log n)\).
The left inequality is capacity counting. By LP duality \(\delta _{\max }\) is the minimum of \(\sum _{(i,j)\in E}d_{ij}/\sum _{ij}d_{ij}\) over metrics; over \(\ell _1\) metrics the minimum is attained at a cut metric, giving the sparsest cut, and by Bourgain’s theorem restricting to \(\ell _1\) loses only \(O(\log n)\).
\((X,d)\) is of negative type if \(\sqrt d\) is an \(\ell _2\) metric; every \(\ell _1\) metric is of negative type.
Whether every negative-type metric embeds into \(\ell _1\) with bounded distortion (refuted by Khot–Vishnoi with an \((\log \log n)^c\) lower bound).