Minimal Euclidean representations of graphs

A simple graph G is representable in a real vector space V if there is an embedding of the vertex set in V such that the Euclidean distance between two vertices u and v depends only on whether or not u and v are adjacent. The Euclidean representation number of G is the smallest dimension in which G is representable. Representations of graphs were introduced by Pouzet in 1977 as a means of showing that certain graph invariants of Tutte are reconstructible. In this talk, we use Euclidean distance matrices to give an exact formula for the Euclidean representation number of any graph in terms of its spectrum and main values.