アンチマトロイド

数学において、反マトロイドとは、集合が要素を一つずつ含めることで構築され、その集合に含まれる要素は、含められるまで利用可能であり続ける過程を記述する形式体系である。 ^[1]反マトロイドは、そのような過程の可能な状態をモデル化する集合体系として、または要素が含まれる可能性のある異なるシーケンスをモデル化する 形式言語として、 2つの同等の方法で公理化されるのが一般的である。ディルワース(1940) は、格子理論に基づく別の公理化を用いて反マトロイドを研究した最初の人物であり、反マトロイドは他の文脈でも頻繁に再発見されている。^[2]

集合システムとしての反マトロイドを定義する公理は、マトロイドの公理と非常に似ていますが、マトロイドが交換公理によって定義されるのに対し、反マトロイドは、その名前の由来となった反交換公理によって定義されます。反マトロイドは、グリードイドおよび半モジュラー格子の特殊なケース、および半順序および分配格子の一般化として見ることができます。反マトロイドは、相補性によって、幾何学における凸集合の組み合わせ的抽象化である凸幾何学と同等です。

反マトロイドは、スケジューリング問題における先行制約、シミュレーションにおける潜在的なイベントシーケンス、人工知能におけるタスク計画、および人間の学習者の知識の状態 をモデル化するために適用されてきました。

反マトロイドは、実行可能集合と呼ばれる有限集合の有限族として定義され、次の2つの性質を持つ：^[3]${\displaystyle {\mathcal {F}}}$

• 任意の 2 つの実行可能集合の和集合も実行可能です。つまり、和集合に対して閉じています。${\displaystyle {\mathcal {F}}}$
• が空でない実行可能集合である場合、 には、（から を除いた集合）も実行可能である要素が含まれます。つまり、はアクセス可能な集合システムです。${\displaystyle S}$${\displaystyle S}$${\displaystyle x}$${\displaystyle S\setminus \{x\}}$${\displaystyle x}$${\displaystyle S}$${\displaystyle {\mathcal {F}}}$

反マトロイドは形式言語、つまり有限の記号アルファベットから定義された文字列の集合として同等の定義も持つ。この集合に属する文字列は言語の単語と呼ばれる。反マトロイドを定義する言語は、以下の特性を満たす必要がある: ^[4]${\displaystyle {\mathcal {L}}}$

• アルファベットのすべての記号は、 の少なくとも 1 つの単語に出現します。${\displaystyle {\mathcal {L}}}$
• の各単語には各記号が最大で1つずつ含まれます。この性質を持つ言語は正規言語と呼ばれます。^[5]${\displaystyle {\mathcal {L}}}$
• 英語の単語の接頭辞はすべて、ドイツ語にも存在します。この性質を持つ言語は遺伝性言語と呼ばれます。^[5]${\displaystyle {\mathcal {L}}}$${\displaystyle {\mathcal {L}}}$
• および が内の単語であり、に含まれない記号を少なくとも 1 つ含む場合、 には 内の別の単語となる記号が存在します。${\displaystyle S}$${\displaystyle T}$${\displaystyle {\mathcal {L}}}$${\displaystyle S}$${\displaystyle T}$${\displaystyle x}$${\displaystyle S}$ ${\displaystyle Tx}$${\displaystyle {\mathcal {L}}}$

これら 2 つの定義形式の同値性は、次のように考えることができます。 が形式言語として定義された反マトロイドである場合、 の語の記号集合はアクセス可能な和集合閉集合システムを形成します。これは文字列の遺伝的性質によってアクセス可能であり、文字列の連結性質を繰り返し適用することで和集合閉であることが示されます。逆に、アクセス可能な和集合閉集合システムから 、接頭辞のすべてが に属する記号集合を持つ通常の文字列の言語は、形式言語が反マトロイドであるための要件を満たします。これら 2 つの変換は互いに逆です。つまり、形式言語を集合族に変換して戻すか、その逆を行うと、同じシステムが生成されます。したがって、これら 2 つの定義は、数学的に同値なオブジェクトのクラスにつながります。^[6]${\displaystyle {\mathcal {L}}}$${\displaystyle {\mathcal {L}}}$${\displaystyle {\mathcal {F}}}$${\displaystyle {\mathcal {F}}}$

