平面カバー – 日本語百科事典辞書

Planar_cover
グラフ理論では、有限グラフGの平面カバーは、それ自体が平面グラフであるGの有限カバーグラフです。射影平面に埋め込むことができるすべてのグラフには平面カバーが根上誠也の未解決の予想では、これらが平面カバーを持つ唯一のグラフであると述べられています。
グラフC は、グラフHの平面カバーです。カバーマップは頂点の色で示されます。
平面カバーの存在は、マイナーが閉じたグラフのプロパティであるため、有限数の禁止マイナーによって特徴付けることができますが、禁止マイナーの正確なセットは不明です。同じ理由で、特定のグラフに平面カバーがあるかどうかをテストするための多項式時間アルゴリズムが存在しますが、このアルゴリズムの明示的な説明は知られ

コンテンツ
1 意味
2 例
3 表紙保存作業
4 根上の推測
5 ノート
6 参考文献
6.1 根上予想に関する二次資料 6.2 平面カバーに関する一次情報源 6.3 裏付けとなる文献

意味
あるグラフCから別のグラフHへのカバーマップは、 Cの頂点からHの頂点までの関数fによって記述できます。この関数は、 Cの頂点vごとに、 vの近傍とfの近傍の間の全単射を与えます。( v )。 H が接続されたグラフの場合、 Hの各頂点はC内に同じ数のプリイメージを持たなければなりません。この数はマップのプライと呼ばれ、 CはGのカバーグラフと呼ばれます。CとHが両方とも有限で、C が平面グラフである場合、CはHの平面カバーと呼ばれます。

例

十二面体の反対側の頂点のペアを特定すると、ピーターセングラフのカバーマップが得られます。
十二面体のグラフには、各頂点を対蹠頂点にマッピングする対称性が対蹠的な頂点のペアとその隣接関係は、それ自体をグラフ(ピーターセングラフ)として見ることができます。十二面体は、この非平面グラフの平面カバーを形成します。この例が示すように、平面カバーを持つすべてのグラフ自体が平面であるわけではありません。ただし、平面グラフが非平面グラフをカバーする場合、層は偶数でなければなりません。

１２角柱は、六角柱の２重カバー、立方体３０の３重カバー、三角柱の４重カバーを形成することができる。
k角柱のグラフは2 k個の頂点を持ち、2 つのk角面とk 個の四角形面を持つ平面です。k = ab、a ≥ 2 およびb ≥ 3の場合、 b正プリズムへのaプライカバーマップがあり、kプリズムの 2 つの頂点がbプリズムの同じ頂点にマップされます。両方が同じk角面に属し、一方から他方までの距離が bの倍数である場合。例えば、１２角柱は、６角柱の２層カバー、立方体３層のカバー、三角柱４層のカバーを形成することができる。これらの例は、グラフが多くの異なる平面カバーを持ち、他の多くのグラフの平面カバーになる可能性があることを示しています。さらに、彼らは、平面カバーの層が任意に大きくてもよいことを示している。プリズムを含むカバーはこれらだけではありません。たとえば、六角プリズムは、対蹠的な頂点ペアを識別することによって、非平面グラフであるユーティリティグラフK 3，3をカバーすることもできます。

