Lower bounds on the distortion of embedding finite metric spaces in graphs (Q1380790): Difference between revisions

Given two finite metric spaces \((X,d)\) and \((Y,\delta)\) with \(|X|=|Y|\), and a \(1-1\) map \(f:X \to Y\), the Lipschitz norm \(||f||\) of \(f\) is \text{\(\displaystyle\max_{s\neq t \in X}{\delta(f(s),f(t))\over d(s,t)}\)} and the Lipschitz distance between \(X\) and \(Y\) is \(\text{dist}(X,Y)=\inf_{f:X\to Y} ||f||\cdot ||f^{-1}||\), where the infimum is taken over all \(1-1\) maps. The authors investigate the question of how well a finite metric space can be represented by a subspace of a graph, subject to certain restrictions. Specifically, they prove (1) if \(H\) is a simple, unweighted connected graph with \(n\) vertices, and if \(G\) is any (weighted) graph with the same number of vertices but strictly fewer edges than \(H\), then \(\text{dist}(H,G)\geq g/3 - 1\), where \(g\) is the girth of \(H\), and (2) with \(H\) as above, if \(G\) is any weighted graph with at least \(n\) vertices, and with \(\chi(G)<\chi(H)\), then for any \(n\)-point subspace \(S\) of the vertices of \(G\), \(\text{dist}(H,S)\geq g/4 - {3\over 2}\). They also investigate how well \(H\) can be approximated by a subspace of a graph \(G\) with \(\chi(G)<\chi(H)-1\) (in this case, the minimum distance is a function of the length of a second shortest cycle of \(H\)) and of how well an \(n\)-circuit can be approximated by a subspace of a tree (the distance is bounded below by \(n/3 -1\)). The latter result is then generalized to the following question: how well can the \(n\)-sphere be approximated by a subspace of a simplicial complex \(K\) of dimension \(\leq n\) with \(H_n(K)\) trivial?