次のシステムは反マトロイドの例を示しています。

チェーン反マトロイド

単一の文字列の接頭辞と、これらの接頭辞に含まれる記号の集合は、反マトロイドを形成する。例えば、文字列によって定義される鎖反マトロイドは、その形式言語として文字列の集合（ここで、は空文字列を表す）を持ち、その実行可能集合の族として族^{[7]を持つ。}${\displaystyle abcd}$$${\displaystyle \{\varepsilon,a,ab,abc,abcd\}}$$${\displaystyle \epsilon }$ $${\displaystyle {\bigl \{}\emptyset ,\{a\},\{a,b\},\{a,b,c\},\{a,b,c,d\}{\bigr \}}.}$$

ポセット反マトロイド

有限な半順序集合の下位集合は反マトロイドを形成し、反マトロイドの全長ワードは半順序の線形拡張を形成する。 ^{[8]分配格子に対する}バーコフの表現定理によれば、ポセット反マトロイド（集合包含によって順序付けられている）の実行可能集合は分配格子を形成し、すべての分配格子はこのようにして形成することができる。したがって、反マトロイドは分配格子の一般化と見なすことができる。連鎖反マトロイドは、全順序に対するポセット反マトロイドの特殊なケースである。^[7]

反マトロイドの砲撃

ユークリッド平面または高次元ユークリッド空間内の有限の点の集合の殻列は、凸包の頂点を繰り返し削除することによって形成される。これらの列によって形成される反マトロイドの実現可能集合は、凸集合の補集合との交差である。^[7]${\displaystyle U}$${\displaystyle U}$

完璧な排除

弦グラフの完全消去順序とは、各頂点に対して、順序付けで後に出現するの隣接頂点がクリーク を形成するような頂点の順序付けである。弦グラフの完全消去順序付けの接頭辞は反マトロイドを形成する。^[9]${\displaystyle v}$${\displaystyle v}$${\displaystyle v}$

チップ発射ゲーム

アーベル砂山モデルのようなチップ発射ゲームは、有向グラフとその頂点に置かれた「チップ」のシステムによって定義される。頂点のチップの数が からの辺の数以上であれば、を発射して、隣接する各頂点に 1 つのチップを移動することができる。回発射されるイベントは、すでに回発射され、合計チップが蓄積されている場合にのみ発生する。これらの条件は、以前の発射の順序に依存せず、 が発射されるまで真であるため、システムが終了する任意のグラフとチップの初期配置は、ペア 上の反マトロイドを定義する。これらのシステムの反マトロイド特性の結果として、与えられた初期状態に対して、各頂点が発射される回数とシステムの最終的な安定状態は、発射順序に依存しない。^[10]${\displaystyle v}$${\displaystyle v}$ ${\displaystyle v}$${\displaystyle v}$${\displaystyle i}$${\displaystyle i-1}$${\displaystyle i\cdot \deg(v)}$${\displaystyle v}$${\displaystyle (v,i)}$

反マトロイドの集合論的公理化では、反マトロイドの集合がまさにパスの和集合であるという意味において、反マトロイド全体を決定するパスと呼ばれる特別な集合が存在する。 ^[11]が反マトロイドの任意の実行可能集合である場合、から削除して別の実行可能集合を形成できる要素はのエンドポイントと呼ばれ、エンドポイントを 1 つだけ持つ実行可能集合は反マトロイドのパスと呼ばれる。^{[12]パスの族は集合包含によって部分的に順序付けることができ、反マトロイドの}パスポセットを形成する。^[13]${\displaystyle S}$${\displaystyle x}$${\displaystyle S}$${\displaystyle S}$

