マトロイド

数学の一分野である組合せ論 において、マトロイド（ˈ m eɪ t r ɔɪ d）は、ベクトル空間における線型独立性の概念を抽象化して一般化する構造である。マトロイドを公理的に定義する同等の方法はたくさんありますが、最も重要なのは、独立集合、基底または回路、階数関数、閉包演算子、および閉集合またはフラットの観点から定義することです。半順序集合の言語では、有限単純マトロイドは幾何学的格子と同等です。

マトロイド理論は、主にこれらの分野で中心的な重要性を持つ様々な概念を抽象化したものであるため、線型代数学とグラフ理論の両方で使用される用語から広範囲に借用しています。マトロイドは、幾何学、位相幾何学、組合せ最適化、ネットワーク理論、符号理論に応用されています。^{[1] [2]}

（有限）マトロイドを定義する同等の方法はたくさんあります。 ^[a]

独立性の観点から見ると、有限マトロイドは、が有限集合（基底集合と呼ばれる）であり、が（独立集合と呼ばれる）の部分集合の族であり、以下の性質を持つペアである： ^[3]${\displaystyle M}$${\displaystyle (E,{\mathcal {I}})\ ,}$${\displaystyle E}$${\displaystyle {\mathcal {I}}}$${\displaystyle E}$

• （I1）空集合は独立である、すなわち、${\displaystyle \emptyset \in {\mathcal {I}}~.}$

• (I2) 独立集合のすべての部分集合は独立である、すなわち、各 に対してならばである。これは遺伝的性質、または下向きに閉じた性質と呼ばれることもある。${\displaystyle A'\subseteq A\subseteq E\ ,}$${\displaystyle A\in {\mathcal {I}}}$${\displaystyle A'\in {\mathcal {I}}~.}$

• (I3)と が2 つの独立集合 (つまり、各集合が独立) であり、 の要素数が多い場合、がとなるような集合が存在します。これは、増加特性または独立集合交換特性と呼ばれることもあります。${\displaystyle A}$${\displaystyle B}$${\displaystyle A}$${\displaystyle B\ ,}$${\displaystyle x\in A\setminus B}$${\displaystyle B\cup \{x\}}$${\displaystyle {\mathcal {I}}~.}$

最初の 2 つの特性は、独立性システム(または抽象単体複合体)として知られる組み合わせ構造を定義します。実際には、(I2) を仮定すると、特性 (I1) は、 の少なくとも 1 つのサブセットが独立である、つまり であるという事実と同等です。 ${\displaystyle E}$${\displaystyle {\mathcal {I}}\neq \emptyset }$

基底集合の独立でない部分集合は従属集合と呼ばれる。最大の独立集合、つまり の任意の要素を追加すると従属する独立集合は、マトロイドの基底と呼ばれる。マトロイドの回路はの最小の従属部分集合、つまりその固有部分集合がすべて独立している従属集合である。この用語は、グラフィックマトロイドの回路が対応するグラフのサイクルであることから生じた。 ^[3]${\displaystyle E}$${\displaystyle E}$${\displaystyle M}$${\displaystyle E}$

マトロイドの従属集合、基底、または回路は、マトロイドを完全に特徴づけます。集合が独立である場合、それは従属していない場合、基底の部分集合である場合、および回路を含まない場合のみです。従属集合、基底、および回路のコレクションはそれぞれ、マトロイドの公理としてとらえることができる単純なプロパティを持っています。たとえば、マトロイドをペア と定義できます。ここで、 は前述のように有限集合であり、 は基底と呼ばれる部分集合のコレクションであり、次のプロパティを持ちます。^[3]${\displaystyle M}$${\displaystyle (E,{\mathcal {B}})}$${\displaystyle E}$${\displaystyle {\mathcal {B}}}$${\displaystyle E,}$

• (B1)は空ではありません。${\displaystyle {\mathcal {B}}}$

• (B2)とがの異なる要素である場合、次のような元が存在する。${\displaystyle A}$${\displaystyle B}$${\displaystyle {\mathcal {B}}}$${\displaystyle a\in A\smallsetminus B\ ,}$${\displaystyle b\in B\smallsetminus A}$${\displaystyle (A\smallsetminus \{a\})\cup \{b\}\in {\mathcal {B}}~.}$

この性質(B2)は基底交換性質と呼ばれます。この性質から、 のどの要素も他の要素の適切な部分集合にはなり得ないことがわかります。 ${\displaystyle {\mathcal {B}}}$

マトロイドの任意の 2 つの基底は同じ数の要素を持つというのは、マトロイド理論の基本的な結果であり、線型代数における同様の基底定理に直接類似している。この数はのランクと呼ばれる。が上のマトロイドであり がのサブセットである場合、のサブセットが独立であるとは、それが で独立している場合に限ると見なすことで、 上のマトロイドを定義できる。これにより、サブマトロイドについて、および の任意のサブセットのランクについて話すことができる。サブセットのランクは、マトロイドのランク関数によって与えられ、次の特性を持つ。^[3]${\displaystyle M}$ ${\displaystyle M~.}$${\displaystyle M}$${\displaystyle E\ ,}$${\displaystyle A}$${\displaystyle E}$${\displaystyle A}$${\displaystyle A}$${\displaystyle M~.}$${\displaystyle E~.}$${\displaystyle A}$ ${\displaystyle r(A)}$

• (R1) ランク関数の値は常に負でない整数です。

• (R2) 任意の部分集合 に対して、${\displaystyle A\subset E}$${\displaystyle r(A)\leq |A|~.}$

• (R3) 任意の2つの部分集合に対して、次式が成り立ちます。つまり、階数はサブモジュラ関数です。${\displaystyle A,B\subset E}$${\displaystyle r(A\cup B)+r(A\cap B)\leq r(A)+r(B)~.}$

