マトロイド

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

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

• （I2）独立集合のすべての部分集合は独立である。すなわち、各${\displaystyle A'\subseteq A}$、 もし${\displaystyle A\in {\mathcal {I}}}$それから${\displaystyle A'\in {\mathcal {I}}}$これは、遺伝的性質、または下方閉包性質と呼ばれることもあります。

• （I3）もし${\displaystyle A}$そして${\displaystyle B}$は 2 つの独立した集合であり (つまり、各集合は独立しており)、${\displaystyle A}$要素が${\displaystyle B}$すると、${\displaystyle x\in A\setminus B}$そのため${\displaystyle B\cup \{x\}}$は独立である。これは、拡張性または独立集合交換性と呼ばれることもある（シュタイニッツ交換補題を参照）。

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

グラウンドセットのサブセット${\displaystyle E}$独立していないものは従属と呼ばれます。

最大独立集合、つまり、要素を追加すると依存するようになる独立集合${\displaystyle E}$―これはマトロイドの基底と呼ばれます。

マトロイド内の回路${\displaystyle M}$は、の最小依存部分集合である。${\displaystyle E}$すなわち、真部分集合がすべて独立である従属集合である。この用語は、グラフィカルマトロイドの回路が対応するグラフのサイクルであることから生じる。^{[ 4 ]}

マトロイドの従属集合、基底、または回路は、マトロイドを完全に特徴づけます。集合が独立であるのは、それが従属でない場合、基底の部分集合である場合、および回路を含まない場合に限ります。従属集合、基底、および回路の集合はそれぞれ、マトロイドの公理として採用できる単純な性質を持っています。例えば、マトロイドを定義することができます。${\displaystyle M}$ペアになる${\displaystyle (E,{\mathcal {B}})}$、 どこ${\displaystyle E}$は以前と同様に有限集合であり、$\displaystyle {\mathcal {B}}}$は、サブセットの集合です。${\displaystyle E}$基底と呼ばれるもので、以下の性質を持つ。^{[ 4 ]}

• （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つの基底が${\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)}$マトロイドは、以下の特性を持つ。^{[ 4 ]}

• （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）任意の集合に対して${\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).}$

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

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

• （F1）全得点${\displaystyle E}$閉店しました。

• （F2）もし${\displaystyle S}$そして${\displaystyle T}$フラットの場合、${\displaystyle S\cap T}$フラットです。

• （F3）もし${\displaystyle S}$はフラットなので、各要素は${\displaystyle E\smallsetminus S}$まさにそのアパートの1つにあります${\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}$。

ランクのマトロイドにおいて${\displaystyle r}$ランクの高いフラット${\displaystyle r-1}$はハイパープレーン、またはコアトム、コポイントと呼ばれます。これらは最大の真のフラットです。つまり、ハイパープレーンの唯一のスーパーセットでフラットでもあるのは、セット です。${\displaystyle E}$マトロイドのすべての要素のうち。同等の定義としては、コートムとは、Mを張らないが、他の要素を追加すると張る集合になるようなEの部分集合である。 ^{[ 6 ]}

家族${\displaystyle {\mathcal {H}}}$マトロイドの超平面には次の性質があり、これはマトロイドの別の公理化とみなすことができる。^{[ 6 ]}

• （H1）グラウンドセット${\displaystyle E}$それ自体は超平面ではない。

• （H2）異なる集合は存在しない${\displaystyle X}$そして${\displaystyle Y}$で${\displaystyle {\mathcal {H}}}$と${\displaystyle X\subseteq Y}$つまり、超平面はスペルナー族を形成する。

• （H3）すべての${\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}$。

Minty (1966)は、グラフォイドを三つ組として定義した。${\displaystyle (L,C,D)}$その中で${\displaystyle C}$そして${\displaystyle D}$は、空でない部分集合のクラスである。${\displaystyle L}$そのため

• （G1）要素なし${\displaystyle C}$（「回路」と呼ばれる）には別の回路が含まれており、

• （G2）要素なし${\displaystyle D}$（「コサーキット」と呼ばれる）には別の回路が含まれており、

• （G3）セットなし${\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}$。

