ロバートソン・シーモアの定理

グラフ理論において、ロバートソン・シーモアの定理（グラフマイナー定理とも呼ばれる^{[ 1 ]}）は、グラフマイナー関係によって部分的に順序付けられた無向グラフが、適切な準順序を形成することを述べている^{[ 2 ]}。言い換えれば、マイナーを取ることによって閉じられるグラフの族はすべて、有限個の禁止マイナーの集合によって定義できる。これは、ワグナーの定理が平面グラフを完全グラフを持たないグラフとして特徴づけるのと同様である。${\displaystyle K_{5}}$または完全二部グラフ${\displaystyle K_{3,3}}$未成年者として。

ロバートソン・シーモアの定理は、1983年から2004年にかけて500ページを超える一連の20本の論文でそれを証明した数学者のニール・ロバートソンとポール・D・シーモアにちなんで名付けられました。 ^{[ 3 ]}証明される前は、この定理の記述はドイツの数学者クラウス・ワーグナーにちなんでワーグナー予想として知られていましたが、ワーグナー自身はそれを予想したことはないと述べています。^{[ 4 ]}

木に関するより弱い結果は、1937年にアンドリュー・ヴァゾニーによって予想され、1960年にジョセフ・クラスカルとS・タルコフスキーによって独立に証明されたクラスカルの木の定理によって示唆される。^{[ 5 ]}

無向グラフのマイナー${\displaystyle G}$は、から得られるグラフです。${\displaystyle G}$ゼロ回以上のエッジの収縮のシーケンスによって${\displaystyle G}$エッジと頂点の削除${\displaystyle G}$マイナー関係は、すべての異なる有限無向グラフの集合上に部分順序を形成します。これは、部分順序の 3 つの公理、すなわち、反射的(すべてのグラフはそれ自身のマイナーである)、推移的(マイナーのマイナーはそれ自身のマイナーである) を満たすためです。${\displaystyle G}$それ自体はマイナーである${\displaystyle G}$）、および反対称（2 つのグラフが${\displaystyle G}$そして${\displaystyle G}$互いにマイナーである場合、それらは同型でなければなりません。しかし、同型であるグラフがそれでも別個のオブジェクトとみなされる場合、グラフ上のマイナー順序は前順序を形成します。これは反射的かつ推移的ですが、必ずしも反対称ではありません。^{[ 6 ]}

前順序は、無限下降鎖も無限反鎖も含まない場合、良好準順序を形成すると言われます。^{[ 7 ]}例えば、非負整数の通常の順序は良好準順序ですが、すべての整数の集合の同じ順序は、無限下降鎖 0、-1、-2、-3... を含むため、良好準順序ではありません。別の例として、割り切れるかどうかで順序付けられた正の整数の集合があり、これには無限下降鎖はありませんが、素数が無限反鎖を構成します。   

ロバートソン・シーモアの定理は、有限無向グラフとグラフマイナーが準整列を形成することを述べている。グラフマイナーの関係には無限下降鎖は含まれない。なぜなら、各縮約または削除によってグラフのエッジと頂点の数（非負の整数）が減少するからである。^{[ 8 ]}この定理の重要な点は、無限反鎖、つまりマイナー順序によって互いに無関係なグラフの無限集合が存在しないことである。$\displaystyle {\mathcal {S}}}$はグラフの集合であり、$\displaystyle {\mathcal {M}}}$は、$\displaystyle {\mathcal {S}}}$最小要素の各同値類に対して 1 つの代表グラフを含む($\displaystyle {\mathcal {S}}}$しかし、適切な未成年者は存在しない$\displaystyle {\mathcal {S}}}$）、 それから$\displaystyle {\mathcal {M}}}$反鎖を形成する。したがって、定理を同値に表現すると、任意の無限集合において、$\displaystyle {\mathcal {S}}}$グラフにおいては、同型でない最小要素は有限個しか存在しないはずである。

