PROBLEMS OF DISTANCE GEOMETRY AND CONVEX PROPERTIES OF QUADRATIC MAPS

A weighted graph is called d-realizable if its vertices can be chosen in d-dimensional Euclidean space so that the Euclidean distance between every pair of adjacent vertices is equal to the prescribed weight. We prove that if a weighted graph with k edges is d-realizable for some d, then it is d-realizable for d = [(square-root 8k + 1 - 1)/2] (this bound is sharp in the worst case). We prove that for a graph G with n vertices and k edges and for a dimension d the image of the so-called rigidity map R(dn) --> R(k) is a convex set in R(k) provided d greater-than-or-equal-to [(square-root 8k + 1 - 1)/2]. These results are obtained as corollaries of a general convexity theorem for quadratic maps which also extends the Toeplitz-Hausdorff theorem. The main ingredients of the proof are the duality for linear programming in the space of quadratic forms and the ''corank formula'' for the strata of singular quadratic forms.