モーザースピンドル
4色を必要とする無向単位距離グラフ

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

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

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

工事

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

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

モーザースピンドルのハヨス構造

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

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

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

ハドヴィガー・ネルソン問題は、ユークリッド平面上の点を、互いに単位距離にある2点の組にそれぞれ異なる色を割り当てるように彩色するために必要な色の数を問う問題である。つまり、平面上のすべての点を頂点とし、すべての辺を単位距離にある2点の組とする無限グラフの彩色数を問う問題である。[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]

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

モーザースピンドルに任意の辺を追加すると、単位距離グラフとして平面に埋め込むことができないグラフが生成され、モーザースピンドルからより小さな単位距離グラフへのグラフ準同型は存在しない。モーザースピンドルのこれらの2つの性質は、ホルバート、クラトチヴィル、ピサンスキー (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]

参照

参考文献

  1. ^ Moser, L. ; Moser, W. (1961)、「問題10の解答」、Can. Math. Bull.、4 : 187–189、doi : 10.1017/S0008439500025753、S2CID  246244722。
  2. ^ abcd Soifer, Alexander (2008), The Mathematical Coloring Book: Mathematics of Coloring and the Colouring Life of its Creators , New York: Springer, pp.  14– 15, ISBN 978-0-387-74640-1。
  3. ^ Bondy, JA; Murty, USR (2008),グラフ理論, 大学院数学テキスト, 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。
  5. ^ ab 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。
  7. ^ ab Burkert, Jeffrey; Johnson, Peter (2011), 「Szlamの補題：1973年のユークリッドラムゼー問題の突然変異体とその応用例」Ramsey theory , Progr. Math., vol. 285, Birkhäuser/Springer, New York, pp.  97– 113, doi :10.1007/978-0-8176-8092-3_6, MR  2759046Soifer（2008）問題40.26、p.496も参照。
  8. ^ ab Horvat, Boris; Kratochvíl, Jan; Pisanski, Tomaž (2011)、「グラフの縮退単位距離表現の計算複雑性について」、Combinatorial Algorithms: 21st International Workshop, 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)「平面最小剛性グラフと擬似三角測量」, Computational Geometry Theory and Applications , 31 ( 1– 2): 31– 61, arXiv : math/0307347 , doi :10.1016/j.comgeo.2004.07.003, MR  2131802。
  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。
「https://en.wikipedia.org/w/index.php?title=Moser_spindle&oldid=1300654472」より取得