させて${\displaystyle E}$有限集合であり、${\displaystyle k}$自然数。マトロイドは次のように定義できる。${\displaystyle E}$あらゆる手段を講じることで${\displaystyle k}$要素サブセット${\displaystyle E}$基礎となる。これはランクの均一マトロイドとして知られている。${\displaystyle k}$ランクが一定の均一なマトロイド${\displaystyle k}$そして${\displaystyle n}$要素は次のように表されます${\displaystyle U_{k,n}}$ランクが2以上のすべての均一マトロイドは単純である（§ 追加用語を 参照）。ランク2の均一マトロイドは${\displaystyle n}$ポイントは${\displaystyle n}$ 点線。マトロイドは、そのマトロイドのランクに1を加えた値より小さいサイズの回路を持たない場合に限り、一様である。一様マトロイドの直和は、分割マトロイドと呼ばれる。

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

マトロイド理論は、主にベクトル空間における独立性と次元の性質を深く考察することから発展した。このように定義されたマトロイドを表現する方法は2つある。

もし${\displaystyle E}$ベクトル空間の任意の有限部分集合${\displaystyle V}$すると、マトロイドを定義できる${\displaystyle M}$の上${\displaystyle E}$独立集合を取ることによって${\displaystyle M}$線形独立な部分集合である${\displaystyle E}$。

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

もし${\displaystyle M}$このように定義できるマトロイドを、集合と呼びます。${\displaystyle E}$表現する${\displaystyle M}$。

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

このように定義されたマトロイドの重要な例として、ファノマトロイドが挙げられます。ファノマトロイドは、ファノ平面 から派生したランク3のマトロイドで、7つの点（マトロイドの7つの要素）と7つの線（マトロイドの適切な非自明な平面）を持つ有限幾何学です。これは線形マトロイドであり、その要素は有限体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}$実数表現可能であるとは、実数上で表現可能であることを意味します。例えば、グラフマトロイド（下記参照）はグラフで表現されますが、任意の体上のベクトルによっても表現可能です。

マトロイド理論における基本的な問題は、与えられた体上で表現可能なマトロイドを特徴づけることである。${\displaystyle F;}$Rota の予想は、すべての有限体に対する可能な特徴付けを記述しています。これまでの主な結果は、 Tutte (1950 年代) によるバイナリ マトロイド(GF(2) 上で表現可能なもの)の特徴付け、Reid と Bixby およびSeymour (1970 年代)による三元マトロイド (3 元体上で表現可能なもの) の特徴付け、 Geelen、Gerards 、 Kapoor (2000 )による四元マトロイド (4 元体上で表現可能なもの) の特徴付けです。Rota の予想の証明は、2014 年に Geelen、Gerards、Whittle によって発表されましたが、出版されていません。^{[ 7 ]}  

正則マトロイドとは、あらゆる体上で表現可能なマトロイドのことである。ヴァーモス・マトロイドは、どの体上でも表現不可能なマトロイドの最も単純な例である。

マトロイド理論のもう一つの起源はグラフ理論である。

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

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

• グラフの双円マトロイドは、連結部分集合が最大で 1 つのサイクルを含む場合に、辺の集合を独立と呼ぶことによって定義されます。つまり、辺の集合は、擬似森林である場合に限り独立です。

• 有向グラフまたは無向グラフにおいて${\displaystyle G}$させて${\displaystyle E}$そして${\displaystyle F}$2 つの異なる頂点集合とする。${\displaystyle E}$部分集合を定義する${\displaystyle U}$独立するには${\displaystyle |U|}$頂点が互いに素なパス${\displaystyle F}$に${\displaystyle U}$これは、上のマトロイドを定義します。${\displaystyle E}$ガンモイドと呼ばれる: ^{[ 9 ]}厳密なガンモイドとは、集合が${\displaystyle E}$は、${\displaystyle G}$[ ^{10 ]​}

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

• グラフマトロイドは、符号付きグラフ、ゲイングラフ、バイアス付きグラフからのマトロイドに一般化されている。${\displaystyle G}$優れた線形クラス${\displaystyle {\mathcal {B}}}$サイクルの集合は「偏りのあるグラフ」として知られている。${\displaystyle (G,{\mathcal {B}})}$は、バイアスグラフのフレームマトロイドとリフトマトロイドとして知られる2つのマトロイドを持つ。