反マトロイドのすべての実行可能集合、およびのすべての要素について、 が端点となる のパス部分集合を見つけることができます。そのためには、 以外の要素を 1 つずつ削除し、削除しても実行可能部分集合がなくなるまで続けます。したがって、反マトロイドのすべての実行可能集合は、そのパス部分集合の和集合です。^[11]がパスでない場合、この和集合の各部分集合は の適切な部分集合です。しかし、自体が を端点とするパスである場合、反マトロイドに属する の各適切な部分集合からは除外されます。したがって、反マトロイドのパスは、それらの適切な実行可能部分集合の和集合と等しくない実行可能集合とまったく同じです。同様に、与えられた集合族が反マトロイドのパス族を形成するのは、 の各 について、の の部分集合の和集合の要素がそれ自体よりも 1 つ少ない場合のみです。^[14]そうであれば、自体は の部分集合の和集合の族です。^[11]${\displaystyle S}$${\displaystyle x}$${\displaystyle S}$${\displaystyle S}$${\displaystyle x}$${\displaystyle x}$${\displaystyle S}$${\displaystyle S}$${\displaystyle S}$${\displaystyle x}$${\displaystyle S}$${\displaystyle x}$${\displaystyle {\mathcal {P}}}$${\displaystyle S}$${\displaystyle {\mathcal {P}}}$${\displaystyle S}$${\displaystyle {\mathcal {P}}}$${\displaystyle S}$${\displaystyle {\mathcal {F}}}$${\displaystyle {\mathcal {P}}}$

反マトロイドの形式言語による形式化では、最も長い文字列は基本語と呼ばれる。各基本語はアルファベット全体の順列を形成する。^[15]が基本語の集合である場合、は の単語の接頭辞の集合として定義できる。^[16]${\displaystyle B}$${\displaystyle {\mathcal {L}}}$${\displaystyle B}$${\displaystyle B}$

が反マトロイドを定義する集合系で、が の集合の和集合に等しい場合、の集合に相補的な集合の族は 凸幾何学と呼ばれることもあり、 の集合は凸集合と呼ばれる。たとえば、シェリング反マトロイドでは、凸集合は与えられた点集合とユークリッド空間の凸部分集合の交差である。凸幾何学を定義する集合系は、交差に関して閉じている必要がある。と等しくない の任意の集合に対して、にない元が存在し、 に加えて の別の集合を形成できる必要がある。^[17]${\displaystyle {\mathcal {F}}}$${\displaystyle U}$${\displaystyle {\mathcal {F}}}$$${\displaystyle {\mathcal {G}}=\{U\setminus S\mid S\in {\mathcal {F}}\}}$$ ${\displaystyle {\mathcal {F}}}$${\displaystyle {\mathcal {G}}}$${\displaystyle S}$${\displaystyle {\mathcal {G}}}$${\displaystyle U}$${\displaystyle x}$${\displaystyle S}$${\displaystyle S}$${\displaystyle {\mathcal {G}}}$

凸幾何学は、任意の部分集合をその最小の閉じた集合に写す閉包演算子 によって定義することもできる。閉包演算子であるためには、以下の性質を持つ必要がある: ^[18]${\displaystyle \tau}$${\displaystyle U}$${\displaystyle \tau}$

• ${\displaystyle \tau (\emptyset )=\emptyset }$:空集合の閉包は空です。
• のすべての部分集合に対して、はおよびの部分集合です。${\displaystyle S}$${\displaystyle U}$${\displaystyle S}$${\displaystyle \tau (S)}$${\displaystyle \tau (S)=\tau {\bigl (}\tau (S){\bigr )}}$
• 常に、は のサブセットです。${\displaystyle S\subset T\subset U}$${\displaystyle \tau (S)}$${\displaystyle \tau (T)}$

このタイプの閉包演算から得られる閉集合の族は、交差に関して必ず閉じているが、凸幾何学ではない可能性がある。凸幾何学を定義する閉包演算子は、追加の反交換公理も満たす。

• が のサブセットであり、と が の異なる要素であり には属さないがには属する場合、 はに属しません。^[18]${\displaystyle S}$${\displaystyle U}$${\displaystyle y}$${\displaystyle z}$${\displaystyle U}$${\displaystyle \tau (S)}$${\displaystyle z}$${\displaystyle \tau (S\cup \{y\})}$${\displaystyle y}$${\displaystyle \tau (S\cup \{z\})}$