表紙保存作業
グラフHに平面カバーがある場合、Hのすべてのマイナーグラフも同様です。 HのマイナーG は、Hからエッジと頂点を削除し、Hのエッジを縮小することによって形成できます。カバーグラフC も同じ方法で変換できます。Hの削除されたエッジまたは頂点ごとにC のプリイメージを削除し、 Hの縮小されたエッジまたは頂点ごとにCのプリイメージを縮小します。これらの操作をCに適用した結果は、GをカバーするCのマイナーです。平面グラフのすべてのマイナーはそれ自体平面であるため、これによりマイナーGの平面カバーが得られます。
平面カバーのあるグラフはマイナーを取る操作の下で閉じられるため、ロバートソン・シーモアの定理から、それらは禁止されたマイナーの有限セットによって特徴付けられる可能性があることがわかります。グラフに平面カバーがない場合、グラフはこのプロパティに対して禁止されたマイナーですが、すべてのマイナーには平面カバーがこの特徴付けは、禁止されたマイナーをそれぞれ検索し、この検索でいずれも見つからなかった場合にのみ平面カバーが存在することを返すことにより、平面カバーの存在をテストする多項式時間アルゴリズムの存在を証明するために使用できます。ただし、このプロパティの禁止された未成年者の正確なセットは不明であるため、この存在証明は非建設的であり、禁止された未成年者のセットまたはそれらに基づくアルゴリズムの明示的な説明にはつながりません。
平面カバーの存在を保存するもう 1 つのグラフ操作はY-Δ 変換です。これは、グラフHの 3 次の頂点を、その 3 つの近傍を接続する三角形で置き換えます。ただし、この変換の逆である Δ-Y 変換では、必ずしも平面カバーが保存されるわけではありません。
さらに、カバーを持つ 2 つのグラフの素結合にもカバーがあり、カバーするグラフの素結合として形成されます。2 つのカバーが互いに同じ層を持っている場合、これはそれらの結合の層でも

根上の推測
数学の未解決問題:
平面カバーを持つ接続されたグラフはすべて、射影平面への埋め込みを持っていますか?(数学にはさらに未解決の問題があります)
グラフH が射影面への埋め込みを持っている場合、必然的に、球である射影面の方向付け可能な二重カバー内のHのプリイメージによって与えられる平面カバーを持ちます。逆に、Negami (1986) は、接続されたグラフH が2 層の平面カバーを持つ場合、 H は射影平面への埋め込みを持たなければならないことを証明しました。ここでは、 Hが接続されているという仮定が必要です。射影平面グラフの素結合自体は射影平面ではない可能性がありますが、依然として平面カバー、つまり方向付け可能な二重カバーの素結合を持つことになるからです。
グラフHの通常のカバーは、そのカバーグラフの対称性のグループから得られるものです。H の各頂点のプリイメージはグループの軌道です。Negami (1988) は、平面の規則的なカバーを持つすべての接続されたグラフを射影平面に埋め込むことができることを証明しました。これら 2 つの結果に基づいて、彼は実際には平面カバーを持つすべての接続されたグラフは射影的であると推測しました。 2013 年の時点でも、この推測は未解決のままです。これは、平面カバーが存在する場合、その最小層は 1 または 2 でなければならないと再定式化できるため、根上の「1-2-∞ 予想」としても知られています。

K 1，2，2，2、根上の予想に対する唯一可能な最小の反例
平面カバーのあるグラフと同様に、射影平面埋め込みのあるグラフは、禁止されたマイナーによって特徴付けることができます。この場合、禁止されている未成年者の正確なセットがわかっています。そのうちの 35 人がいます。これらのうち 32 個のグラフは接続されており、これら 32 個のグラフのうちの 1 つは、接続された非射影平面グラフのマイナーとして必ず表示されます。根上が推測を行って以来、これら 32 の禁止マイナーのうち 31 は平面カバーを持たないか、Y-Δ 変換によってこのリストのより単純なグラフに削減できることが証明されました。これがまだ行われていない残りの 1 つのグラフはK 1，2，2，2です。これは、4 次元の八面体ピラミッドの骨格を形成する7 頂点の頂点グラフです。K 1，2，2，2に平面カバーがないことが示されれば、予想の証明が完了します。一方、予想が偽の場合、K 1，2，2，2は必然的にその最小の反例になります。
Michael Fellowsによる関連する推測は、現在解決されていますが、平面エミュレータ(グラフの近傍を全射的ではなく全射的にマッピングする平面カバーの一般化) に関するものです。平面エミュレータを使用したグラフは、平面カバーを使用したグラフと同様、マイナーおよび Y-Δ 変換の下で閉じられます。 1988 年に、根上とは別に、フェローズは、平面エミュレータを使用したグラフはまさに射影平面に埋め込むことができるグラフであると推測しました。この予想は、通常の平面カバーに関する Negami (1988)の結果と同様の結果により、基礎となるカバーグラフの自己同型性から得られる通常のエミュレータに対して当てはまります。しかし、射影平面グラフの 32 個の接続された禁止マイナーのうちのいくつかは平面エミュレーターを持っていることが判明しました。したがって、フェローズの推測は誤りである。平面エミュレータの存在を示す禁止された未成年者の完全なセットを見つけることは、未解決の問題のままです。

