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

グラフ理論において、ロバートソン・シーモア定理（グラフマイナー定理^[1]とも呼ばれる）は、グラフマイナー関係によって部分的に順序付けられた無向グラフが、よく準順序付けされたグラフを形成すると述べています。^{[2]同様に、マイナーに関して閉じているグラフのすべての族は、}禁制マイナーの有限集合によって定義できます。これは、ワグナーの定理が平面グラフを、マイナーとして完全グラフK ₅または完全二部グラフK _{3,3 を}持たないグラフとして特徴付けるのと同じです。

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

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

無向グラフGのマイナーとは、Gの辺の0 個以上の縮約とGの辺および頂点の削除のシーケンスによってGから得られるグラフのことです。マイナー関係は、すべての異なる有限無向グラフの集合上で半順序を形成します。これは、3 つの半順序公理に従うためです。マイナー関係は、反射的(すべてのグラフはそれ自身のマイナーである)、推移的( Gのマイナーのマイナーはそれ自体がGのマイナーである)、反対称的(2 つのグラフGとHが互いのマイナーである場合、それらは同型でなければならない) です。ただし、同型であるグラフが異なるオブジェクトと見なせる場合は、グラフ上のマイナー順序は、反射的かつ推移的であるが必ずしも反対称的ではない関係である前順序を形成します。 ^[6]

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

ロバートソン・シーモア定理は、有限の無向グラフとグラフマイナーが準整列を形成することを述べています。グラフマイナー関係には無限降順チェーンは含まれません。これは、各縮小または削除によってグラフの辺と頂点の数 (非負の整数) が減少するためです。^[8]この定理の重要な部分は、マイナー順序によって互いに無関係なグラフの無限集合である無限アンチチェーンが存在しないことです。Sがグラフの集合であり、M がSのサブセットで、最小要素の同値類( Sに属するが、適切なマイナーがSに属していないグラフ) ごとに 1 つの代表グラフを含む場合、M はアンチチェーンを形成します。したがって、この定理を同等に述べる方法は、任意の無限グラフ集合Sには、非同型最小要素が有限個しか存在しないという ことです。

この定理の別の同等の形式は、任意のグラフの無限集合Sには、一方が他方のマイナーであるグラフのペアが必ず存在するというものです。^[8]すべての無限集合には有限個の最小要素があるという主張は、この形式の定理を暗示しています。なぜなら、有限個の最小要素しかない場合、残りの各グラフは、最小要素のいずれかとこのタイプのペアに属している必要があるからです。また、逆の方向では、この形式の定理は、無限アンチチェーンは存在できないという主張を暗示しています。なぜなら、無限アンチチェーンは、マイナー関係で関連付けられたペアを含まない集合だからです。

グラフの族Fは、 F内のグラフのすべてのマイナーがFにも属する場合、マイナーを取る操作に関して閉じていると言われる。F がマイナー閉族である場合、S をFに含まれないグラフのクラス（Fの補集合）とする。ロバートソン・シーモア定理によれば、Sには極小元の有限集合H が存在する。これらの極小元はFの禁制グラフ特徴付けを形成する。つまり、 F内のグラフは、 H内のどのグラフもマイナーとして持たないグラフである。 ^[9] Hのメンバーは、族Fの排除マイナー（または禁制マイナー、またはマイナー極小障害）と呼ばれる。

たとえば、平面グラフはマイナーを取ることに関して閉じています。つまり、平面グラフの辺を縮めたり、グラフから辺や頂点を削除したりしても、その平面性は失われません。したがって、平面グラフにはマイナーの禁止特性があり、この場合、これはワグナーの定理によって与えられます。マイナー極小非平面グラフの集合H には、完全グラフ K ₅と完全二部グラフ K _3,3の 2 つのグラフが含まれ、平面グラフは集合 { K ₅ ,  K _3,3 } 内にマイナーを持たないグラフとまったく同じです。

すべてのマイナー閉グラフ族に対する禁制マイナー特徴付けの存在は、ロバートソン・シーモア定理を述べるのと同等の方法です。というのは、すべてのマイナー閉族F が極小禁制マイナーの有限集合Hを持ち、S が任意のグラフの無限集合であると仮定します。SからF を、 Sにマイナーを持たないグラフの族として定義します。すると、Fはマイナー閉であり、極小禁制マイナーの有限集合Hを持ちます。 C をFの補集合とします。SとF は互いに素であり、H はCの極小グラフであるため、 SはCのサブセットです。 H内のグラフGを考えます。G はC内で極小であるため、S内に適切なマイナーを持つことはできません。同時に、G はS内にマイナーを持たなければなりません。そうでなければ、 G はFの要素になってしまうからです。したがって、GはSの要素、つまりHはSのサブセットであり、Sの他のすべてのグラフはHのグラフの間でマイナーを持つため、H はSの最小要素の有限集合です。

もう 1 つの含意として、すべてのグラフ集合には極小グラフの有限部分集合があり、マイナー閉集合Fが与えられていると仮定します。グラフがHにマイナーを持たない場合に限り、グラフがFに属するようなグラフの集合H を見つけます。Fに属するどのグラフのマイナーでもないグラフをEとし、Eに属する極小グラフの有限集合をHとします。ここで、任意のグラフGが与えられます。まず、 GがFに属すると仮定します。GはFに属し、H はEの部分集合であるため、 GはHにマイナーを持つことはできません。次に、 G がFに属さないと仮定します。すると、Fはマイナー閉であるため、G はFに属するどのグラフのマイナーでもありません。したがって、 GはEに属するため、G はHにマイナーを持ちます。

