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 Erdos and Simonovits (1980) [5], we show that any graph with less than ((d+2)(2)) 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/root 2, (C) 2019 Elsevier Inc. All rights reserved.