• (R4) 任意の集合と要素について、次が成り立ちます。最初の不等式から、より一般的には、 の場合、つまり、rank は単調関数であることがわかります。${\displaystyle A}$${\displaystyle x\,}$${\displaystyle r(A)\leq r(A\cup \{x\})\leq r(A)+1~.}$${\displaystyle A\subseteq B\subseteq E\ ,}$${\displaystyle r(A)\leq r(B)\leq r(E)~.}$

これらの特性は、有限マトロイドの代替定義の 1 つとして使用できます。 がこれらの特性を満たす場合、 上のマトロイドの独立集合は、を持つのサブセットとして定義できます。半順序集合の言語では、このようなマトロイド構造は、要素が包含によって部分的に順序付けられたサブセットである幾何学的格子と同等です。 ${\displaystyle (E,r)}$${\displaystyle E}$${\displaystyle A}$${\displaystyle E}$${\displaystyle r(A)=|A|~.}$${\displaystyle A\subset M\ ,}$

差はサブセットの無効性と呼ばれます。これは、独立集合を得るために から削除しなければならない要素の最小数です。におけるの無効性は の無効性と呼ばれます。差はサブセットの共階数と呼ばれることもあります。 ${\displaystyle |A|-r(A)}$${\displaystyle A~.}$${\displaystyle A}$${\displaystyle E}$${\displaystyle M}$${\displaystyle M~.}$${\displaystyle r(E)-r(A)}$${\displaystyle A}$

を有限集合 上のマトロイドとし、階数関数は上記の通りとする。の部分集合の閉包またはスパンは集合 ${\displaystyle M}$${\displaystyle E\}$${\displaystyle r}$ ${\displaystyle \operatorname {cl} (A)}$${\displaystyle A}$${\displaystyle E}$

${\displaystyle \operatorname {cl} (A)={\Bigl \{}\ x\in E\mid r(A)=r{\bigl (}A\cup \{x\}{\bigr )}{\Bigr \}}~.}$

これは、次の特性を持つ べき集合を表す閉包演算子を定義します。 ${\displaystyle \operatorname {cl} :{\mathcal {P}}(E)\mapsto {\mathcal {P}}(E)}$${\displaystyle {\mathcal {P}}}$

• （C1）すべての部分集合について${\displaystyle X}$${\displaystyle E\ ,}$ ${\displaystyle X\subseteq \operatorname {cl} (X)~.}$

• （C2）すべての部分集合について${\displaystyle X}$${\displaystyle E\ ,}$ ${\displaystyle \operatorname {cl} (X)=\operatorname {cl} \left(\operatorname {cl} \left(X\right)\right)~.}$

• (C3) のすべての部分集合とに対して、${\displaystyle X}$${\displaystyle Y}$${\displaystyle E}$${\displaystyle X\subseteq Y\ ,}$ ${\displaystyle \operatorname {cl} (X)\subseteq \operatorname {cl} (Y)~.}$

• (C4) およびのすべての要素とのすべての部分集合に対して、${\displaystyle a}$${\displaystyle b}$${\displaystyle E}$${\displaystyle Y}$${\displaystyle E\ ,}$${\displaystyle a\in \operatorname {cl} (Y\cup \{b\})\smallsetminus \operatorname {cl} (Y)}$${\displaystyle b\in \operatorname {cl} (Y\cup \{a\})\smallsetminus \operatorname {cl} (Y)~.}$

これらの特性のうち最初の3つは閉包演算子の定義特性です。4番目はマクレーン・シュタイニッツ交換特性と呼ばれることもあります。これらの特性はマトロイドの別の定義として捉えることができます。つまり、これらの特性に従うすべての関数はマトロイドを決定します。^[3]${\displaystyle \operatorname {cl} :{\mathcal {P}}(E)\to {\mathcal {P}}(E)}$

閉包がそれ自身に等しい集合は閉じている、あるいはマトロイドの平坦空間または部分空間であると言われる。 ^{[4]集合がそのランクに対して}最大である場合、集合は閉じている。つまり、集合に他の要素を追加するとランクが増加する。マトロイドの閉集合は被覆分割特性によって特徴付けられる。

• (F1) 点集合全体が閉じられます。${\displaystyle E}$

• (F2) とがフラットであれば、 はフラットです。${\displaystyle S}$${\displaystyle T}$${\displaystyle S\cap T}$

• (F3)がフラットである場合、 の各要素はを覆うフラットのちょうど 1 つに含まれます(つまり、 は を適切に含みますが、と の間にフラットは存在しません)。${\displaystyle S}$${\displaystyle E\smallsetminus S}$${\displaystyle T}$ ${\displaystyle S}$${\displaystyle T}$${\displaystyle S\ ,}$${\displaystyle U}$${\displaystyle S}$${\displaystyle T}$

集合包含によって部分的に順序付けられたすべての平面のクラスは、マトロイド格子を形成する。逆に、すべてのマトロイド格子は、次の閉包演算子の下で、その原子の集合上のマトロイドを形成する。結合を持つ原子の集合に対して${\displaystyle {\mathcal {L}}(M)}$${\displaystyle L}$${\displaystyle E}$${\displaystyle S}$${\displaystyle \bigvee S\ ,}$

${\displaystyle \operatorname {cl} (S)=\{x\in E\mid x\leq \bigvee S\}~.}$

このマトロイドの平面は格子の要素と1対1に対応しており、格子要素に対応する平面は集合 ${\displaystyle y}$

${\displaystyle \{x\in E\mid x\leq y\}~.}$

したがって、このマトロイドの平面の格子は自然に と同型です。 ${\displaystyle L}$