この公理を満たす閉包操作は、反交換閉包と呼ばれる。 が反交換閉包における閉集合である場合、反交換公理は に属さない要素に関する半順序を決定する。ここで、半順序においてが に属する場合。 がこの半順序の最小要素である場合、 は閉じている。つまり、反交換閉包の閉集合族は、普遍集合以外の任意の集合に対して、別の閉集合を生成するために追加できる要素が存在するという性質を持つ。この性質は反マトロイドのアクセス可能性の性質と相補的であり、閉集合の共通部分が閉じているという事実は、反マトロイドにおける実行可能集合の和集合が実行可能であるという性質と相補的である。したがって、任意の反交換閉包の閉集合の補集合は反マトロイドを形成する。^[17]${\displaystyle S}$${\displaystyle S}$${\displaystyle x\leq y}$${\displaystyle x}$${\displaystyle \tau (S\cup \{y\})}$${\displaystyle x}$${\displaystyle S\cup \{x\}}$${\displaystyle x}$

凸集合（頂点間の最短経路をすべて含む頂点の部分集合）が凸幾何学を形成する無向グラフは、まさにプトレマイオスグラフである。^[19]

反マトロイドの 2 つの実行可能集合には、それぞれ一意の最小上限(それらの和集合) と一意の最大値下限(反マトロイド内の集合のうち、両方に含まれる集合の和集合) があります。したがって、集合の包含によって部分的に順序付けられた反マトロイドの実行可能集合は、格子 を形成します。反マトロイドのさまざまな重要な特徴は、格子理論の用語で解釈できます。たとえば、反マトロイドのパスは、対応する格子の結合既約要素であり、反マトロイドの基本ワードは、格子の最大鎖に対応します。このように反マトロイドから生じる格子は、有限分配格子を一般化し、いくつかの異なる方法で特徴付けることができます。

• Dilworth (1940) によって最初に考えられた記述は、格子のmeet-irreducible元に関するものです。反マトロイドの各元に対して、を含まない唯一の最大実行可能集合が存在します。 は、を含まないすべての実行可能集合の和集合として構築できます。 この集合は自動的に meet-irreducible であり、つまり、任意の 2 つの大きな格子元の交わりではありません。 のすべての実行可能スーパーセットには が含まれるため、これは真であり、したがって、同じことが実行可能スーパーセットのすべての共通部分についても当てはまります。 任意の格子のすべての元は、多くの場合複数の方法で meet-irreducible 集合の交わりとして分解できますが、反マトロイドに対応する格子では、各元には、交わりが である meet-irreducible 集合の唯一の最小族があります。この族は、 が実行可能であるような元に対する集合で構成されます。つまり、格子には、唯一の meet-irreducible 分解があります。${\displaystyle x}$${\displaystyle S_{x}}$${\displaystyle x}$${\displaystyle S_{x}}$${\displaystyle x}$${\displaystyle S_{x}}$${\displaystyle S_{x}}$${\displaystyle x}$${\displaystyle T}$${\displaystyle T}$${\displaystyle S_{x}}$${\displaystyle x}$${\displaystyle T\cup \{x\}}$
• 2 つ目の特徴付けは、格子内の区間、つまりのすべての格子要素からなる格子要素のペアによって定義される部分格子に関するものです。区間内のすべての要素が原子 (底辺要素 より上の最小要素)の結合である場合、その区間は原子的であり、有限集合のすべての部分集合の格子と同型である場合、その区間はブール的です。反マトロイドの場合、原子的な区間はすべてブールでもあります。${\displaystyle x\leq y}$${\displaystyle z}$${\displaystyle x\leq z\leq y}$${\displaystyle x}$
• 第三に、反マトロイドから生じる格子は半モジュラ格子であり、任意の2 つの要素 および に対して、が覆う場合、がを覆うという上半モジュラ法則を満たす格子です。この条件を反マトロイドの実行可能集合に置き換えると、実行可能集合に別の実行可能集合に属さない要素が 1 つだけある場合、その 1 つの要素を に追加して反マトロイドの別の集合を形成できます。さらに、反マトロイドの格子には、ミート半分配特性があります。つまり、すべての格子要素、、およびに対して、 と が互いに等しい場合、これらは両方とも に等しくなります。半モジュラ格子およびミート半分配格子は、結合分配格子と呼ばれます。${\displaystyle x}$${\displaystyle y}$${\displaystyle y}$${\displaystyle x\wedge y}$${\displaystyle x\vee y}$${\displaystyle x}$${\displaystyle Y}$${\displaystyle X}$${\displaystyle X}$${\displaystyle x}$${\displaystyle y}$${\displaystyle z}$${\displaystyle x\wedge y}$${\displaystyle x\wedge z}$${\displaystyle x\wedge (y\vee z)}$

