The University of Michigan Combinatorics Seminar
Winter 2000
February 25, 4:10-5:00, 3866 East Hall

On realization of weighted graphs as graphs
of distances between points in Euclidean space

Alexander Barvinok

University of Michigan


Given an edge-weighted graph and a number d, is it possible to place the vertices of the graph in d-dimensional Euclidean space so that the distance between adjacent points is equal to the prescribed weight? I am planning to discuss two results about this problem. The first result is constructive and has a transparent mechanical interpretation, whereas the second result, while being only epsilon stronger, is non-constructive and has a mysterious mechanical interpretation.