階数のマトロイドにおいて、階数のフラットは超平面と呼ばれる。(超平面はコアトムまたはコポイントとも呼ばれる。) これらは最大限に適切なフラットである。つまり、フラットでもある超平面の唯一のスーパーセットは、マトロイドのすべての要素の集合である。同等の定義は、コアトムはM を張らないEのサブセットであるが、それに他の要素を追加するとスパニングセットになるというものである。^[5]${\displaystyle r\ ,}$${\displaystyle r-1}$${\displaystyle E}$

マトロイドの超平面族には次のような性質があり、これはマトロイドのもう一つの公理化として捉えることができる。 ^[5]${\displaystyle {\mathcal {H}}}$

• (H1)には異なる集合とが存在しない。つまり、超平面はスペルナー族を形成する。${\displaystyle X}$${\displaystyle Y}$${\displaystyle {\mathcal {H}}}$${\displaystyle X\subseteq Y~.}$

• (H2) と異なるすべてのに対して、とが存在する。${\displaystyle x\in E}$${\displaystyle Y,Z\in {\mathcal {H}}}$${\displaystyle x\notin Y\cup Z\ ,}$${\displaystyle X\in {\mathcal {H}}}$${\displaystyle (Y\cap Z)\cup \{x\}\subseteq X~.}$

ミンティ（1966）は、グラフォイドを、およびがの非空部分集合のクラスであって、 ${\displaystyle (L,C,D)}$${\displaystyle C}$${\displaystyle D}$${\displaystyle L}$

• （G1）（「回路」と呼ばれる）のどの要素も他の要素を含まない、${\displaystyle C}$

• （G2）の要素（「コサーキット」と呼ばれる）は他の要素を含まない。${\displaystyle D}$

• (G3) 内の集合と内の集合がちょうど1つの要素で交差せず、${\displaystyle C}$${\displaystyle D}$

• (G4) が(単独集合)と部分集合の非結合和集合として表されるときは、 が存在して となるか、 が存在して となるかのいずれかである。${\displaystyle L}$${\displaystyle R,G,B}$${\displaystyle G=\{g\}}$${\displaystyle X\in C}$${\displaystyle g\in X\subseteq R\cup G}$${\displaystyle Y\in D}$${\displaystyle g\in Y\subseteq B\cup G~.}$

彼は、が回路のクラスであり、が余回路のクラスであるマトロイドが存在することを証明しました。逆に、と が基底集合を持つマトロイドの回路クラスと余回路クラスである場合、 はグラフォイドです。したがって、グラフォイドはマトロイドの 自己双対暗号型公理化を与えます。${\displaystyle C}$${\displaystyle D}$${\displaystyle C}$${\displaystyle D}$${\displaystyle M}$${\displaystyle E\ ,}$${\displaystyle (E,C,D)}$

を有限集合とします。 のすべての部分集合の集合はマトロイドの独立集合を定義します。これは上の自由マトロイドと呼ばれます。 ${\displaystyle E}$${\displaystyle E}$${\displaystyle E}$

を有限集合、自然数とします。 のすべての要素サブセットを基底として、上のマトロイドを定義できます。これは、ランク の一様マトロイドとして知られています。ランク を持ち、要素を持つ一様マトロイドは と表されます。ランク 2 以上のすべての一様マトロイドは単純です (§ その他の用語を参照)。点上のランク 2 の一様マトロイドは、点線と呼ばれます。マトロイドが一様であるのは、そのマトロイドのランクに 1 を加えた値よりも小さいサイズの回路がない場合のみです。一様マトロイドの直和は、分割マトロイドと呼ばれます。 ${\displaystyle E}$${\displaystyle k}$${\displaystyle E}$${\displaystyle k}$${\displaystyle E}$${\displaystyle k~.}$${\displaystyle k}$${\displaystyle n}$${\displaystyle U_{k,n}~.}$${\displaystyle n}$${\displaystyle n}$ 

一様マトロイドでは、すべての要素はループ（どの独立集合にも属さない要素）であり、一様マトロイドでは、すべての要素はコロプ（すべての基底に属する要素）です。これら 2 種類のマトロイドの直和は、すべての要素がループまたはコロプである分割マトロイドであり、離散マトロイドと呼ばれます。離散マトロイドの同等の定義は、基底集合のすべての適切な空でない部分集合がセパレータであるマトロイドです。 ${\displaystyle U_{0,n}\ ,}$${\displaystyle U_{n,n}\ ,}$${\displaystyle E}$

マトロイド理論は、主にベクトル空間における独立性と次元の特性の詳細な調査から発展しました。このように定義されたマトロイドを表現する方法は 2 つあります。

がベクトル空間の任意の有限部分集合である場合、の独立集合をの線型独立部分集合としてとることで、上のマトロイドを定義することができる。${\displaystyle E}$ ${\displaystyle V\ ,}$${\displaystyle M}$${\displaystyle E}$${\displaystyle M}$${\displaystyle E~.}$

このマトロイドの独立集合公理の妥当性は、シュタイニッツ交換補題から導かれます。

がこのように定義できるマトロイドである場合、その集合は${\displaystyle M}$${\displaystyle E}$ ${\displaystyle M~.}$

この種のマトロイドはベクトルマトロイドと呼ばれます。

このように定義されたマトロイドの重要な例として、ファノマトロイドが挙げられます。これは、 7 つの点 (マトロイドの 7 つの要素) と 7 つの線 (マトロイドの適切な非自明な平面) を持つ有限幾何学であるファノ平面から派生した階数 3 のマトロイドです。これは、有限体GF(2)上の 3 次元ベクトル空間内の 7 つの非ゼロ点として要素が記述される線形マトロイドです。ただし、 GF(2) の代わりに 実数を使用してファノマトロイドの同様の表現を提供することはできません。

フィールドにエントリを持つ行列は 、その列の集合にマトロイドを生成します。マトロイドの従属列集合は、ベクトルとして線形従属する集合です。 ${\displaystyle A}$${\displaystyle M}$

