On a problem of Specker about Euclidean representations of finite graphs

Abstract

Say that a graph $G$ is \emph{representable in ${\mathbb{R}}^n$} if there is a map $f$ from its vertex set into the Euclidean space ${\mathbb{R}}^n$ such that $\Vert f(x)-f(x^{\prime })\Vert =\Vert f(y)-f(y^{\prime })\Vert$ iff $\{x,x^{\prime }\}$ and $\{y,y^{\prime }\}$ are both edges or both non-edges in $G$. The purpose of this note is to present the proof of the following result, due to Einhorn and Schoenberg: if $G$ finite is neither complete nor independent, then it is representable in ${\mathbb{R}}^{|G|-2}$. A similar result also holds in the case of finite complete edge-colored graphs.

8 pages, 2 figures. The 2011 version of this article was supposed to remain unpublished because the question it answers was actually answered in 1966 (even before the question existed!). This new version, with a typo corrected on p.3, will nevertheless appear as an expository article in Expo. Math