Embedding graphs in Euclidean space

The dimension of a graph G is the smallest d for which its vertices can be embedded in d-dimensional Euclidean space in the sense that the distances between endpoints of edges equal 1 (but there may be other unit distances). Answering a question of Erdős and Simonovits (1980) [5], we show that any graph with less than (d+22) edges has dimension at most d. Improving their result, we prove that the dimension of a graph with maximum degree d is at most d. We show the following Ramsey result: if each edge of the complete graph on 2d vertices is coloured red or blue, then either the red graph or the blue graph can be embedded in Euclidean d-space. We also derive analogous results for embeddings of graphs into the (d−1)-dimensional sphere of radius 1/2.