ノート
^ フリンニニー（2010)、p. 1
^ Hliněný （2010)、提案 1、p. 2
^ Hliněný （2010)、定義、p. 2
^ Inkmann & Thomas （2011) : 「この構造は図 1 に示されており、十二面体がピーターセングラフの平面二重カバーであることが示されています。」
^ 大執事とリヒター (1990) ; 根上（2003)。
^ ゼリンカ (1982)
^ ロバートソン＆シーモア（2004)
^ ロバートソン＆シーモア (1995)
^ フェローズ＆ラングストン (1988) ; フェローズとコブリッツ (1992)。k倍平面カバーの存在をアルゴリズム的にテストする非構成性は、フェローズとコブリッツによって例として明示的に示されています。
^ 根上 (1986) ; Hliněný （2010)、定理 2、p. 2
^ たとえば、2 つのKuratowski グラフは射影平面ですが、それらの 2 つの結合は射影平面ではありません ( Archdeacon 1981 )。
^ 根上 (1988) ; Hliněný （2010)、定理 3、p. 3
^ 根上 (1988) ; Hliněný （2010)、推測 4、p. 4
^ チマーニら。（2013)
^ フネケ (1993)
^ フリンニニー（2010)、p. 4; 禁止された射影平面マイナーのリストはArchdeacon (1981)からのものです。Negami (1988) は代わりに、 Glover， Huneke & Wang (1979)によって与えられた 103 の既約非射影平面グラフに対する対応する観察を述べました。
^ 根上 (1988) ; フネケ (1993) ; フリニニー (1998) ; 大執事（2002) ; フリニニー（2010)、4–6 ページ
^ フリンニニー（2010)、6–9 ページ
^ フェローズ (1985) ; 北久保 (1991) ; Hliněný （2010)、定義、p. 9
^ Hliněný （2010)、提案 13、p. 9. Hliněný はこれはフェローズの功績であり、その証明は自明ではないと書いている。
^ Hliněný （2010)、推測 14、p. 9
^ 北久保 (1991)。
^ Hliněný （2010)、9–10 ページ。Rieck & 山下（2010) ; チマーニら。（2013)
^ フリンニニー（2010)、p. 10

参考文献

根上予想に関する二次資料
Hliněný、Petr （2010)、「20 years of Negami’s planar cover conjecture」 (PDF)、Graphs and Combinatorics、26 (4): 525–536、doi : 10.1007/s00373-010-0934-9、MR 2669457、S2CID 121645。注記のページ番号はプレプリント版を指します。
Huneke， John Philip (1993)、「位相グラフ理論における予想」、グラフ構造理論 (シアトル、ワシントン州、1991)、現代数学、vol. 147、プロビデンス、RI: アメリカ数学協会、pp. 387–389、doi : 10.1090/conm/147/01186、MR 1224718。