すべてのサイクルが特別なクラスに属する場合、これらのマトロイドはサイクルマトロイドと一致します。${\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}$。

部分集合を定義する${\displaystyle S}$の${\displaystyle E}$拡張体が代数的に独立である場合${\displaystyle F(S)}$超越度は${\displaystyle |S|}$[ ^{13 ]​}

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

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

双対は、マトロイドを定義する他の方法を用いて同様にうまく説明できる。例えば、次のようになる。

• 集合は独立している${\displaystyle M^{*}}$その補集合が張る場合に限る${\displaystyle M}$。

• セットは回路である${\displaystyle M^{*}}$その補集合がコートムである場合に限る${\displaystyle M}$。

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

クラトフスキーの定理のマトロイド版によると、グラフィック マトロイドの双対${\displaystyle M}$グラフィックマトロイドであるのは、${\displaystyle M}$は平面グラフのマトロイドです。この場合、の双対は${\displaystyle M}$は、双対グラフのマトロイドである。${\displaystyle G}$[ ^{16 ]特定の}体上で表現可能なベクトルマトロイドの双対${\displaystyle F}$も表現可能${\displaystyle F}$横断マトロイドの双対は厳密ガモイドであり、その逆もまた然りである。

例

グラフのサイクルマトロイドは、そのグラフのボンドマトロイドの双対マトロイドである。

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

線形代数では、これはSのベクトルによって生成される部分空間に制限することに対応します。同様に、T = M − Sの場合、これはTの削除と呼ばれ、M \ TまたはM − Tと表記されます。M のサブマトロイドは、削除のシーケンスの結果であり、順序は関係ありません。^{[ 17 ] [ 18 ]}

制限の双対操作は縮約である。^{[ 19 ]} TがEの部分集合である場合、MのTによる縮約、M / Tと表記されるものは、基底集合E − T上のマトロイドであり、そのランク関数は  ${\displaystyle r'(A)=r(A\cup T)-r(T)}$[ ^{20 ]}線形代数では、これはT のベクトルによって生成される線形空間による商空間と、 E − Tのベクトルの像を一緒に^調べることに相当します。  

一連の制限および縮約操作によってMから得られるマトロイドNは、 Mのマイナーと呼ばれます。^{[ 18 ] [ 21 ]} MはNをマイナーとして含む と言います。多くの重要なマトロイド族は、その族に属さないマイナー最小マトロイドによって特徴付けられることがあります。これらは禁止マイナーまたは除外マイナーと呼ばれます。^{[ 22 ]}

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

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

Mの特性多項式（彩色多項式とも呼ばれるが、彩色は考慮しない）は次のように定義される。^{[ 32 ]}

${\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について取られる。^{[ 33 ]}

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

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

• Mが線形超平面の配置AのマトロイドM ( A )である場合${\displaystyle \mathbb {R} ^{n}}$（またはF ⁿでFは任意の体）配置の特性多項式はp _A  ( λ ) = λ ^{n − r ( M )} p _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)}$。

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

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

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

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

これは、${\displaystyle M}$および特性${\displaystyle M^{*}}$タット多項式の定義の一つは、

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

これは、タッテ多項式を共ランク零性またはランク生成多項式の評価として表現する^{[ 36 ]}。

${\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).}$

別の定義は、内部活動と外部活動、および基数に関する合計という観点から、${\displaystyle T(1,1)}$は基数です。^{[ 37 ]}これは、より少ない部分集合について合計しますが、より複雑な項があり、Tutte の元の定義です。

削除と縮約による再帰に関するさらなる定義がある。^{[ 38 ]}削除縮約恒等式は

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

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

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

はTutte–Grothendieck 不変量であると言われています。^{[ 36 ]} Tutte 多項式は、そのような不変量の中で最も一般的なものです。つまり、Tutte 多項式は Tutte–Grothendieck 不変量であり、そのような不変量はすべて Tutte 多項式の評価です。^{[ 32 ]}

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