モーザースピンドル

モーザースピンドル
モーザースピンドル
名前の由来	レオ・モーザー、ウィリアム・モーザー
頂点	7
エッジ	11
半径	2
直径	2
胴回り	3
自己同型	8
彩度数	4
色指数	4
プロパティ	平面; 単位距離; ラマングラフ
	グラフとパラメータの表

モーザースピンドル（モーザースピンドル、モーザーグラフとも呼ばれる）は、数学者のレオ・モーザーとその兄弟ウィリアムにちなんで名付けられた、7つの頂点と11の辺を持つ無向グラフである。モーザースピンドルは^、任意のグラフ彩色で4色を必要とする単位距離のグラフであり、その存在は、平面の彩色数が少なくとも4であることを証明するために使用できる。 ^[2]

モーザースピンドルは、ハヨース構造の一例と見ることができるため、ジェルジ・ハヨースにちなんでハヨースグラフとも呼ばれる。^[3]しかし、「ハヨースグラフ」という名前は、六角形に内接する三角形の形をした別のグラフにも適用されている。^[4]

工事

モーザースピンドルは、平面の 7 色化とともに、平面に単位距離グラフとして埋め込まれています。

単位距離グラフとして、モーザースピンドルは 60 度と 120 度の角度を持つ 2 つの菱形によって形成され、菱形の辺と短い対角線は正三角形を形成します。2 つの菱形は平面に配置され、鋭角の頂点の 1 つを共有し、残りの 2 つの鋭角の頂点が互いに単位距離離れるように配置されます。グラフの 11 の辺は、8 つの菱形の辺、菱形の 2 つの短い対角線、および単位距離の鋭角の頂点のペア間の辺です。

モーザースピンドルは、4つの頂点を持つ2つの完全グラフから始まるハヨス構成を使用して、幾何学的埋め込みを参照せずにグラフ理論的に構築することもできます。この構成では、各完全グラフから辺を削除し、削除された辺の2つの端点を両方のクリークが共有する単一の頂点にマージし、削除された辺の残りの2つの端点を接続する新しい辺を追加します。^[5]

モーザースピンドルを構築するもう一つの方法は、ユーティリティグラフK3,3の辺の1つを細分化して形成されたグラフの補グラフとして_構築する方法である。[ 6 ^]

ハドヴィガー・ネルソン問題への応用

ハドヴィガー・ネルソン問題は、ユークリッド平面上の点を、互いに単位距離にある各点のペアに異なる色を割り当てるように色付けするのに必要な色の数を問うものである。つまり、平面上のすべての点が頂点となり、すべての辺が単位距離にある点のペアとなる無限グラフの彩色数を問うものである。^[2]

モーザースピンドルは、グラフの色付けに 4 色を必要とします。モーザースピンドルを構成する 2 つの菱形のうちの 1 つを 3 色で色付けすると、その菱形の 2 つの鋭角頂点は必然的に互いに同じ色になります。しかし、2 つの菱形の共有頂点が、2 つの反対の鋭角頂点と同じ色である場合、これらの 2 つの頂点は互いに同じ色になり、それらを接続する辺の端点が異なる色であるという要件に違反します。この矛盾は、3 色は不可能であるため、少なくとも 4 色が必要であることを示しています。モーザースピンドルの色付けには 4 色で十分であり、これは、たとえばモーザースピンドルの退化が 3 であるという事実から明らかです。

モーザースピンドルが4色を必要とするという別の証明は、ハヨス構成から得られます。モーザースピンドルが形成される完全なグラフは両方とも4色を必要とし、ハヨス構成はこの特性を保持します。^[5]さらに直接的には、モーザースピンドルの各独立集合には最大で2つの頂点があるため、^[7] 7つの頂点すべてをカバーするには少なくとも4つの独立集合が必要です。

モーザースピンドルは平面の無限単位距離グラフのサブグラフであるため、平面のグラフも任意の彩色で少なくとも 4 色を必要とする。ド・ブリュイン・エルデシュ定理(選択公理が真であるという仮定) によれば、平面の彩色数はその有限サブグラフの最大彩色数と同じである。2018 年に 5 彩色単位距離グラフの族が発見されるまで、モーザースピンドルよりも多くの色数を必要とする無限単位距離グラフのサブグラフは見つかっていなかった。しかし、平面の彩色数の最良の上限は 7 であり、モーザースピンドルに必要な色数よりも大幅に多い。^[2]

その他の特性と用途