この定理の別の同値形式は、任意の無限集合において、$\displaystyle {\mathcal {S}}}$グラフのペアが存在する場合、一方のグラフが他方のグラフのマイナーとなるようなグラフのペアが存在する必要があります。^{[ 8 ]}すべての無限集合には有限個の最小要素があるという記述は、この定理の形式を暗示しています。なぜなら、最小要素が有限個しかない場合、残りの各グラフは、最小要素のいずれかとこのタイプのペアに属していなければならないからです。また、反対方向には、この定理の形式は、無限反鎖は存在しないという記述を暗示しています。なぜなら、無限反鎖は、マイナー関係で関連付けられたペアを含まない集合だからです。

家族$\displaystyle {\mathcal {F}}}$グラフのマイナーを取る操作に関して閉じていると言われるのは、グラフのすべてのマイナーが$\displaystyle {\mathcal {F}}}$また、$\displaystyle {\mathcal {F}}}$。 もし$\displaystyle {\mathcal {F}}}$未成年者で閉鎖的な家族の場合は、$\displaystyle {\mathcal {S}}}$に含まれないグラフのクラスとする$\displaystyle {\mathcal {F}}}$（​​$\displaystyle {\mathcal {F}}}$) ロバートソン・シーモアの定理によれば、有限集合が存在する。$\displaystyle {\mathcal {H}}}$最小限の要素$\displaystyle {\mathcal {S}}}$これらの最小要素は、禁止グラフ特性を形成します。$\displaystyle {\mathcal {F}}}$: グラフは$\displaystyle {\mathcal {F}}}$は、グラフを持たないグラフです。$\displaystyle {\mathcal {H}}}$未成年者として。^{[ 9 ]}メンバーは$\displaystyle {\mathcal {H}}}$家族にとって、除外された未成年者（または禁止された未成年者、または軽微な障害）と呼ばれる。$\displaystyle {\mathcal {F}}}$。

例えば、平面グラフはマイナー操作に関して閉じている。つまり、平面グラフの辺を縮約したり、グラフから辺や頂点を削除したりしても、平面性は損なわれない。したがって、平面グラフは禁止マイナー特性を持ち、この場合はワーグナーの定理によって与えられる。すなわち、集合は$\displaystyle {\mathcal {H}}}$マイナー最小非平面グラフには、ちょうど 2 つのグラフ、完全グラフが含まれます。${\displaystyle K_{5}}$完全二部グラフ${\displaystyle K_{3,3}}$、そして平面グラフは、集合にマイナーを持たないグラフである。${\displaystyle {\mathcal {H}}=\{K_{5},K_{3,3}\}.}$

すべてのマイナー閉グラフ族に禁止マイナー特性が存在することは、ロバートソン・シーモアの定理を述べるのと同等の方法である。なぜなら、すべてのマイナー閉族が$\displaystyle {\mathcal {F}}}$有限集合を持つ$\displaystyle {\mathcal {H}}}$最小限の禁止された未成年者、そして$\displaystyle {\mathcal {S}}}$は任意の無限グラフ集合とする。$\displaystyle {\mathcal {F}}}$から$\displaystyle {\mathcal {S}}}$マイナーを持たないグラフのファミリーとして$\displaystyle {\mathcal {S}}}$。 それから$\displaystyle {\mathcal {F}}}$マイナー閉包であり、有限集合を持つ$\displaystyle {\mathcal {H}}}$最小限の禁止未成年者。$\displaystyle {\mathcal {C}}}$補数である$\displaystyle {\mathcal {F}}}$。$\displaystyle {\mathcal {S}}}$は、$\displaystyle {\mathcal {C}}}$以来$\displaystyle {\mathcal {S}}}$そして$\displaystyle {\mathcal {F}}}$互いに素であり、$\displaystyle {\mathcal {H}}}$最小グラフは$\displaystyle {\mathcal {C}}}$グラフを考えてみましょう${\displaystyle G}$で$\displaystyle {\mathcal {H}}}$。${\displaystyle G}$適切なマイナーを持つことはできません$\displaystyle {\mathcal {S}}}$以来${\displaystyle G}$最小限$\displaystyle {\mathcal {C}}}$。 同時に、${\displaystyle G}$未成年者でなければならない${\displaystyle S}$そうでなければ${\displaystyle G}$要素となるだろう$\displaystyle {\mathcal {F}}}$。 したがって、${\displaystyle G}$は要素です$\displaystyle {\mathcal {S}}}$つまり、$\displaystyle {\mathcal {H}}}$は、$\displaystyle {\mathcal {S}}}$、およびその他すべてのグラフ$\displaystyle {\mathcal {S}}}$グラフの中でマイナーな$\displaystyle {\mathcal {H}}}$、 それで$\displaystyle {\mathcal {H}}}$は最小要素の有限集合である$\displaystyle {\mathcal {S}}}$。

