ガモイド

数学の一分野であるマトロイド理論において、ガモイドはマトロイドの一種であり、有向グラフ内の頂点が互いに素な経路で到達できる頂点の集合を記述します。

ガモイドの概念は、分離した経路のシステムの存在に対する障害を特徴付けるメンガーの定理 に関連する考察に基づいて、ヘイゼル・パーフェクト（1968）によって導入され、マトロイドであることが示されました。 ^{[1]ガモイドはピム（1969） [2]}によって命名され、メイソン（1972）によってより詳細に研究されました。^[3]

を有向グラフ、を始点の集合、を終点の集合（ と必ずしも交わらない）とします。このデータから導出されるガモイドは、その要素の集合として を持ちます。のサブセットがで独立であるとは、始点がすべて に属し、終点がちょうど であるような頂点が交わらない経路の集合が存在する場合です。^[4]${\displaystyle G}$${\displaystyle S}$${\displaystyle T}$${\displaystyle S}$${\displaystyle \ガンマ}$${\displaystyle T}$${\displaystyle I}$${\displaystyle T}$${\displaystyle \ガンマ}$${\displaystyle S}$${\displaystyle I}$

厳密なガモイドとは、目的頂点の集合が内のすべての頂点で構成されるガモイドである。したがって、ガモイドは厳密なガモイドの要素のサブセットへの制限である。^{[4] [5]}${\displaystyle T}$${\displaystyle G}$

要素の集合上の一様マトロイド を考えてみましょう。このマトロイドでは、各集合またはそれ以下の要素が独立しています。このマトロイドをガモイドとして表現する 1 つの方法は、2 分割の片側に頂点の集合、2 分割のもう一方の側に頂点の集合、すべての辺が から に向いている完全な 2 部グラフを形成することです。このグラフでは、 のサブセットは、 またはそれ以下の頂点がある場合に限り、1 組の分離パスのエンドポイントの集合です。それ以外の場合は、 にパスを開始するのに十分な頂点がありません。このグラフの特殊な構造は、一様マトロイドがガモイドであると同時に横断マトロイドであることを示しています。 ^[6]${\displaystyle U{}_{n}^{r}}$${\displaystyle n}$${\displaystyle r}$ ${\displaystyle K_{r,n}}$${\displaystyle S}$${\displaystyle r}$${\displaystyle T}$${\displaystyle n}$${\displaystyle S}$${\displaystyle T.}$${\displaystyle T}$${\displaystyle r}$${\displaystyle S}$

あるいは、同じ一様マトロイドを、頂点のサブセットを選択し、選択した各頂点をグラフ内の他のすべての頂点に接続することで、頂点のみを持つ小さなグラフ上のガモイドとして表すこともできます。この場合も、グラフの頂点のサブセットが互いに素なパスの終点になることができるのは、頂点の数が またはそれ以下である場合のみです。それ以外の場合は、パスの始点になる頂点が足りないためです。このグラフでは、すべての頂点がマトロイドの要素に対応しており、一様マトロイドが厳密なガモイドであることを示しています。^[7]${\displaystyle U{}_{n}^{r}}$${\displaystyle n}$${\displaystyle S}$${\displaystyle r}$${\displaystyle r}$

グラフと頂点部分集合から定義されるガモイド内の集合の階数は、定義により、 から への頂点が互いに素な経路の最大数である。メンガーの定理により、階数は からへのすべての経路と交差する集合の最小濃度とも等しい。^[4]${\displaystyle X\subset T}$${\displaystyle G}$${\displaystyle S}$${\displaystyle T}$${\displaystyle S}$${\displaystyle X}$${\displaystyle Y}$${\displaystyle S}$${\displaystyle X}$

横断マトロイドは、集合の族から定義されます。その要素は集合の要素であり、これらの要素の集合は、の要素と、それらを含む互いに素な集合との 1 対 1 のマッチングが存在する場合、つまり、別個の代表のシステムが存在する場合に、独立しています。同様に、横断マトロイドは、各集合に対して に頂点、各要素に対して に頂点、各集合からそれに含まれる各要素への辺を持つ有向 二部グラフから定義される、特殊な種類のガモイドで表すことができます。${\displaystyle X}$${\displaystyle X}$ ${\displaystyle (S,T,E)}$${\displaystyle S}$${\displaystyle T}$

それほど自明ではないが、厳密なガモイドは、まさに横断マトロイドの双対マトロイドである。すべての厳密なガモイドが横断マトロイドの双対であることを確認するために、を有向グラフと開始頂点集合から定義された厳密なガモイドとし、各頂点 に対する集合の族 に対する横断マトロイドについて考える。ここで、頂点 は、 に等しいか への辺を持つ場合にに属する。からの互いに素なパスの集合の端点で構成される厳密なガモイドの任意の基底は、各 を がパス辺である頂点 ( がパスの1 つに参加していない場合は 自身) に一致させる、横断マトロイドの基底の補基底である。逆に、各 の代表で構成される横断マトロイドのすべての基底は、辺の集合 によって形成されるパスの端点で構成される厳密なガモイドの補基底を生じさせる。この結果はイングルトンとピフによるものである。^{[4] [8]}${\displaystyle \gamma}$${\displaystyle G}$${\displaystyle S}$${\displaystyle N_{v}}$${\displaystyle v\in V(G)\setminus S}$${\displaystyle u}$${\displaystyle N_{v}}$${\displaystyle v}$${\displaystyle v}$${\displaystyle |S|}$${\displaystyle S}$${\displaystyle N_{v}}$${\displaystyle u}$${\displaystyle uv}$${\displaystyle v}$${\displaystyle v}$${\displaystyle u_{v}}$${\displaystyle N_{v}}$${\displaystyle u_{v}v}$

逆に、すべての横断マトロイドが厳密なガモイドと双対であることを確認するには、マトロイドを定義する集合のサブファミリーを見つけます。このサブファミリーは、異なる代表のシステムを持ち、同じマトロイドを定義します。集合の和集合を頂点とし、同じ集合の他のメンバーから各集合の代表要素への辺を持つグラフを形成します。すると、各代表要素に対して上記のように形成された集合は、元の横断マトロイドを定義する集合とまったく同じになり、このグラフと代表要素の集合によって形成される厳密なガモイドは、与えられた横断マトロイドと双対になります。^{[4] [8]}${\displaystyle N_{v}}$${\displaystyle v}$

イングルトン・ピフ定理の簡単な帰結として、すべてのガモイドは横断マトロイドの縮約である。ガモイドは横断マトロイドを含み、双対性とマイナーの適用に関して閉じているマトロイドの最小のクラスである。^{[4] [9] [10]}

すべてのガモイドが正則である、つまりすべての体で表現可能であるというのは真実ではない。特に、一様マトロイドはバイナリマトロイドではなく、より一般的には-点線は個以上の要素を持つ体でのみ表現できる。しかし、すべてのガモイドはほぼすべての有限体で表現できる。^{[3] [4]}より具体的には、要素セットを持つガモイドは少なくとも 個の要素を持つすべての体で表現できる。^{[4] [11] [12]}${\displaystyle U{}_{4}^{2}}$${\displaystyle n}$${\displaystyle U{}_{n}^{2}}$${\displaystyle n-1}$${\displaystyle S}$${\displaystyle 2^{|S|}}$