単位距離グラフ
単位距離グラフは、高次元ユークリッド空間に拡張できる。グラフは、十分に高い次元の点の集合として考えられる。前原は、グラフを高次元に埋め込む際、必要な次元は、最大次数の2倍が上界となる可能性があることを示した。
すべての点間が単位距離となるために必要な次元と、辺が単位距離になるために必要な次元は、大きく異なる場合がある。例えば、2n -頂点のcrown graphは、4次元ですべての辺が単位長さになるような配置を有するが、全ての点間が単位距離となるためには少なくとも n - 2次元が必要である(Erdős & Simonovits 1980)。
Paul Erdős (1946) は、 n 個の点を配置し、単位距離だけ離れた点対をいくつ生成できるか?という問題を考えた。グラフ理論的には、単位距離グラフをどこまで密にできるか?と言いかえられる。
超立方体グラフは単位距離を O ( n log  n ) {\displaystyle O(n\log n)} だけ有し、下界となる。正方形格子状に配置することで、ポール・エルデシュは下界を
O ( n 1 + c / log  log  n ) , {\displaystyle O(n^{1+c/\log \log n}),}
まで改善した。 さらに、このような形式で上界を設けられるかという問題に対して500ドルの賞金を用意した(Kuperberg 1992)。現在知られている最も良い上界は、Joel Spencer, Endre Szemerédi, and William Trotter (1984)による、: O ( n 4 / 3 ) {\displaystyle O(n^{4/3})} である。 この上界は単位円の隣接する個数としても考えられるため、Szemerédi–Trotter theoremと関連が深い。ハミンググラフ(3,3) はこの上界の1つであり、27頂点で81辺を持つ。