同値性の逆方向を示すために、グラフの任意の集合には最小グラフの有限部分集合が存在すると仮定し、マイナー閉集合を$\displaystyle {\mathcal {F}}}$与えられる。我々は集合を見つけたい$\displaystyle {\mathcal {H}}}$グラフが$\displaystyle {\mathcal {F}}}$マイナーがない場合に限り$\displaystyle {\mathcal {H}}}$。 させて${\displaystyle {\mathcal {E}}}$グラフのマイナーではないグラフを$\displaystyle {\mathcal {F}}}$、そして$\displaystyle {\mathcal {H}}}$最小グラフの有限集合を${\displaystyle {\mathcal {E}}}$。さて、任意のグラフを考えてみましょう。${\displaystyle G}$が与えられると仮定します。${\displaystyle G}$は$\displaystyle {\mathcal {F}}}$。${\displaystyle G}$未成年者を持つことはできません$\displaystyle {\mathcal {H}}}$以来${\displaystyle G}$は$\displaystyle {\mathcal {F}}}$そして$\displaystyle {\mathcal {H}}}$は、${\displaystyle {\mathcal {E}}}$では、${\displaystyle G}$は$\displaystyle {\mathcal {F}}}$。 それから${\displaystyle G}$はどのグラフのマイナーでもありません$\displaystyle {\mathcal {F}}}$、 以来$\displaystyle {\mathcal {F}}}$マイナークローズです。したがって、${\displaystyle G}$は${\displaystyle {\mathcal {E}}}$、 それで${\displaystyle G}$副専攻は$\displaystyle {\mathcal {H}}}$。

以下の有限グラフの集合はマイナー閉集合であり、したがって（ロバートソン・シーモアの定理により）禁止されたマイナー特性を持つ。

• 森林、線形森林（パスグラフの非交和）、擬似森林、およびサボテングラフ。
• 平面グラフ、外平面グラフ、頂点グラフ（平面グラフに単一の頂点を追加して形成される）、トーラスグラフ、および任意の固定された2次元多様体に埋め込むことができるグラフ。^{[ 10 ]}
• ユークリッド3空間にリンクレス埋め込み可能なグラフ、およびユークリッド3空間にノットレス埋め込み可能なグラフ。 ^{[ 10 ]}
• フィードバック頂点集合のサイズが何らかの固定定数で制限されるグラフ。コリン・ド・ヴェルディエールグラフ不変量が何らかの固定定数で制限されるグラフ。ツリー幅、パス幅、またはブランチ幅が何らかの固定定数で制限されるグラフ。