これら3つの特徴付けは同等である。一意の会合不約分解を持つ任意の格子はブール原子間隔を持ち、結合分配的であり、ブール原子間隔を持つ任意の格子は一意の会合不約分解を持ち、結合分配的であり、任意の結合分配格子は一意の会合不約分解とブール原子間隔を持つ。^[20]したがって、これら3つの特性のいずれかを持つ格子を結合分配的と呼ぶことができる。任意の反マトロイドは有限の結合分配格子を生じ、任意の有限の結合分配格子はこのように反マトロイドから生じる。^[21]有限結合分配格子の別の同等の特徴付けは、それらが段階的であり（任意の2つの極大鎖は同じ長さである）、極大鎖の長さが格子の会合不可元数に等しいことである。^[22]有限結合分配格子を表す反マトロイドは、格子から復元することができる。すなわち、反マトロイドの要素は、格子の会合不可元とすることができ、格子の任意の要素に対応する実行可能集合は、格子内で が 以上でないような会合不可元の集合から構成される。${\displaystyle x}$${\displaystyle y}$${\displaystyle y}$${\displaystyle x}$

任意の有限結合分配格子を、和集合に対して閉じた集合のアクセス可能な族として（つまり、反マトロイドとして）表現することは、任意の有限分配格子が和集合と積集合に対して閉じた集合の族として表現されるという バーコフの表現定理の類似物として考えることができます。

コクセター群の要素に半順序を定義する問題に動機づけられて、アームストロング (2009) は超可解格子でもある反マトロイドを研究した。超可解反マトロイドは、要素の完全に順序付けられたコレクションと、これらの要素の集合の族によって定義される。族には空集合が含まれていなければならない。さらに、2 つの集合と が族に属し、集合論的差が空でなく、が の最小の要素である場合、も族に属するという特性を持つ必要がある。アームストロングが指摘するように、このタイプの集合の族はどれも反マトロイドを形成する。アームストロングはまた、この構成が形成できる反マトロイドの格子理論的特徴付けも提供している。^[23]${\displaystyle A}$${\displaystyle B}$ ${\displaystyle B\setminus A}$${\displaystyle x}$${\displaystyle B\setminus A}$${\displaystyle A\cup \{x\}}$

と が2 つの反マトロイドで、どちらも同じ元の宇宙上の集合の族として記述されている場合、別の反マトロイドであるとの結合は次のように形成されます。 これは、反マトロイドの格子理論的特徴付けで考慮される結合とは異なる操作です。つまり、反マトロイド内の 2 つの集合を結合して別の集合を形成するのではなく、2 つの反マトロイドを結合して別の反マトロイドを形成します。同じ宇宙上のすべての反マトロイドの族は、この結合操作で半格子を形成します。^[24]${\displaystyle {\mathcal {A}}}$${\displaystyle {\mathcal {B}}}$${\displaystyle {\mathcal {A}}}$${\displaystyle {\mathcal {B}}}$$${\displaystyle {\mathcal {A}}\vee {\mathcal {B}}=\{S\cup T\mid S\in {\mathcal {A}}\wedge T\in {\mathcal {B}}\}.}$$

