双対マトロイド

マトロイド理論では、マトロイドの双対とは、と同じ要素を持つ別のマトロイドであり、集合が独立である場合、かつその集合と基底集合が互いに素である場合に限ります。^{[1] [2] [3]}${\displaystyle M}$${\displaystyle M^{\ast}}$${\displaystyle M}$${\displaystyle M}$

マトロイド双対は、マトロイドを定義したハスラー・ホイットニーの最初の論文に遡ります。^[4]彼らは平面グラフ双対性の概念をマトロイドに一般化しました。

二重性は反転である。すべての に対して、である。^{[1] [3] [4]}${\displaystyle M}$${\displaystyle (M^{\ast })^{\ast }=M}$

双対マトロイドの別の定義は、その基底集合がの基底集合の補集合であるというものである。基底からマトロイドを定義するために使用される基底交換公理は自己補完的であるため、マトロイドの双対は必然的にマトロイドである。^[3]${\displaystyle M}$

の平面はの巡回集合（回路の和集合）と補完的であり、逆もまた同様である。^[3]${\displaystyle M}$${\displaystyle M^{\ast }}$

が基底集合 上のマトロイドのランク関数である場合、双対マトロイドのランク関数は である。^{[1] [3] [4]}${\displaystyle r}$${\displaystyle M}$${\displaystyle E}$${\displaystyle r^{\ast }(S)=r(E\setminus S)+|S|-r(E)}$

マトロイドマイナーは、2つの操作によってより大きなマトロイドから形成されます。制約は、残りのセットの独立性やランクを変更せずにから要素を削除します。縮約は、それが属するすべてのセットのランクから1を減算した後に から要素を削除します。これら2つの操作は双対です。つまり、と です。したがって、双対のマイナーは、マイナーの双対と同じものです。^[5]${\displaystyle M}$${\displaystyle M\setminus x}$${\displaystyle x}$${\displaystyle M}$${\displaystyle M/x}$${\displaystyle x}$${\displaystyle M}$${\displaystyle M\setminus x=(M^{\ast }/x)^{\ast }}$${\displaystyle M/x=(M^{\ast }\setminus x)^{\ast }}$

個々のマトロイドは、自身の双対と同型である場合に自己双対である（例えば、グラフィックマトロイドの自己双対多面体を一般化する）。同型性はマトロイドの要素を固定したままにしてもよいが、そうしなくてもよい。独立オラクルを介してマトロイドにアクセスできる、与えられたマトロイドが自己双対であるかどうかをテストするアルゴリズムは、指数関数的な数のオラクルクエリを実行する必要があり、したがって多項式時間で実行できない。^[6]

多くの重要なマトロイド族は自己双対です。つまり、マトロイドが族に属するのは、その双対が族に属する場合のみです。他の多くのマトロイド族は双対ペアになっています。この現象の例には次のものがあります。

• バイナリマトロイド（ GF(2)上で表現可能なマトロイド）、他の任意の体上で表現可能なマトロイド、および正則マトロイドはすべて自己双対族である。^[7]
• ガモイドは自己双対族を形成する。厳密なガモイドは横断マトロイドと双対である。^[8]
• 一様マトロイドと分割マトロイドは自己双対である。一様マトロイドの双対は一様マトロイドである。^[9]${\displaystyle U{}_{n}^{r}}$${\displaystyle U{}_{n}^{n-r}}$
• グラフィックマトロイドの双対は、基礎となるグラフが平面グラフである場合にのみ、それ自体がグラフィックである。平面グラフの双対のマトロイドは、グラフのマトロイドの双対と同じである。したがって、平面グラフのグラフィックマトロイドの族は自己双対である。^[10]
• グラフィックマトロイド、より一般的にはバイナリマトロイドの中で、二部マトロイド（すべての回路が偶数であるマトロイド）はオイラーマトロイド（互いに素な回路に分割できるマトロイド）の双対である。^{[11] [12]}

代数マトロイド族が自己双対であるかどうかは未解決の問題です。

Vがベクトル空間でV *がその直交補空間である場合、Vの線型マトロイドとV *の線型マトロイドは双対である。系として、任意の線型マトロイドの双対は線型マトロイドである。^[13]

• クン、ジョセフ PSv 編 (1986)、マトロイド理論のソースブック、ボストン: バークハウザー、doi :10.1007/978-1-4684-9199-9、ISBN 978-0-8176-3173-4、MR  0890330。