マトロイドマイナー

マトロイドの数学的理論では、マトロイドMのマイナーは、一連の制限および縮約操作によってMから得られる別のマトロイドNです。マトロイドマイナーはグラフマイナーと密接に関連しており、それらを形成する制限および縮約操作は、グラフのエッジ削除およびエッジ縮約操作に対応します。マトロイドマイナーの理論は、マトロイドの構造的分解と、グラフの対応する理論に類似した禁制マイナーによるマトロイド族の特徴付けにつながります。

M が集合E上のマトロイドであり、SがEのサブセットである場合、 M のSへの制限( M  | Sと表記) は、独立集合がSに含まれるMの独立集合である集合S上のマトロイドです。その回路はSに含まれるMの回路であり、そのランク関数はSのサブセットに制限されたMのランク関数です。

T がEの独立部分集合である場合、 MのTによる縮約、M / Tは、基底集合E − T上のマトロイドであり、その独立集合は、 Tとの和がMにおいて独立である集合である。この定義は、 Tの基底を選択し、この基底との和がMにおいて独立である限り、縮約において独立であると定義することによって、任意のTに拡張することができる。縮約のランク関数は、${\displaystyle r'(A)=r(A\cup T)-r(T).}$

マトロイドN は、制限操作と収縮操作によって Mから構築できる場合、マトロイドMのマイナーです。

マトロイドの平面によって形成される幾何学的格子の観点から見ると、マトロイドのマイナーを取ることは、格子の区間、つまり与えられた下限要素と上限要素の間にある格子の部分を取ることに相当する。^[1]

マトロイドの重要なファミリーの多くは、マイナーを取る操作の下で閉じています。つまり、マトロイドM がファミリーに属する場合、Mのすべてのマイナーもファミリーに属します。この場合、ファミリーは、ファミリーに属さないマイナー極小マトロイドである「禁制マトロイド」の集合によって特徴付けられる場合があります。マトロイドは、マイナーとして禁制マトロイドを持たない場合にのみ、ファミリーに属します。多くの場合、禁制マトロイドの集合は有限ですが、常にそうであるとは限りません。これは、マイナーが閉じたグラフ ファミリーの禁制マイナーの集合は常に有限であるというRobertson-Seymour 定理に似ています。

この現象の例は、すべての体で表現可能な正則マトロイドで与えられます。同様に、マトロイドは、完全にユニモジュラな行列(すべての正方部分行列の行列式が 0、1、または -1 に等しい行列) で表現できる場合、正則です。 Tutte (1958) は、マトロイドが正則であるためには、3 つの禁制小行列式、つまり一様マトロイド (4 点直線)、ファノ平面、またはファノ平面の双対マトロイドの 1 つを持たないことを証明しました。このために、彼は困難なホモトピー定理 を使用しました。その後、より簡単な証明が見つかりました。 ${\displaystyle U{}_{4}^{2}}$

グラフィックマトロイド(独立集合がグラフのフォレスト サブグラフであるマトロイド) には、5 つの禁制マイナーがあります。3 つは通常のマトロイドに対するもので、もう 1 つはグラフK ₅とK _{3,3に対するグラフィック マトロイドの 2 つのデュアルで、これらは}ワーグナーの定理により平面グラフの禁制マイナーです。

バイナリマトロイド、つまり2要素の有限体上で表現可能なマトロイドには、グラフィックマトロイドと通常マトロイドの両方が含まれます。 Tutteは、これらのマトロイドには禁制マイナー特性があることを再度示しました。つまり、これらは4点直線をマイナーとして持たないマトロイドです。Rotaは、任意の有限体に対して、その体上で表現可能なマトロイドには有限個の禁制マイナーがあると予想しました。^[2]この予想の証明は、2014年にGeelen、Gerards、Whittleによって発表されましたが、出版されていませんでした。^[3]実数上で表現できるマトロイドには、無限個の禁制マイナーがあります。^[4]

マトロイドの分岐分解は、グラフの定義と同様に定義できます。マトロイドの分岐分解は、マトロイド要素の階層的クラスタリングであり、マトロイドの要素を葉に持つ根なし二分木として表されます。この木のエッジを削除すると、マトロイドは 2 つの互いに素なサブセットに分割されます。このような分割は e 分離と呼ばれます。rがマトロイドのランク関数を表す場合、e 分離の幅はr ( A ) + r ( B ) − r ( M ) + 1と定義されます。分解の幅は、その e 分離の最大幅であり、マトロイドの分岐幅は、その分岐分解の最小幅です。

グラフの枝幅とそれに対応するグラフィックマトロイドの枝幅は異なる場合があります。たとえば、3辺のパスグラフと3辺のスターグラフの枝幅はそれぞれ2と1と異なりますが、どちらも枝幅1の同じグラフィックマトロイドを誘導します。^[5]ただし、ツリーではないグラフの場合、グラフの枝幅は、関連するグラフィックマトロイドの枝幅に等しくなります。^[6]マトロイドの枝幅は、常にそのデュアルの枝幅に等しくなります。^[5]

枝幅は、グラフマイナーの理論をマトロイドに拡張する試みの重要な要素です。木幅はマトロイドにも一般化でき、^[7]グラフマイナーの理論では枝幅よりも大きな役割を果たしますが、枝幅はマトロイドの設定でより便利な特性を持っています。^[8] 有限体上で表現可能なマトロイドのマイナー閉族にすべての平面グラフのグラフィックマトロイドが含まれていない場合、族内のマトロイドの枝幅には一定の境界があり、マイナー閉グラフ族に同様の結果を一般化します。^[9]

ロバートソン・シーモア定理は、禁制マイナーのリストによって特徴付けられるグラフィックマトロイドのすべてのマトロイド特性は、有限リストによって特徴付けられることを意味します。同じことを別の方法で言うと、マイナー操作によって形成されるグラフィックマトロイド上の部分順序は、十分に準順序付けされます。ただし、無限に多くの禁制マイナーを持つ実数表現可能なマトロイドの例は、マイナー順序付けがすべてのマトロイド上で十分に準順序付けされていないことを示しています。

ロバートソンとシーモアは、任意の特定の有限体上で表現可能なマトロイドは準整列していると推測した。これまでのところ、これは分岐幅が制限されたマトロイドに対してのみ証明されている。^[10]

グラフ構造定理はグラフマイナー理論の重要なツールであり、これによれば、任意のマイナー閉族のグラフは、より単純なグラフからクリーク和演算によって構築できる。マトロイド理論でも類似の結果がいくつか知られている。特に、シーモアの分解定理は、すべての正則マトロイドは、グラフィックマトロイド、その双対、および1つの特別な10要素マトロイドのクリーク和として簡単な方法で構築できることを述べている。^[11] 結果として、完全にユニモジュラな行列によって定義される線形計画は、この分解のグラフィック部分とコグラフィック部分に対応する 一連の最小全域木問題の解を組み合わせることによって、組み合わせ的に解くことができる。

グラフマイナー理論の重要な要素の 1 つは、グラフHが別のグラフGのマイナーであるかどうかをテストするためのアルゴリズムの存在です。このテストには、 Hの任意の固定された選択に対してGの多項式時間がかかります( Hのサイズが変化することを許可されている場合は、より強く固定パラメータを扱いやすくなります)。この結果を Robertson–Seymour の定理と組み合わせると、任意のマイナー閉じたグラフファミリのメンバーを多項式時間で認識できます。これに対応して、マトロイド理論では、与えられた固定マトロイドが入力マトロイドのマイナーであるかどうかを認識するための効率的なアルゴリズムを開発することが望ましいでしょう。残念ながら、そのような強力な結果は不可能です。マトロイドオラクルモデルでは、多項式時間で認識できるマイナーは、ランクまたはコランクが 1 のユニフォームマトロイドだけです。 ^[12]しかし、問題が何らかの固定された有限体上で表現可能なマトロイド（そしてその体上の行列として表現される）に限定されている場合、グラフの場合と同様に、任意の固定されたマイナーを含むマトロイドを多項式時間で認識できると推測される。^[8]