結合は、形式言語を反マトロイドにマッピングする閉包演算と密接に関連しており、ここで言語の閉包は、 を部分言語として含むすべての反マトロイドの共通部分です。この閉包は、 内の文字列の接頭辞の和集合を実行可能集合として持ちます。この閉包演算の観点では、結合はとの言語の和集合の閉包です。すべての反マトロイドは、連鎖反マトロイドの族の結合として、または同等に基本単語の集合の閉包として表すことができます。反マトロイドの凸次元は、そのような表現における連鎖反マトロイドの最小数（または同等に基本単語の最小数）です。 が、基本単語がすべて に属する連鎖反マトロイドの族である場合、の実行可能集合がのすべてのパスを含む場合に限り、 が生成されます。単一鎖反マトロイドに属するのパスはのパス ポセット内でチェーンを形成する必要があるため、反マトロイドの凸次元はパス ポセットをカバーするために必要なチェーンの最小数に等しく、これはディルワースの定理によりパス ポセットの幅に等しくなります。^[25]${\displaystyle {\mathcal {L}}}$${\displaystyle {\mathcal {L}}}$${\displaystyle {\mathcal {L}}}$${\displaystyle {\mathcal {A}}}$${\displaystyle {\mathcal {B}}}$${\displaystyle {\mathcal {A}}}$${\displaystyle {\mathfrak {F}}}$${\displaystyle {\mathcal {A}}}$${\displaystyle {\mathfrak {F}}}$${\displaystyle {\mathcal {A}}}$${\displaystyle {\mathfrak {F}}}$${\displaystyle {\mathcal {A}}}$${\displaystyle {\mathcal {A}}}$${\displaystyle {\mathcal {A}}}$

反マトロイドの表現を基本語の集合の閉包として持つ場合、この表現を使用して反マトロイドの実行可能集合を次元ユークリッド空間の点にマッピングできます。基本語 ごとに 1 つの座標を割り当て、実行可能集合の座標値を のサブセットである の最長接頭辞の長さにします。この埋め込みにより、 が別の実行可能集合のサブセットとなるのは、 の座標がすべて の対応する座標以下である場合のみです。したがって、実行可能集合の包含順序の順序次元は、最大で反マトロイドの凸次元に等しくなります。^[26]ただし、一般にこれら 2 つの次元は非常に異なる場合があります。順序次元が 3 であるが、凸次元が任意に大きい反マトロイドが存在する場合があります。^[27]${\displaystyle d}$${\displaystyle d}$${\displaystyle W}$${\displaystyle S}$${\displaystyle W}$${\displaystyle S}$${\displaystyle S}$${\displaystyle T}$${\displaystyle S}$${\displaystyle T}$

集合の要素数が増えると、その集合上の反マトロイドの数は急速に増加する。1、2、3などの要素の集合の場合、異なる反マトロイドの数は^[28] $${\displaystyle 1,3,22,485,59386,133059751,\dots \,.}$$

理論的なスケジューリング問題の標準表記法における優先順位制約と解放時間制約は、どちらも反マトロイドでモデル化できます。Boyd と Faigle (1990) は、タスクのスケジューリングが遅れることによって発生する最大ペナルティを最小限に抑えることを目標とする、優先順位制約のある単一プロセッサ スケジューリング問題を最適に解決するためのEugene Lawlerの貪欲アルゴリズムを反マトロイドを使用して一般化しました。

Glasserman & Yao (1994) は、反マトロイドを使用して、離散イベントシミュレーションシステムにおけるイベントの順序をモデル化します。

Parmar (2003) は、反マトロイドを使用して、人工知能の 計画問題 における目標に向けた進行をモデル化します。

制約下での最適化に基づく自然言語の発展のための数学モデルである最適性理論では、文法は反マトロイドと論理的に同等である。 ^[29]

数理心理学では、反マトロイドは人間の学習者の実現可能な知識状態を説明するために使われてきた。反マトロイドの各要素は学習者が理解すべき概念、または学習者が正しく解決できる可能性のある問題のクラスを表し、反マトロイドを形成する要素の集合は一人の人間が理解できる可能性のある概念の集合を表す。反マトロイドを定義する公理は、ある概念を学習しても学習者が別の概念を学習するのを妨げることはなく、一度に一つの概念を学習することであらゆる実現可能な知識状態に到達できると非公式に表現される。知識評価システムのタスクは、少数の適切に選択された問題に対する学習者の反応を分析することによって、特定の学習者が知っている概念の集合を推測することである。この文脈では、反マトロイドは「学習空間」や「適切に段階分けされた知識空間」とも呼ばれる。^[30]