次の有限グラフの集合はマイナー閉であり、したがって（ロバートソン・シーモア定理により）マイナー特徴付けが禁止されている。

• フォレスト、線形フォレスト（パスグラフの非結合和）、疑似フォレスト、サボテングラフ。
• 平面グラフ、外平面グラフ、頂点グラフ（平面グラフに1つの頂点を追加して形成されます）、トロイダルグラフ、および任意の固定された2次元多様体に埋め込むことができるグラフ。^[10]
• ユークリッド3次元空間にリンクレスに埋め込み可能なグラフと、ユークリッド3次元空間に結び目レスに埋め込み可能なグラフ^[10]
• ある固定定数によって制限されるサイズのフィードバック頂点セットを持つグラフ。ある固定定数によって制限されるColin de Verdière グラフ不変量を持つグラフ。ある固定定数によって制限されるtreewidth、pathwidth、またはbranchwidth を持つグラフ。

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

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

ロバートソン・シーモア定理は、ロバートソンとシーモアによって、固定された各グラフhに対して、グラフがhをマイナーとして持つかどうかをテストする多項式時間アルゴリズムが存在するという証明により、計算の複雑さに関して重要な結果をもたらします。このアルゴリズムの実行時間は、マイナーhのサイズに超多項式的に依存する定数係数を持ちますが、3乗（チェックするグラフのサイズに対して）です。実行時間は、河原林、小林、およびリードによって2乗に改善されました。^[12]その結果、すべてのマイナー閉族Fに対して、グラフがFに属するかどうかをテストする多項式時間アルゴリズムが存在します。つまり、 Fの障害集合内の禁止されたマイナーhごとに、指定されたグラフにhが含まれているかどうかを単にチェックするだけです。 ^[13]

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

各kに対して、不変量が最大でkであるグラフはマイナー閉である、という特性を持つグラフ不変量の場合、同じ方法が適用されます。たとえば、この結果により、ツリー幅、ブランチ幅、パス幅、頂点カバー、および埋め込みの最小種数はすべてこのアプローチに従えるようになり、任意の固定kに対して、これらの不変量が最大でkであるかどうかをテストする多項式時間アルゴリズムが存在し、そのアルゴリズムの実行時間の指数はkに依存しません。指数がkに依存しない任意の固定kに対して多項式時間で解決できるというこの特性を持つ問題は、固定パラメータで扱いやすい問題として知られています。

しかし、この方法では、禁制のマイナーセットを決定するのが難しいため、 kが未知のグラフのパラメータ値を計算するための単一の固定パラメータで扱いやすいアルゴリズムを直接提供することはできません。さらに、これらの結果に含まれる大きな定数因子により、非常に非実用的になります。したがって、 kへの依存性を改善したこれらの問題に対する明示的な固定パラメータアルゴリズムの開発は、引き続き重要な研究分野となっています。

フリードマン、ロバートソン、シーモア（1987）は、次の定理が、ペアノ算術よりもはるかに強力なさまざまな形式システムでは証明不可能であるが、 ZFCよりもはるかに弱いシステムでは証明可能であるという点で独立性現象を示していることを示した。

定理:任意の正の整数nに対して、G ₁ , ..., G m_が有限無向グラフの列である場合に、

ここで、各G _{i の}サイズは最大でn + iであり、あるj < kに対してG _j ≤ G _{k と}なります。

(ここで、グラフの サイズは頂点と辺の合計数であり、≤ はマイナー順序を表します。)

• グラフ構造定理

• Bienstock, Daniel; Langston, Michael A. (1995)、「グラフマイナー定理のアルゴリズム的意味」(PDF)、ネットワークモデル、オペレーションズリサーチとマネジメントサイエンスのハンドブック、第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。
• フェローズ、マイケル R. ;ラングストン、マイケル A. (1988)、「多項式時間決定可能性を証明するための非構成的ツール」、Journal of the ACM、35 (3): 727–739、doi : 10.1145/44483.44491。
• フリードマン、ハーヴェイ、ロバートソン、ニール、シーモア、ポール(1987)、「グラフマイナー定理のメタ数学」、シンプソン、S. (編)、論理と組合せ論、現代数学、第 65 巻、アメリカ数学会、pp. 229–261。
• 河原林 健一; 小林 雄介;リード ブルース(2012)、「二次時間における非結合経路問題」(PDF)、Journal of Combinatorial Theory、シリーズ 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。
• ウェンディ・ミルボルド、ジェニファー・ウッドコック（2018）「トーラス障害の大規模セットとその発見方法」、電子組合せ論ジャーナル、25（1）：P1.16、doi：10.37236/3797。
• ロバートソン、ニール;シーモア、ポール(1983)、「グラフマイナー。I. フォレストの除外」、組み合わせ理論ジャーナル、シリーズ B、35 (1): 39–61、doi : 10.1016/0095-8956(83)90079-5。
• ロバートソン、ニール、シーモア、ポール(1995)、「グラフマイナー。XIII. 分離パス問題」、組み合わせ理論ジャーナル、シリーズ B、63 (1): 65–110、doi : 10.1006/jctb.1995.1006。
• ロバートソン、ニール、シーモア、ポール(2004)、「グラフマイナー。XX。ワグナーの予想」、組み合わせ理論ジャーナル、シリーズ B、92 (2): 325–357、doi : 10.1016/j.jctb.2004.08.001。

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