正則マトロイド

数学において、正則マトロイドはすべての体にわたって表現できるマトロイドです。

意味

マトロイドは、特定の公理を満たす有限集合の部分集合の族として定義されます。族内の集合は「独立集合」と呼ばれます。マトロイドを構築する方法の 1 つは、ベクトル空間内の有限ベクトル集合を選択し、ベクトル空間内で線形独立である場合に、マトロイド内でベクトルのサブセットを独立であると定義することです。このように構築された集合の族はすべてマトロイドですが、すべてのマトロイドをこのように構築できるわけではなく、異なるフィールド上のベクトル空間は、それらから構築できる異なるマトロイドの集合につながります。

マトロイドが正則であるとは、任意の体に対してが上のベクトル系で表せる場合である。^[1]^[2] $M$ $F$ $M$ $F$

プロパティ

マトロイドが正則であれば、その双対マトロイドも正則であり、^[1]そのマイナーマトロイドもすべて正則です。^[3]正則マトロイドのすべての直和は正則のままです。^[4]

すべてのグラフィックマトロイド（およびすべてのコグラフィックマトロイド）は正則です。^{[5]逆に、すべての正則マトロイドは、グラフ上の}クリーク和演算を一般化するマトロイド結合演算を使用して、グラフィックマトロイド、コグラフィックマトロイド、およびグラフィックでもコグラフィックでもない特定の10要素マトロイドを組み合わせることによって構築できます。^[6]

正則マトロイドの基底の数は、関連する行列の行列式として計算することができ、キルヒホッフの行列木定理をグラフィックマトロイドに一般化することができる。^[7]

特徴

一様マトロイド（4点直線）は正則ではない。2元有限体 GF(2)上では実現できないため、 2元マトロイドではないが、他のすべての体上では実現できる。ファノ平面（7つの3点が従属する階数3のマトロイド）のマトロイドとその双対も正則ではない。GF(2)上、および特性2のすべての体上では実現できるが、それ以外の体上では実現できない。Tutte（1958）が示したように、これら3つの例は正則マトロイドの理論の基本である。すべての非正則マトロイドは、これら3つのうち少なくとも1つをマイナーとして持つ。したがって、正則マトロイドは、3つの禁制マイナーの1つ、ファノ平面、またはその双対を持たないマトロイドである。^[8] $U{}_{4}^{2}$ $U{}_{4}^{2}$

マトロイドが正則であれば、明らかにGF(2)とGF(3)の2つの体上で実現可能でなければならない。逆もまた真である。つまり、これら2つの体の両方上で実現可能なマトロイドはすべて正則である。この結果は、これらの体上で実現可能なマトロイドの禁じられたマイナーな特徴付けから導かれる。これは、ロータの予想によって体系化された結果のファミリーの一部である。^[9]

正則マトロイドは、全ユニモジュラ行列から定義できるマトロイドです。全ユニモジュラ行列とは、すべての正方部分行列の行列式が 0、1、または -1 である行列のことです。マトロイドを実現するベクトルは、行列の行としてとることができます。このため、正則マトロイドはユニモジュラマトロイドと呼ばれることもあります。^[10]正則マトロイドとユニモジュラ行列の同値性、および禁制マイナーによるそれらの特徴付けは、WT Tutteの深い成果であり、もともとTutte ホモトピー定理を使用して証明されました。^[8] Gerards (1989) は後に、禁制マイナーによるユニモジュラ行列の特徴付けの代替的でより簡単な証明を発表しました。^[11]

アルゴリズム

独立性オラクルを介してマトロイドにアクセスできれば、マトロイドが正則かどうかをテストするための多項式時間アルゴリズムが存在する。^[12]

参考文献