モーザースピンドルは平面グラフであり、平面上で交差することなく描くことができる。しかし、直線の辺で単位距離の描画となるような描画を形成することはできない。つまり、マッチ棒グラフではない。モーザースピンドルはラマングラフでもあり、平面に埋め込むと最小限の剛性システムを形成する。 ^[8]平面ラマングラフとして、それは尖った擬似三角形分割のグラフであり、つまり、境界のない面が埋め込みの凸包であり、すべての境界のある面が3つの凸頂点のみを持つ擬似三角形であるような方法で平面に埋め込むことができる。^[9]

モーザーグラフの補グラフは三角形のないグラフである。したがって、モーザーグラフの単位距離埋め込みは、すべての3つの点が互いに単位距離にある少なくとも1つのペアを含むように7つの点を平面に配置する問題を解決するために使用できます。^[2]^[10]

モーザースピンドルに任意の辺を追加すると、単位距離グラフとして平面に埋め込むことができないグラフになり、モーザースピンドルからより小さな単位距離グラフへのグラフ準同型は存在しません。モーザースピンドルのこれらの 2 つの特性は、Horvat、Kratochvíl、Pisanski (2011) によって、与えられたグラフが 2 次元の単位距離表現を持つかどうかをテストすることのNP 困難性を示すために使用されました。証明には、モーザースピンドルを還元の中心的な真理設定ガジェットとして使用する3SATからの還元が使用されています。 ^[8]

モーザースピンドルは、ユークリッドラムゼー理論の結果を証明するためにも使用できます。Tが平面内の任意の三角形であり、平面の点が2色の黒と白である場合、Tの黒い変換、または互いに単位距離にある白い点のペアのいずれかが存在します。たとえば、M をモーザースピンドルの単位距離埋め込みとし、M + T をMと Tのミンコフスキー和とします。M + Tに白い単位距離ペアがない場合、 M + T内のモーザースピンドルの3つのコピーのそれぞれは、最大で2つの白い点を持つ必要があります。これは、各コピーの白い点が独立したセットを形成する必要があり、モーザースピンドルの最大の独立セットのサイズが2であるためです。したがって、モーザースピンドルの7つの頂点のうち、M + Tに白いコピーを持つ頂点は最大で6つであるため、7つの頂点のうちの1つで、すべてのコピーが黒である頂点が存在する必要があります。しかし、この頂点の3つのコピーは、Tの変換を形成します。^[7]

参照

ゴロムグラフ

参考文献

^ モーザー、L. ; モーザー、W. (1961)、「問題 10 の解答」、Can. Math. Bull.、4 : 187–189、doi : 10.1017/S0008439500025753、S2CID 246244722。
^ abcd Soifer, Alexander (2008) 『数学的ぬり絵の本：色彩の数学とその創作者たちの多彩な人生』、ニューヨーク：Springer、pp. 14–15、ISBN 978-0-387-74640-1。
^ Bondy, JA; Murty, USR (2008)、「グラフ理論」、Graduate Texts in Mathematics、vol. 244、Springer、p. 358、doi :10.1007/978-1-84628-970-5、ISBN 978-1-84628-969-9。
^ Berge, C. (1989)、「グラフの部分q色付けに対するミニマックス関係」、離散数学、74 (1–2): 3–14、doi : 10.1016/0012-365X(89)90193-3、MR 0989117。
^ ab Hajós、G. (1961)、「Über eine Konstruktion nicht $n$ -färbbarer Graphen」、Wiss. Z. マーティン・ルター大学ハレ・ヴィッテンベルクの数学-自然。霊河、10 : 116–117。
^ Gervacio, Severino V.; Lim, Yvette F.; Maehara, Hiroshi (2008)、「平面単位距離グラフと平面単位距離補数」、離散数学、308 (10): 1973–1984、doi : 10.1016/j.disc.2007.04.050、MR 2394465。
^ ab Burkert, Jeffrey; Johnson, Peter (2011)、「Szlam の補題: 1973 年のユークリッドラムゼー問題の突然変異体、多数の応用」、ラムゼー理論、Progr. Math.、vol. 285、Birkhäuser/Springer、ニューヨーク、pp. 97–113、doi :10.1007/978-0-8176-8092-3_6、MR 2759046Soifer（2008）問題40.26、p.496も参照。
^ ab Horvat, Boris; Kratochvíl, Jan; Pisanski, Tomaž (2011)、「グラフの縮退単位距離表現の計算複雑性について」、組み合わせアルゴリズム: 第 21 回国際ワークショップ、IWOCA 2010、ロンドン、英国、2010 年 7 月 26 ～ 28 日、改訂選択論文、Lecture Notes in Computer Science、vol. 6460、pp. 274 ～ 285、arXiv : 1001.0886、Bibcode :2011LNCS.6460..274H、doi :10.1007/978-3-642-19222-7_28、ISBN 978-3-642-19221-0、S2CID 17585590。
^ Haas, Ruth ; Orden, David; Rote, Günter; Santos, Francisco ; Servatius, Brigitte ; Servatius, Herman; Souvaine, Diane ; Streinu, Ileana ; Whiteley, Walter (2005)、「平面最小剛性グラフと擬似三角測量」、計算幾何学理論と応用、31 (1–2): 31–61、arXiv : math/0307347、doi :10.1016/j.comgeo.2004.07.003、MR 2131802。
^ ウィンクラー、ピーター（2011年11月）、「パズル：平面上の点間の距離」、Communications of the ACM、54（11）：120、doi：10.1145 / 2018396.2018422、S2CID 195633418. ソリューション、第12号、2011年12月、doi :10.1145/2043174.2043200。