平面カバーに関する一次情報源
Archdeacon、Dan （2002)、「平面カバーのない 2 つのグラフ」、Journal of Graph Theory、41 (4): 318–326、doi : 10.1002/jgt.10075、MR 1936947。
ダン大執事; Richter、R. Bruce (1990)、「平面カバーのパリティについて」、Journal of Graph Theory、14 (2): 199–204、doi : 10.1002/jgt.3190140208、MR 1053603。
チマーニ、マルクス。デルカ、マーティン。フリニニー、ペトル。Klusáček、Matěj（2013）、「平面排出可能なグラフを特徴付ける方法」、Advances in Applied Mathematics、50（1）：46–68、Arxiv：1107.0176、doi：10.1016/j.aam.2012.06.004、MR 29963838383。
Hliněný、Petr (1998)、「K 4，4 − e has no finite planar cover」、Journal of Graph Theory、27 (1): 51–60、doi : 10.1002/(SICI)1097-0118(199801)27: 1<51::AID-JGT8>3.3.CO;2-S、MR 1487786。
インクマン、トルステン。Thomas、Robin （2011)、「偶数分岐幅の最小平面グラフ」、組み合わせ論、確率とコンピューティング、20 (1): 73–82、arXiv : 1007.0373、doi : 10.1017/S0963548310000283、MR 2745678、S2C ID 9093660。
北久保茂 (1991)、「グラフの平面分岐カバー」、横浜数学ジャーナル、38 (2): 113–120、MR 1105068。
根上誠也 (1986)、「グラフの射影平面埋め込みの列挙」、離散数学、62 (3): 299–306、doi : 10.1016/0012-365X(86)90217-7、MR 0866945。
根上誠也 (1988)、「球状属数と実質的に平面のグラフ」、離散数学、70 (2): 159–168、doi : 10.1016/0012-365X(88)90090-8、MR 0949775。
根上誠也（2003)、「グラフの複合平面カバーリング」、離散数学、268 (1–3): 207–216、doi : 10.1016/S0012-365X(02)00689-1、MR 1983279。
リエック、ヨアヴ。山下泰（2010)、「 K 4，5 − 4 K 2およびK 1，2，2，2の有限平面エミュレータとフェローズ予想」、European Journal of Combinatorics、31 (3): 903–907、arXiv : 0812.3700、土井: 10.1016/j.ejc.2009.06.003、MR 2587038、S2CID 36777608。

裏付けとなる文献
Archdeacon、Dan (1981)、「射影平面の Kuratowski 定理」、Journal of Graph Theory、5 (3): 243–246、doi : 10.1002/jgt.3190050305、MR 0625065
フェロー、マイケル R. (1985)、グラフ内のグラフのエンコード、博士号。論文、大学カリフォルニア、サンディエゴの。
フェロー、マイケル R. ; Koblitz、Neal (1992)、「自己目撃多項式時間複雑性と素因数分解」、Designs、Codes and Cryptography、2 (3): 231–235、doi : 10.1007/BF00141967、MR 1181730、S2CID 3976355。
フェロー、マイケル R. ; Langston， Michael A. (1988)、「多項式時間決定可能性を証明するための非建設的ツール」、Journal of the ACM、35 (3): 727–739、doi : 10.1145/44483.44491、S2CID 16587284。
ヘンリー・H・グローバー; ジョン・P・フネケ；Wang， Chin San (1979)、「射影平面に対して既約な 103 グラフ」、Journal of Combinatorial Theory、シリーズ B、27 (3): 332–370、doi : 10.1016/0095-8956(79)90022-4、MR 0554298。
ニール・ロバートソン; Seymour， Paul (1995)、「グラフマイナー。XIII. 素のパスの問題」、Journal of Combinatorial Theory、シリーズ B、63 (1): 65–110、doi : 10.1006/jctb.1995.1006。
ニール・ロバートソン; Seymour， Paul （2004)、「グラフマイナー。XX. ワグナー予想」、Journal of Combinatorial Theory、シリーズ B、92 (2): 325–357、doi : 10.1016/j.jctb.2004.08.001。
Zelinka、Bohdan (1982)、「グラフの二重カバーについて」、Mathematica Slovaca、32 (1): 49–54、MR 0648219。”