^ ab 藤重悟 (2005)、劣モジュラ関数と最適化、Annals of Discrete Mathematics、エルゼビア、p. 24、ISBN 9780444520869。
^ オクスリー、ジェームズ G. (2006)、「マトロイド理論」、オックスフォード大学院数学テキスト第 3 巻、オックスフォード大学出版局、p. 209、ISBN 9780199202508。
^ オクスリー（2006）、112ページ。
^ オクスリー（2006）、131ページ。
^ Tutte, WT (1965)、「マトロイドに関する講義」、国立標準局研究ジャーナル、69B : 1–47、doi : 10.6028/jres.069b.001、MR 0179781。
^ シーモア、PD（1980）、「正則マトロイドの分解」、組み合わせ理論ジャーナル、シリーズB、28（3）：305–359、doi：10.1016 / 0095-8956（80）90075-1、hdl：10338.dmlcz / 101946、MR 0579077。
^ マウラー、スティーブン B. (1976)、「グラフのツリー、サイクル、コサイクルに関するいくつかの定理の行列一般化」、SIAM 応用数学ジャーナル、30 (1): 143–148、doi :10.1137/0130017、MR 0392635。
^ ab Tutte, WT (1958)、「マトロイドのホモトピー定理。I、II」、アメリカ数学会誌、88 (1): 144–174、doi :10.2307/1993244、JSTOR 1993244、MR 0101526。
^ シーモア、PD（1979）、「GF（3）上のマトロイド表現」、組み合わせ理論ジャーナル、シリーズB、26（2）：159–173、doi：10.1016 / 0095-8956（79）90055-8、MR 0532586。
^ オクスリー（2006）、20ページ。
^ Gerards, AMH (1989)、「Tutte の完全ユニモジュラ行列の特徴付けの簡単な証明」、線形代数とその応用、114/115: 207–212、doi : 10.1016/0024-3795(89)90461-8。
^ Truemper, K. (1982)、「マトロイドの表現可能性テストの効率について」、European Journal of Combinatorics、3 (3): 275–291、doi : 10.1016/s0195-6698(82)80039-5、MR 0679212。

[sfo-1] 藤重悟 (2005)、劣モジュラ関数と最適化、Annals of Discrete Mathematics、エルゼビア、p. 24、ISBN 9780444520869。

[2] オクスリー、ジェームズ G. (2006)、「マトロイド理論」、オックスフォード大学院数学テキスト第 3 巻、オックスフォード大学出版局、p. 209、ISBN 9780199202508。

[3] オクスリー（2006）、112ページ。

[4] オクスリー（2006）、131ページ。

[5] Tutte, WT (1965)、「マトロイドに関する講義」、国立標準局研究ジャーナル、69B : 1–47、doi : 10.6028/jres.069b.001、MR 0179781。

[6] シーモア、PD（1980）、「正則マトロイドの分解」、組み合わせ理論ジャーナル、シリーズB、28（3）：305–359、doi：10.1016 / 0095-8956（80）90075-1、hdl：10338.dmlcz / 101946、MR 0579077。

[7] マウラー、スティーブン B. (1976)、「グラフのツリー、サイクル、コサイクルに関するいくつかの定理の行列一般化」、SIAM 応用数学ジャーナル、30 (1): 143–148、doi :10.1137/0130017、MR 0392635。

[t58-8] Tutte, WT (1958)、「マトロイドのホモトピー定理。I、II」、アメリカ数学会誌、88 (1): 144–174、doi :10.2307/1993244、JSTOR 1993244、MR 0101526。

[9] シーモア、PD（1979）、「GF（3）上のマトロイド表現」、組み合わせ理論ジャーナル、シリーズB、26（2）：159–173、doi：10.1016 / 0095-8956（79）90055-8、MR 0532586。

[10] オクスリー（2006）、20ページ。

[11] Gerards, AMH (1989)、「Tutte の完全ユニモジュラ行列の特徴付けの簡単な証明」、線形代数とその応用、114/115: 207–212、doi : 10.1016/0024-3795(89)90461-8。

[12] Truemper, K. (1982)、「マトロイドの表現可能性テストの効率について」、European Journal of Combinatorics、3 (3): 275–291、doi : 10.1016/s0195-6698(82)80039-5、MR 0679212。