このマトロイドはの列マトロイドと呼ばれ、 を表すと言われています。${\displaystyle A}$${\displaystyle A}$ ${\displaystyle M}$

例えば、ファノマトロイドは3×7 (0,1)行列として表現できます。列マトロイドは別名ベクトルマトロイドですが、行列表現を好む理由がしばしばあります。^[b]

ベクトルマトロイドと同等のマトロイドは、表現方法が異なっていても、表現可能または線形と呼ばれます。 が体上のベクトルマトロイドと同等である場合、 は上で表現可能であるといいます。特に、が実数 上で表現可能である場合、 は実数表現可能です。たとえば、グラフィックマトロイド (以下を参照) はグラフで表現されますが、任意の体上のベクトルでも表現できます。 ${\displaystyle M}$ ${\displaystyle F}$${\displaystyle M}$ ${\displaystyle F}$${\displaystyle M}$

マトロイド理論における基本的な問題は、与えられた体上で表現できるマトロイドを特徴づけることである。ロータの予想は、あらゆる有限体に対して可能な特徴づけを記述する。これまでの主な成果は、トゥッテ（1950年代）による2元マトロイド（GF(2)上で表現できるもの） 、リードとビクスビー、およびシーモア（1970年代）による3元マトロイド（3要素体上で表現できるもの）、およびギーレン、ジェラーズ、カプール（2000年）による4元マトロイド（4要素体上で表現できるもの）の特徴づけである。ロータの予想の証明は、2014年にギーレン、ジェラーズ、ホイットルによって発表されたが、出版されなかった。^[6]${\displaystyle F}$

通常のマトロイドは、すべての可能なフィールドで表現可能なマトロイドです。Vámosマトロイドは、どのフィールドでも表現できないマトロイドの最も単純な例です。

マトロイド理論の2番目の起源はグラフ理論です。

すべての有限グラフ（またはマルチグラフ）は、次のようにマトロイドを生成します。を のすべての辺の集合として取り、辺の集合 がフォレスト である場合、つまり単純なサイクル を含まない場合に限り、 を独立であるとみなします。はサイクルマトロイドと呼ばれます。このようにして導出されたマトロイドはグラフィックマトロイドです。すべてのマトロイドがグラフィックであるとは限りませんが、3つの要素上のすべてのマトロイドはグラフィックです。^[7]すべてのグラフィックマトロイドは正則です。 ${\displaystyle G}$${\displaystyle M(G)}$${\displaystyle E}$${\displaystyle G}$${\displaystyle M(G)}$

その後、グラフ上の他のマトロイドが発見されました。

• グラフの双円マトロイドは、接続されたすべてのサブセットに最大 1 つのサイクルが含まれる場合、エッジのセットが独立であると言うことによって定義されます。

• 任意の有向グラフまたは無向グラフにおいて、 と を2 つの異なる頂点集合とする。集合 において、からへの頂点が互いに素な経路が存在する場合、の部分集合 が独立であると定義する。これにより、 上のマトロイドがガモイドと呼ばれることが定義される。^[8]厳密なガモイドとは、 の集合がの頂点集合全体となるものである。^[9]${\displaystyle G}$${\displaystyle E}$${\displaystyle F}$${\displaystyle E}$${\displaystyle U}$${\displaystyle |U|}$${\displaystyle F}$${\displaystyle U}$${\displaystyle E}$${\displaystyle E}$${\displaystyle G}$

• 二部グラフ では、要素が二部グラフの片側の頂点であり、独立部分集合がグラフのマッチングの端点の集合であるマトロイドを形成できる。これは横断マトロイドと呼ばれ、^{[10] [11]}ガモイドの特殊なケースである。^[8] 横断マトロイドは、厳密なガモイドの双対マトロイドである。 ^[9]${\displaystyle G=(U,V,E)}$${\displaystyle U}$

• グラフィック マトロイドは、符号付きグラフ、ゲイン グラフ、およびバイアス グラフからのマトロイドに一般化されています。 「バイアス グラフ」と呼ばれる、サイクルの明確な線形クラスを持つグラフには、フレーム マトロイドとバイアス グラフのリフトマトロイドと呼ばれる 2 つのマトロイドがあります。${\displaystyle G}$${\displaystyle B}$${\displaystyle (G,B)\ ,}$

すべてのサイクルが区別されたクラスに属する場合、これらのマトロイドは のサイクル マトロイドと一致します。サイクルが区別されていない場合、フレーム マトロイドは の双円マトロイドです。エッジが符号でラベル付けされた符号付きグラフと、エッジがグループから方向付けられてラベル付けされたグラフであるゲイン グラフは、それぞれバイアス グラフを生成し、したがってフレーム マトロイドとリフト マトロイドを持ちます。${\displaystyle G}$${\displaystyle G~.}$

• ラマングラフは、構造剛性理論で定義されるマトロイドである2 次元剛性マトロイドの基底を形成します。

• を連結グラフとし、をその辺集合とする。を連結されたままであるようなの部分集合の集合とする。すると、その要素集合は であり、独立集合のクラスとして を持つマトロイドは、 の結合マトロイドと呼ばれる。${\displaystyle G}$${\displaystyle E}$${\displaystyle I}$${\displaystyle F}$${\displaystyle E}$${\displaystyle G-F}$${\displaystyle M^{*}(G)\ ,}$${\displaystyle E}$${\displaystyle I}$${\displaystyle G~.}$

ランク関数は、エッジ サブセット上に誘導されるサブグラフの循環数であり、そのサブグラフの最大フォレストの外側のエッジの数、およびその中の独立したサイクルの数に等しくなります。${\displaystyle r(F)}$${\displaystyle F\ ,}$

マトロイド理論の3番目の起源は場の理論です。

