次元（グラフ理論）

数学、特にグラフ理論において、グラフの次元とは、すべての辺の長さが単位である 次元nのユークリッド空間にグラフの「古典的表現」が存在するような最小の整数nのことです。

古典的な表現では、頂点は異なる点である必要がありますが、辺は互いに交差する場合があります。^[1]

グラフGの次元は と書きます。 ${\displaystyle \dim G}$

たとえば、ピーターセングラフは では単位辺で描くことができますが、 では描くことができません。したがって、その次元は 2 です (右の図を参照)。 ${\displaystyle E^{2}}$${\displaystyle E^{1}}$

この概念は1965年にポール・エルデシュ、フランク・ハラリー、ウィリアム・タットによって導入されました。^[2]これは単位距離グラフの概念を2次元以上に一般化したものです。

最悪の場合、すべての頂点のペアが接続され、完全なグラフになります。

すべての辺の長さが単位である完全なグラフを浸すには、次元のユークリッド空間が必要です。^[3]たとえば、右に示すように、浸すには2次元（正三角形）が必要で、浸すには3次元（正四面体）が必要です。 ${\displaystyle K_{n}}$${\displaystyle n-1}$${\displaystyle K_{3}}$${\displaystyle K_{4}}$

${\displaystyle \dim K_{n}=n-1}$

つまり、完全グラフの次元は、同じ数の頂点を持つ 単体グラフの次元と同じです。

左の図に示すように、 のすべてのスター グラフ ( ) は次元 2 を持ちます。m が 1 または 2 であるスター グラフには次元1のみ が必要です。 ${\displaystyle K_{m,1}}$${\displaystyle m\geq 3}$

完全な二部グラフ の次元 ( ) は、右の図のように、半径が 1 未満の円上にm 個の頂点を配置し、他の 2 個の頂点を円の平面の両側に適切な距離を置いて配置することによって描くことができます。は平面上に単位菱形として描くことができるため、次元は 2 です。 ${\displaystyle K_{m,2}}$${\displaystyle m\geq 3}$${\displaystyle K_{2,2}}$

要約すると:

${\displaystyle \dim K_{m,n}=1,2,3{\text{ または }}4}$mとnの値に応じて異なります。

上記のグラフの次元の定義は、最小のn表現について次のように述べています。

• Gの 2 つの頂点が辺で接続されている場合、それらの頂点は単位距離離れていなければなりません。
• ただし、単位距離離れた 2 つの頂点は必ずしも辺で接続されるわけではありません。

この定義は一部の著者によって拒否されています。1991年にアレクサンダー・ソイファーによって、グラフのユークリッド次元と呼ばれる別の定義が提案されました。 ^[4]それ以前の1980年に、ポール・エルデシュとミクローシュ・シモノビッツは、忠実次元という名前でそれをすでに提案していました。^[5]この定義によると、最小n表現とは、グラフの2つの頂点が、それらの表現の距離が1である 場合に限り接続されているような表現です。

反対側の図は、中心の頂点と 6 つの周辺頂点を持ち、スポークが 1 つ削除された車輪グラフの場合の、これらの定義の違いを示しています。平面での表現では、距離 1 の 2 つの頂点が許可されますが、それらは接続されていません。

この次元は と書きます。これは上で定義された次元より小さくなることはありません。 ${\displaystyle \operatorname {編集} G}$

${\displaystyle \dim G\leq \operatorname {編集} G}$

Paul Erdős と Miklós Simonovits は 1980 年に次の結果を証明しました: ^[5]

与えられたグラフの次元またはユークリッド次元が最大で与えられた値であるかどうかをテストすることはNP困難であり、実数の存在理論ではより具体的には完全である。次元またはユークリッド次元が2であるかどうかをテストすることさえ困難な問題である。^[6]