Loading article…
幾何学的グラフ理論において、ヒューゴ・ハドウィガーとエドワード・ネルソンにちなんで名付けられたハドウィガー・ネルソン問題は、互いに距離1にある2つの点が同じ色にならないように平面を彩色するために必要な最小色の数を求める問題である。答えは不明であるが、5、6、7のいずれかに絞り込まれている。正しい値は集合論の公理の選択によって異なる可能性がある。[ 1 ]
この問題は、グラフ理論の観点から次のように表現できます。Gを平面の単位距離グラフとします。これは、平面のすべての点を頂点とし、2 つの頂点間の距離が 1 の場合に限り、 2 つの頂点間に辺が存在する無限グラフです。ハドウィガー・ネルソン問題は、 Gの彩色数を求めることです。したがって、この問題はしばしば「平面の彩色数を求める」と呼ばれます。de BruijnとErdős (1951)の結果であるde Bruijn–Erdős の定理により、この問題は (選択公理の仮定の下で) 有限単位距離グラフの最大の彩色数を求める問題と同等です。
Jensen & Toft (1995)によると、この問題は 1950 年に Nelson によって初めて定式化され、1960 年に Gardnerによって初めて発表された。Hadwiger (1945)はそれ以前に、5 つの合同な閉集合による平面の任意の被覆には、いずれかの集合に単位距離が含まれることを示す関連結果を発表しており、また、後の論文( Hadwiger 1961 )でこの問題に言及している。Soifer (2008) はこの問題とその歴史について詳しく論じている。
この問題の応用例の一つは、単位距離を保存するユークリッド平面（または任意の高次元空間）からそれ自身への写像は、すべての距離を保存する等長写像でなければならないというベックマン・クォールズの定理と関連付けられる。[ 2 ]これらの空間の有限彩色を用いて、単位距離を保存するが等長写像ではない、より高次元の空間への写像を構築することができる。例えば、ユークリッド平面を7色で彩色し、距離が1の2点が同じ色にならないようにして、その色によって点を単位長の辺を持つ6次元正単体の7つの頂点に写像することで、6次元空間に写像することができる。これにより、単位距離にある任意の2点が異なる色に写像され、そこから互いに単位距離にある単体の異なる頂点に写像される。しかし、他のすべての距離は0または1に写像されるため、等長写像ではない。平面を彩色するために必要な色の数を7色からより少ない数に減らすことができれば、この構成におけるターゲット空間の次元にも同じ削減が適用されるだろう。[ 3 ]
平面の彩色数が少なくとも4でなければならないという事実は、彩色数が4の7頂点単位距離グラフの存在から導かれる。このグラフは、1961年にウィリアム・モーザーとレオ・モーザー兄弟によって発見されたことから、モーザー紡錘と名付けられている。このグラフは、共通の頂点xで結合された2つの単位正三角形から構成される。これらの三角形はそれぞれ、別の辺で別の正三角形と結合されている。これらの結合された三角形の頂点yとzは、互いに単位距離にある。平面を3色で着色できるとすると、三角形内の着色によってyとzの両方がxと同じ色になるが、yとzは互いに単位距離にあるため、平面の単位距離グラフを適切に着色することはできない。したがって、このグラフとそれを含む平面を着色するには、少なくとも4色が必要となる。 10個の頂点を持つ4色単位距離グラフであるゴロンブグラフという別の下限が、ほぼ同時期にソロモン・W・ゴロンブによって発見された。[ 4 ]
下限は2018年に5に引き上げられた。コンピュータ科学者で生物老年学者のオーブリー・デ・グレイが、1581個の頂点を持つ4色で彩色できない単位距離グラフを発見した。証明はコンピュータ支援で行われた。[ 5 ]数学者のギル・カライとコンピュータ科学者のスコット・アーロンソンは、デ・グレイの発見についての議論を投稿し、アーロンソンはSATソルバーを使用してデ・グレイの結果の独立した検証を報告した。カライは、ジョーダン・エレンバーグとノーム・エルキースによる追加の投稿へのリンクを貼り、エルキースと（別々に）デ・グレイは、デ・グレイの構成よりも頂点数が少ない4色で彩色できない単位距離グラフを見つけるためのPolymathプロジェクトを提案した。 [ 6 ] 2021年現在、彩色数5の最小の既知の単位距離グラフは509個の頂点を持つ。[ 7 ]ポリマスプロジェクトのページ、ポリマス（2018）には、さらなる研究、メディアの引用、検証データが含まれています。
彩色数の上限が7であることは、直径が1よりわずかに小さい正六角形による平面のテセレーションが存在し、それらに7色を繰り返し割り当てることで平面の7彩色を形成できることから導かれる。ソイファー（2008）によれば、この上限はジョン・R・イズベルによって最初に発見された。
この問題は高次元にも拡張できる。例えば、平面上のバージョンと同様に、3次元空間の彩色数は不明だが、少なくとも6、最大で15であることが示されている。[ 8 ]
問題のn次元の場合、 n次元立方体のタイル張りから得られる必要な彩色数の簡単な上限は次のようになります。単体からの下限は。 のために下限値これは、モーザー紡錘の一般化によって実現可能であり、2 つのオブジェクト (それぞれ 2 つの単体がファセット上で接着されている) のペアが、片側で点によって、もう片側で線によって結合されている。指数下限は、1981 年に Frankl と Wilson によって証明された。[ 9 ]
また、各色の点の集合が特定のタイプの集合に制限される平面の彩色も考えられます。[ 10 ]このような制限により、特定の彩色が許容されると見なされなくなるため、必要な色の数が増える可能性があります。たとえば、平面の彩色がジョルダン曲線で囲まれた領域で構成されている場合、少なくとも6色が必要になります。[ 11 ]
{{citation}}: CS1メンテナンス: DOIは2025年7月現在非アクティブです（リンク）