solidot新版网站常见问题,请点击这里查看。
消息
本文已被查看5711次
Embedding graphs in Euclidean space. (arXiv:1802.03092v1 [math.CO])
来源于:arXiv
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\H{o}s and Simonovits [Ars Combin. 9 (1980)
229--246], we show that any graph with less than $\binom{d+2}{2}$ edges has
dimension at most $d$. Improving their result, we prove that 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/\sqrt{2}$. 查看全文>>