体の拡張によりマトロイドが生成されます。

および が を含む体であると仮定します。を の任意の有限部分集合とします。${\displaystyle F}$${\displaystyle K}$${\displaystyle K}$${\displaystyle F}$${\displaystyle E}$${\displaystyle K}$

拡大体の超越次数が^[12]に等しいとき、その部分集合を代数的に独立であると定義する。${\displaystyle S}$${\displaystyle E}$${\displaystyle F(S)}$${\displaystyle |S|~.}$

この種のマトロイドと同等のマトロイドは代数マトロイドと呼ばれます。^[13] 代数マトロイドを特徴付ける問題は非常に難しく、それについてはほとんど知られていません。Vámosマトロイドは代数的ではないマトロイドの例を提供します。

古いマトロイドから新しいマトロイドを作成する標準的な方法がいくつかあります。

が有限マトロイドである場合、同じ基底集合を取り、その補集合が の基底である場合に限り、 の基底と呼ぶことで直交マトロイドまたは双対マトロイドを定義できる。 がマトロイドであり、 の双対が^[14]であることを確認することは難しくない。${\displaystyle M}$ ${\displaystyle M^{*}}$${\displaystyle M^{*}}$${\displaystyle M~.}$${\displaystyle M^{*}}$${\displaystyle M^{*}}$${\displaystyle M~.}$

双対は、マトロイドを定義する他の方法でも同様に説明できます。たとえば、次のようになります。

• 集合が独立であるのは、その補集合が${\displaystyle M^{*}}$${\displaystyle M~.}$

• 集合は、その補集合が${\displaystyle M^{*}}$${\displaystyle M~.}$

• 双対のランク関数は${\displaystyle r^{*}(S)=|S|-r(M)+r\left(E\smallsetminus S\right)~.}$

クラトフスキーの定理のマトロイド版によれば、グラフィックマトロイドの双対がグラフィックマトロイドであるための必要条件は、 が平面グラフのマトロイドである場合である。この場合、 の双対はの双対グラフのマトロイドである。 ^[15]特定の体上で表現可能なベクトルマトロイドの双対は上でも表現可能である。横断マトロイドの双対は厳密なガモイドであり、その逆もまた同様である。 ${\displaystyle M}$${\displaystyle M}$${\displaystyle M}$${\displaystyle G~.}$${\displaystyle F}$${\displaystyle F~.}$

例

グラフのサイクルマトロイドは、その結合マトロイドの双対マトロイドです。

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

線型代数では、これはSのベクトルによって生成される部分空間に制限することに相当する。同様に、T = M − Sの場合、これはTの削除と呼ばれ、M \ TまたはM − Tと表記される。 Mのサブマトロイドは、まさに一連の削除の結果であり、順序は無関係である。^{[16] [17]}