外部リンク

Weisstein、Eric W.「Moser Spindle」。MathWorld。

[1] モーザー、L. ; モーザー、W. (1961)、「問題 10 の解答」、Can. Math. Bull.、4 : 187–189、doi : 10.1017/S0008439500025753、S2CID 246244722。

[soifer-2] Soifer, Alexander (2008) 『数学的ぬり絵の本：色彩の数学とその創作者たちの多彩な人生』、ニューヨーク：Springer、pp. 14–15、ISBN 978-0-387-74640-1。

[3] Bondy, JA; Murty, USR (2008)、「グラフ理論」、Graduate Texts in Mathematics、vol. 244、Springer、p. 358、doi :10.1007/978-1-84628-970-5、ISBN 978-1-84628-969-9。

[4] Berge, C. (1989)、「グラフの部分q色付けに対するミニマックス関係」、離散数学、74 (1–2): 3–14、doi : 10.1016/0012-365X(89)90193-3、MR 0989117。

[hajos-5] Hajós、G. (1961)、「Über eine Konstruktion nicht $n$ -färbbarer Graphen」、Wiss. Z. マーティン・ルター大学ハレ・ヴィッテンベルクの数学-自然。霊河、10 : 116–117。

[6] Gervacio, Severino V.; Lim, Yvette F.; Maehara, Hiroshi (2008)、「平面単位距離グラフと平面単位距離補数」、離散数学、308 (10): 1973–1984、doi : 10.1016/j.disc.2007.04.050、MR 2394465。

[bj11-7] Burkert, Jeffrey; Johnson, Peter (2011)、「Szlam の補題: 1973 年のユークリッドラムゼー問題の突然変異体、多数の応用」、ラムゼー理論、Progr. Math.、vol. 285、Birkhäuser/Springer、ニューヨーク、pp. 97–113、doi :10.1007/978-0-8176-8092-3_6、MR 2759046Soifer（2008）問題40.26、p.496も参照。

[hkp10-8] Horvat, Boris; Kratochvíl, Jan; Pisanski, Tomaž (2011)、「グラフの縮退単位距離表現の計算複雑性について」、組み合わせアルゴリズム: 第 21 回国際ワークショップ、IWOCA 2010、ロンドン、英国、2010 年 7 月 26 ～ 28 日、改訂選択論文、Lecture Notes in Computer Science、vol. 6460、pp. 274 ～ 285、arXiv : 1001.0886、Bibcode :2011LNCS.6460..274H、doi :10.1007/978-3-642-19222-7_28、ISBN 978-3-642-19221-0、S2CID 17585590。

[9] Haas, Ruth ; Orden, David; Rote, Günter; Santos, Francisco ; Servatius, Brigitte ; Servatius, Herman; Souvaine, Diane ; Streinu, Ileana ; Whiteley, Walter (2005)、「平面最小剛性グラフと擬似三角測量」、計算幾何学理論と応用、31 (1–2): 31–61、arXiv : math/0307347、doi :10.1016/j.comgeo.2004.07.003、MR 2131802。

[winkler-10] ウィンクラー、ピーター（2011年11月）、「パズル：平面上の点間の距離」、Communications of the ACM、54（11）：120、doi：10.1145 / 2018396.2018422、S2CID 195633418. ソリューション、第12号、2011年12月、doi :10.1145/2043174.2043200。