Problems of distance geometry and convex properties of quadratic maps (Q1346137)

Let \(G = (V, E, \rho)\) be a graph. The elements of \(V\), \(E\) are called vertices, edges respectively. \(\rho : E \to \mathbb{N}\) is a mapping that determines the weights of the edges. \(G\) is said to be \(d\)-realizable if its vertices can be chosen in the Euclidean space \(\mathbb{R}^d\) so that the Euclidean distance between every pair of adjacent vertices \(v_i\), \(v_j\) is equal to the weight of the connecting edge. The following results are obtained: Let \(|E |= k\). If \(G\) is \(d\)-realizable for some \(d\) then it is \(d_0\)-realizable for \(d_0 := [(\sqrt {8k + 1} - 1) {1\over 2}]\). The image of the `rigidity map' \(\mathbb{R}^{dn} \to \mathbb{R}^k\) is a convex set in \(\mathbb{R}^k\) provided \(d \geq d_0\). These results are corollaries of a convexity theorem which may be considered as an extension of the Toeplitz-Hausdorff theorem.