制限の双対的な操作は縮約である。^[18] T がEのサブセットである場合、MのTによる縮約、M / Tと書かれる、は階数関数が次の基底集合E − T上のマトロイドである。 ^{[19]線型代数では、これは}T のベクトルによって生成される線型空間による商空間を、 E - Tのベクトルの像とともに見ることに相当します。 ${\displaystyle r'(A)=r(A\cup T)-r(T).}$

Mから一連の制限と収縮操作によって得られるマトロイドNは、 Mのマイナーと呼ばれます。^{[17] [20]} M にはマイナーとしてN が含まれていると 言います。多くの重要なマトロイド族は、その族に属さないマイナー極小マトロイドによって特徴付けられる場合があります。これらは禁制マイナーまたは排除マイナーと呼ばれます。^[21]

M を要素の基本集合Eを持つマトロイドとし、N を基本集合 F 上の別のマトロイドとします。マトロイドMとN の直和は、その基本集合がEとFの非結合和であり、その独立集合がMの独立集合とNの独立集合の非結合和であるマトロイドです。

MとNの和集合は、その基礎集合がEとFの和集合（互いに素な和集合ではない）であり、その独立集合がMの独立集合とNの独立集合の和集合である部分集合であるマトロイドです。通常、「和集合」という用語はE = Fの場合に適用されますが、この仮定は必須ではありません。EとFが互いに素である場合、和集合は直和です。

M を、要素の基底集合Eを持つマトロイドとします。

• E はMの基底集合と呼ぶことができ、その要素はMの点と呼ぶことができる。

• E の部分集合がMを張る とは、その閉包がEである場合です。集合が閉集合Kを張るとは、その閉包がKである場合です。

• マトロイドの内周は、その最小の回路または従属セットのサイズです。

• Mの単一要素回路を形成する要素はループと呼ばれる。同様に、要素がどの基底にも属さない場合もループである。^{[7] [22]}

• どの回路にも属さない要素は、コロプまたは地峡と呼ばれます。同様に、要素がすべての基底に属する場合、その要素はコロプです。

ループとコループは相互に双対である。^[22]

• 2要素集合{ f,g }がMの回路である場合、fとgはM内で平行である。^[7]

• マトロイドは、1 要素または 2 要素からなる回路を持たない場合、単純マトロイドと呼ばれます。つまり、ループや並列要素はありません。組み合わせ幾何学という用語も使用されます。^[7]すべてのループを削除し、各 2 要素回路から 1 つの要素を削除して 2 要素回路がなくなるまで 別のマトロイドMから得られる単純マトロイドは、 Mの単純化と呼ばれます。^[23]マトロイドは、その双対マトロイドが単純である場合、共単純です。^[24]

• 回路の和集合は、Mのサイクルと呼ばれることもあります。したがって、サイクルは、双対マトロイドのフラットの補集合です。(この用法は、グラフ理論における「サイクル」の一般的な意味と矛盾します。)

• MのセパレータはEの部分集合Sであり、 となる。適切なセパレータまたは非自明なセパレータとは、 Eでも空集合でもないセパレータである。 ^[25]既約セパレータとは、他の空でないセパレータを含まない空でないセパレータである。既約セパレータは基底集合E を分割する。${\displaystyle r(S)+r(E-S)=r(M)}$

• 2つの空でないマトロイドの直和として表すことができないマトロイド、または同等に適切なセパレータを持たないマトロイドは、連結または既約と呼ばれます。マトロイドが連結であるのは、その双対が連結されている場合のみです。^[26]

• Mの最大既約サブマトロイドはMの成分と呼ばれる。成分はMの既約セパレータへの制限であり、逆にMの既約セパレータへの制限は成分である。セパレータは成分の和集合である。^[25]

• マトロイドMは、Mまたはそれを含むマトロイドが、 Mのすべての点が基底要素のペアを結ぶ線上に含まれるような基底を持つ場合、フレームマトロイドと呼ばれます。 ^[27]

• マトロイドの全ての回路の大きさが少なくともそのランクに等しい場合、そのマトロイドは舗装マトロイドと呼ばれる。 ^[28]

• マトロイド多面体は 、 の基底の指示ベクトルの凸包です。${\displaystyle P_{M}}$${\displaystyle M}$

いくつかの重要な組み合わせ最適化問題は、あらゆるマトロイド上で効率的に解決できます。特に、

• 重み付きマトロイドの最大重み独立集合を見つけることは、貪欲アルゴリズムによって解決できます。この事実はマトロイドを特徴付けるためにも使用できます。つまり、部分集合を取ることで閉じた集合の族F が、集合の重み付けに関係なく貪欲アルゴリズムによって族内で最大重み集合が見つかるという性質を持つ場合、F はマトロイドの独立集合の族でなければなりません。^[29]

• マトロイド分割問題は、マトロイドの要素をできるだけ少ない独立集合に分割することであり、マトロイドパッキング問題は、できるだけ多くの互いに素な全域集合を見つけることです。どちらも多項式時間で解決でき、マトロイドの合計のランクを計算する問題や独立集合を見つける問題に一般化できます。

• 同じ基底集合上の 2 つ以上のマトロイドのマトロイド交差は、各マトロイドで同時に独立である集合の族です。2 つのマトロイドの交差で最大の集合、または最大重み付き集合を見つける問題は、多項式時間で見つけることができ、他の多くの重要な組み合わせ最適化問題の解決策を提供します。たとえば、二部グラフの最大マッチングは、2 つのパーティション マトロイドを交差させる問題として表現できます。ただし、3 つ以上のマトロイドの交差で最大の集合を見つけることはNP 完全です。

マトロイドの計算のための 2 つのスタンドアロン システムは、Kingan の Oid と Hlineny の Macek です。どちらもオープン ソース パッケージです。「Oid」は、マトロイドの実験のためのインタラクティブで拡張可能なソフトウェア システムです。「Macek」は、表現可能なマトロイドを使用した合理的に効率的な組み合わせ計算のためのツールとルーチンを備えた特殊なソフトウェア システムです。

オープンソースの数学ソフトウェアシステムSAGEとMacaulay2にはマトロイドパッケージが含まれています。Mapleにはバージョン2024以降、マトロイドを扱うためのパッケージがあります。^[30]

基底集合E上の有限マトロイドMに関連付けられた特に重要な多項式が 2 つあります。それぞれはマトロイド不変量であり、同型マトロイドは同じ多項式を持つことを意味します。

Mの特性多項式は、彩色を数えないものの 、彩色多項式^{[31]と呼ばれることもあるが、次のように定義される。}

${\displaystyle p_{M}(\lambda ):=\sum _{S\subseteq E}(-1)^{|S|}\lambda ^{r(E)-r(S)},}$

または（空集合がMにおいて閉じている限り）

${\displaystyle p_{M}(\lambda ):=\sum _{A}\mu (\emptyset ,A)\lambda ^{r(E)-r(A)}\ ,}$

ここでμはマトロイドの幾何学的格子のメビウス関数を表し、その和はマトロイドのすべての平面Aにわたって取られる。 ^[32]

• M がグラフGのサイクルマトロイドM ( G ) である場合、特性多項式は彩色多項式をわずかに変形したもので、 χ _G  (λ) = λ ^c p _{M ( G )} (λ)で与えられます 。ここで、c はGの連結成分の数です。

• M がグラフGの結合マトロイドM *( G ) である場合、特性多項式はGのフロー多項式に等しくなります。

• M がℝ ⁿ (またはF ⁿ 、ただしFは任意の体)内の線型超平面の配置AのマトロイドM ( A )である場合、配置の特性多項式はp _A  (λ) = λ ^{n − r ( M )} p _M  (λ) で与えられます。

クラポ（1967）によって導入されたマトロイドのベータ不変量は、導関数の評価として特性多項式で表現することができる^[33]${\displaystyle p}$

${\displaystyle \beta (M)=(-1)^{r(M)-1}p_{M}'(1)}$

または直接^[34]

${\displaystyle \beta (M)=(-1)^{r(M)}\sum _{X\subseteq E}(-1)^{|X|}r(X)~.}$

ベータ不変量は非負であり、が切断されているか、空であるか、ループである場合にのみゼロとなる。それ以外の場合は、のフラットの格子にのみ依存する。ループとコロループがない場合、 ^[34]${\displaystyle M}$${\displaystyle M~.}$${\displaystyle M}$${\displaystyle \beta (M)=\beta (M^{*})~.}$

の第一種のホイットニー数は、特性多項式におけるのべき乗の係数です。具体的には、番目のホイットニー数はの係数であり、 はメビウス関数の値の合計です。 ${\displaystyle M}$${\displaystyle \lambda }$${\displaystyle i}$${\displaystyle w_{i}(M)}$${\displaystyle \lambda ^{r(M)-i}}$

${\displaystyle w_{i}(M)=\sum \{\mu (\emptyset ,A):r(A)=i\},}$

右の階数のフラットを合計します。これらの数字は符号が交互に変わるため、${\displaystyle (-1)^{i}w_{i}(M)>0}$${\displaystyle 0\leq i\leq r(M)~.}$

2 つ目の種類のホイットニー数は、各ランクのフラットの数です。つまり、はランク フラットの数です 。 ${\displaystyle M}$${\displaystyle W_{i}(M)}$${\displaystyle i}$

両種のホイットニー数は、第1種および第2種のスターリング数を一般化したものであり、これらは完全グラフのサイクルマトロイドのホイットニー数であり、分割格子のホイットニー数と同等である。これらは、マトロイド理論の（共同）創始者であるハスラー・ホイットニーにちなんで、ジャン・カルロ・ロータによって命名された。この名前は、有限の順位付けされた半順序集合の同様の数にも拡張されている。

マトロイドのトゥッテ多項式は、特性多項式を2つの変数に一般化したものである。これにより、より組み合わせ的な解釈が可能になり、双対性も得られる。 ${\displaystyle T_{M}(x,y)\ ,}$

${\displaystyle T_{M^{*}}(x,y)=T_{M}(y,x)\ ,}$

これは、 の性質と の性質の間にいくつかの双対性があることを意味している。 Tutte 多項式の定義の 1 つは、 ${\displaystyle M}$${\displaystyle M^{*}~.}$

${\displaystyle T_{M}(x,y)=\sum _{S\subseteq E}(x-1)^{r(M)-r(S)}\ (y-1)^{|S|-r(S)}~.}$

これは、Tutte多項式を共階数零または階数生成多項式の評価として表現したものである。^[35]

${\displaystyle R_{M}(u,v)=\sum _{S\subseteq E}u^{r(M)-r(S)}v^{|S|-r(S)}~.}$

この定義から、特性多項式は、単純な因数を除いて、具体的には、 ${\displaystyle T_{M}\ ,}$

${\displaystyle p_{M}(\lambda )=(-1)^{r(M)}T_{M}(1-\lambda ,0)~.}$

もう一つの定義は、内部活動と外部活動、および基底の合計という観点からであり、基底の数であるという事実を反映している。^[36]これは、より少ないサブセットの合計であるがより複雑な用語を持ち、タットの元の定義であった。 ${\displaystyle T(1,1)}$

削除と短縮による再帰の観点からのさらなる定義がある。^[37]削除短縮の同一性は

${\displaystyle F(M)=F(M-e)+F(M/e)}$

がループでもコロコップでもないとき。この再帰と乗法条件を満たすマトロイドの不変量（つまり、同型マトロイド上で同じ値を取る関数） ${\displaystyle e}$

${\displaystyle F(M\oplus M')=F(M)F(M')}$

はトゥット＝グロタンディーク不変量と言われている。^[35]トゥット多項式は最も一般的な不変量である。つまり、トゥット多項式はトゥット＝グロタンディーク不変量であり、そのような不変量はすべてトゥット多項式の評価である。^[31]

グラフの Tutte 多項式は、そのサイクルマトロイドの Tutte多項式です 。 ${\displaystyle T_{G}}$${\displaystyle T_{M(G)}}$

無限マトロイドの理論は有限マトロイドの理論よりもはるかに複雑で、独自の主題を形成しています。長い間、困難の 1 つは、合理的で有用な定義が多数存在し、そのどれもが有限マトロイド理論の重要な側面をすべて捉えているようには見えなかったことです。たとえば、基底、回路、および双対性を無限マトロイドの 1 つの概念にまとめることは困難であるように思われます。

無限マトロイドの最も単純な定義は、有限ランクを要求することです。つまり、Eのランクは有限です。この理論は、有限ランクの無限マトロイドの双対が有限ランクを持たないという事実による双対性の失敗を除いて、有限マトロイドの理論に似ています。有限ランクのマトロイドには、有限次元ベクトル空間と有限超越次数の体拡大の任意のサブセットが含まれます。

次に単純な無限一般化は有限マトロイドであり、プレジオメトリとも呼ばれる。無限の基底集合を持つマトロイドは、次の性質を持つ場合 有限である。

${\displaystyle x\in \operatorname {cl} (Y)\ \Leftrightarrow \ {\text{ there is a finite set }}Y'\subseteq Y{\text{ such that }}x\in \operatorname {cl} (Y').}$

同様に、すべての従属集合には有限の従属集合が含まれます。

例としては、無限次元ベクトル空間の任意の部分集合の線型従属（ただし、ヒルベルト空間やバナッハ空間のような無限従属ではない）や、おそらく無限の超越次数を持つ体拡大の任意の部分集合における代数従属がある。また、有限マトロイドのクラスは自己双対ではない。有限マトロイドの双対は有限ではないからである。

有限無限マトロイドは、代数学と密接な関係のある数学論理学の分野であるモデル理論で研究されています。

1960 年代後半、マトロイド理論家は、有限マトロイドのさまざまな側面を共有し、その双対性を一般化する、より一般的な概念を求めました。この課題に応えて、無限マトロイドの多くの概念が定義されましたが、問題は未解決のままでした。DA ヒッグスが検討したアプローチの 1 つはB マトロイドとして知られるようになり、1960 年代と 1970 年代にヒッグス、オクスリー、その他によって研究されました。Bruhn ら (2013) による最近の結果によると、それは問題を解決します。彼らは独立して同じ概念に到達し、独立性、基底、回路、閉包、およびランクに関して 5 つの同等の公理系を提供しました。B マトロイドの双対性は、無限グラフで見られる双対性を一般化します。

独立公理は次のとおりです。

1. 空集合は独立しています。
2. 独立集合のすべての部分集合は独立しています。
3. 任意の非最大（集合包含下）独立集合および最大独立集合に対して、が独立であるような が存在する。${\displaystyle \ I\ }$${\displaystyle \ J\ }$${\displaystyle \ x\in J\smallsetminus I\ }$${\displaystyle \ I\cup \{x\}\ }$
4. 基底空間の任意の部分集合に対して、 の任意の独立部分集合はの最大独立部分集合に拡張できる。${\displaystyle \ X\ }$${\displaystyle \ I\ }$${\displaystyle \ X\ }$${\displaystyle \ X~.}$

これらの公理により、すべてのマトロイドには双対が存在します。

マトロイド理論はホイットニー（1935）によって導入されました。また、中沢健夫によって独立に発見されましたが、彼の研究は長年忘れられていました（西村・黒田（2009））。

ホイットニーは独創的な論文で、独立性に関する 2 つの公理を提示し、これらの公理に従うあらゆる構造を「マトロイド」と定義しました。^[c] 彼の重要な観察は、これらの公理がグラフと行列の両方に共通する「独立性」の抽象化を提供しているというものでした。このため、マトロイド理論で使用される用語の多くは、線形代数やグラフ理論の類似概念の用語に似ています。

ホイットニーが初めてマトロイドについて書いた直後、マックレーン (1936) がマトロイドと射影幾何学の関係について重要な論文を執筆しました。1年後、ファン・デル・ワールデン (1937) は、現代代数学の古典的な教科書の中で、代数的依存性と線形依存性の類似点を指摘しました。

1940 年代にリチャード・ラドーは横断理論を視野に入れた「独立システム」という名前でさらなる理論を展開しました。この分野では、彼がこの分野に付けた名前が今でも時々使われています。

1950年代、WTタットはマトロイド理論の第一人者となり、その後も長年その地位を維持した。彼の貢献は多岐にわたり、

• 排除されたマイナーによるバイナリ、正則、およびグラフィックマトロイドの特徴付け

• 正則マトロイド表現可能性定理

• 連鎖群とそのマトロイドの理論

そして彼が多くの結果を証明するために使用したツール:

• 「経路定理」

• 「トゥッテのホモトピー定理」 (Tutte (1965) などを参照)

これらは非常に複雑なため、後の理論家たちは証明においてこれらを必要としないようにするために多大な努力を払った。^[d]

Crapo (1969) と Brylawski (1972) は、現在Tutte 多項式(Crapo により命名)として知られるグラフ多項式である Tutte の「二色性」をマトロイドに一般化しました。彼らの研究に続いて、最近 (特に 2000 年代) 大量の論文が発表されていますが、グラフの Tutte 多項式に関する論文ほど多くはありません。

1976 年にドミニク・ウェルシュはマトロイド理論に関する最初の包括的な本を出版しました。

ポール・シーモアの正則マトロイドの分解定理 (シーモア (1980)) は、1970 年代後半から 1980 年代にかけての最も重要かつ影響力のある研究でした。カーンとクン (1982) によるもう 1 つの基本的な貢献は、射影幾何学とダウリング幾何学がマトロイド理論で重要な役割を果たす理由を示しました。

1980 年代までに、他にも多くの重要な貢献者がいましたが、有理数上で表現可能な 2 元マトロイドの Tutte による特徴付け (Whittle 1995) を 3 元マトロイドに拡張した Geoff Whittle についても言及しないわけにはいきません。これはおそらく 1990 年代の最大の貢献です。

現在（2000年頃以降）では、 Geelen、Gerards、Whittleらによるマトロイドマイナープロジェクト^[e]が マトロイドの構造理論に大きな進歩をもたらしました。他の多くの人々もマトロイド理論のその部分に貢献しており、この理論は（21世紀の最初の10年と20年のうちに）繁栄しています。

マトロイドの研究を開拓した数学者には、

その他の主な貢献者には、

• 反マトロイド – 反交換公理を持つ順序または集合の数学的体系
• コクセターマトロイド – マトロイドの群論的一般化
• Greedoid  – 貪欲最適化で使用されるセットシステム
• 有向マトロイド – 順序付き線形代数の抽象化
• ポリマトロイド – マトロイドの多重集合類似体
• プレジオメトリ（モデル理論）  – 閉包演算子を用いたマトロイドの定式化

• 「マトロイド」。数学百科事典。EMS Press。2001 [1994]。

• キングアン、サンドラ。「マトロイド理論」。userhome.brooklyn.cuny.edu (学術個人サイト)。ブルックリン カレッジ。ブルックリン、ニューヨーク:ニューヨーク市立大学。— マトロイド論文、マトロイド ソフトウェア、リンクの大規模な参考文献。

• Locke, SC「貪欲アルゴリズム」。math.fau.edu (学術個人サイト)。フロリダ州ボカラトン:フロリダ アトランティック大学。

• Pagano, Steven R. 「マトロイドと符号付きグラフ」。math.binghamton.edu (学術個人サイト)。ニューヨーク州ビンガムトン:ビンガムトン大学。

• Hubenthal, Mark. 「マトロイドの簡単な説明」(PDF)。math.washington.edu (学術個人サイト) 。シアトル、ワシントン州:ワシントン大学。2010年 8 月 12 日のオリジナル( PDF)からアーカイブ。— この記事の記述の証明を示します。

• Oxley, James. 「マトロイドとは何か?」(PDF) . math.lsu.edu (学術個人サイト) . バトン ルージュ、ルイジアナ州:ルイジアナ州立大学.

• ホワイト、ニール編 (1992b)。マトロイドアプリケーション。ケンブリッジ大学出版局。ISBN 978-0-5213-8165-9. ISSN  0953-4806 – Google ブックス経由。