ロバートソン・シーモアの定理が証明される以前から、特定のグラフクラスについては有限の障害集合の例がいくつか知られていました。例えば、すべての森の集合に対する障害はループグラフ（または、単純グラフに限定すれば、3つの頂点を持つサイクル）です。これは、グラフが森であるのは、そのマイナーのいずれもループ（または、それぞれ3つの頂点を持つサイクル）ではない場合に限ることを意味します。パスの集合に対する唯一の障害は、4つの頂点を持つ木であり、そのうちの1つは次数が3です。これらの場合、障害集合は単一の要素を含みますが、一般にはそうではありません。ワグナーの定理は、グラフが平面グラフであるのは、グラフがどちらも持たない場合に限ると述べています。${\displaystyle K_{5}}$または${\displaystyle K_{3,3}}$マイナーとして。言い換えれば、セット${\displaystyle \{K_{5},K_{3,3}\}}$は、すべての平面グラフの集合に対する障害集合であり、実際には唯一の最小障害集合である。同様の定理によれば、${\displaystyle K_{4}}$そして${\displaystyle K_{2,3}}$これらは、外平面グラフの集合に対する禁止マイナーです。

ロバートソン・シーモアの定理はこれらの結果を任意のマイナー閉グラフ族に拡張するものの、どの族に対しても障害集合の明示的な記述を提供しないため、これらの結果の完全な代替とはなり得ない。例えば、トーラスグラフの集合には有限の障害集合があることはわかるが、そのような集合は提供しない。トーラスグラフの禁止マイナーの完全な集合は未だ不明だが、少なくとも17,535個のグラフが含まれている。^{[ 11 ]}

ロバートソン・シーモアの定理は、ロバートソンとシーモアによる証明により、計算複雑性において重要な意味を持つ。各固定グラフに対して、${\displaystyle H}$グラフが​${\displaystyle H}$マイナーとして。このアルゴリズムの実行時間は（チェックするグラフのサイズに対して）3乗ですが、マイナーのサイズに超多項式的に依存する定数係数があります。${\displaystyle H}$実行時間は河原林、小林、リードによって二次関数に改善された。^{[ 12 ]}その結果、すべてのマイナークローズドファミリーについて$\displaystyle {\mathcal {F}}}$グラフが属するかどうかをテストするための多項式時間アルゴリズムがあります。$\displaystyle {\mathcal {F}}}$: 与えられたグラフが${\displaystyle H}$禁止されている未成年者一人につき${\displaystyle H}$障害物セットにおいて$\displaystyle {\mathcal {F}}}$[ ^{13 ]​}

しかし、この方法は特定の有限の障害物集合が機能することを必要とし、定理はそれを提供しません。定理は、そのような有限の障害物集合が存在することを証明し、したがって上記のアルゴリズムにより問題は多項式時間であることを示しています。ただし、このアルゴリズムは、そのような有限の障害物集合が提供されている場合にのみ実際に使用できます。結果として、定理は問題を多項式時間で解くことができることを証明しますが、それを解くための具体的な多項式時間アルゴリズムは提供しません。このような多項式の証明は非構成的です。明示的な多項式時間アルゴリズムを提供せずに問題の多項式性を証明します。^{[ 14 ]}多くの具体的なケースでは、グラフが特定のマイナー閉族に属するかどうかのチェックはより効率的に行うことができます。たとえば、グラフが平面であるかどうかのチェックは線形時間で行うことができます。

グラフ不変量で、各${\displaystyle k}$不変量が最大で${\displaystyle k}$がマイナー閉じている場合、同じ方法が適用されます。たとえば、この結果により、ツリー幅、ブランチ幅、パス幅、頂点被覆、埋め込みの最小種数はすべてこのアプローチに適しており、任意の固定に対して${\displaystyle k}$これらの不変量が最大でも${\displaystyle k}$アルゴリズムの実行時間における指数は、${\displaystyle k}$この性質の問題点は、任意の固定値に対して多項式時間で解けることである。${\displaystyle k}$指数は${\displaystyle k}$は、固定パラメータ扱い可能として知られています。

しかし、この方法は、未知のパラメータを持つ与えられたグラフのパラメータ値を計算するための、単一の固定パラメータ追跡可能なアルゴリズムを直接提供するものではありません。${\displaystyle k}$禁止マイナーの集合を決定するのが難しいため、また、これらの結果に含まれる大きな定数係数によって、非常に非実用的になります。したがって、これらの問題に対する明示的な固定パラメータアルゴリズムの開発は、${\displaystyle k}$は、引き続き重要な研究分野であり続けている。

フリードマン、ロバートソン、シーモア（1987）は、次の定理がペアノ算術よりもはるかに強い様々な形式体系では証明不可能であるが、ZFCよりもはるかに弱い体系では証明可能であるという独立現象を示すことを示した：^{[ 15 ]}

定理：すべての正の整数に対して${\displaystyle n}$整数が存在する${\displaystyle m}$とても大きいので、${\displaystyle G_{1},\dots ,G_{m}}$は有限無向グラフのシーケンスであり、各${\displaystyle G_{i}}$最大サイズ${\displaystyle n+i}$、 それから${\displaystyle G_{j}\leq G_{k}}$一部の人にとって${\displaystyle j\leq k}$。

（ここで、グラフのサイズとは、頂点と辺の総数を指し、≤はマイナー順序を表します。）

フリードマンはこの結果を単純なサブ3次グラフに適用して、急速に成長する関数SSCGを構築した。^{[ 16 ]}

• グラフ構造定理

• Bienstock, Daniel; Langston, Michael A. (1995)、「グラフ小定理のアルゴリズム的含意」（PDF）、Network Models、Handbooks in Operations Research and Management Science、vol.  7、pp. 481–502、doi : 10.1016/S0927-0507(05)80125-2、ISBN  978-0-444-89292-8。
• Diestel, Reinhard ( 2005)、「マイナー、ツリー、およびWQO」、グラフ理論（PDF）（電子版2005年 版）、Springer、pp. 326–367 。
• Fellows, Michael R. ; Langston, Michael A. (1988)、「多項式時間決定可能性を証明するための非構成的ツール」、Journal of the ACM、35 (3): 727–739、doi : 10.1145/44483.44491。
• フリードマン、ハーヴェイ；ロバートソン、ニール；シーモア、ポール（1987）「グラフ小定理のメタ数学」、シンプソン、S.（編）『論理と組み合わせ論』 、現代数学、第 65巻、アメリカ数学会、 229～ 261ページ 。
• フリードマン、ハーベイ (2006)。「[ FOM ] 274：サブキューブグラフ数」。オハイオ州立大学数学科。2024年4月7日にオリジナルからアーカイブ済み。
• 河原林健一、小林祐介、ブルース・リード（2012）「二次時間における互いに素な経路問題」（PDF） , Journal of Combinatorial Theory, Series B , 102 (2): 424–435 , doi : 10.1016/j.jctb.2011.07.004。
• Lovász、László (2005)、「グラフ マイナー理論」、米国数学協会紀要、新シリーズ、43 (1): 75–86、doi : 10.1090/S0273-0979-05-01088-8。
• Myrvold, Wendy ; Woodcock, Jennifer (2018)、「トーラスの障害物の大きな集合とその発見方法」、電子組合せ論ジャーナル、25 (1): P1.16、doi : 10.37236/3797。
• Robertson, Neil ; Seymour, Paul (1983)、「グラフマイナー。I. 森の除外」、Journal of Combinatorial Theory, Series B、35 (1): 39–61、doi : 10.1016/0095-8956(83)90079-5。
• Robertson, Neil ; Seymour, Paul (1995)、「グラフマイナー XIII. 互いに素なパスの問題」、Journal of Combinatorial Theory, Series B、63 (1): 65–110、doi : 10.1006/jctb.1995.1006。
• Robertson, Neil ; Seymour, Paul (2004)、「グラフマイナー XX. ワグナー予想」、Journal of Combinatorial Theory, Series B、92 (2): 325–357、doi : 10.1016/j.jctb.2004.08.001。

• ワイススタイン、エリック・W.、「ロバートソン＝シーモアの定理」、MathWorld