正則マトロイド
数学における正則マトロイド（せいそくマトロイド、英: regular matroid）とは、任意の体の上で 表現できるマトロイドのことである。
定義
[編集]マトロイドは、有限集合の部分集合族でいくつかの公理を満たすものと定義される。マトロイドに属する部分集合は独立集合（independent set）と呼ばれる。マトロイドを構成する方法の一つは、あるベクトル空間から有限個のベクトルを選び、それらの部分集合がマトロイドの意味で独立集合であるのは、それら（ベクトルの有限集合）がこのベクトル空間で線形独立であるとき、かつそのときに限ると定義することである。
この方法で構成される集合族は必ずマトロイドになるが、任意のマトロイドがこの方法で表現されるとは限らない。また、ベクトル空間の係数体を取り換えると、それに応じて構成されるマトロイドも変わり得る。
マトロイド が正則であるとは、どのような体 を選んでも、 が 上のベクトル空間から上記の方法で構成できることを言う[1][2]。
性質
[編集]マトロイドが正則であるとき、その双対マトロイド、および任意のマトロイドマイナーもまた正則である[1][3]。正則マトロイドの直和（direct sum） はまた正則マトロイドになる[4]。
任意のグラフ的マトロイド（および任意の補グラフ的マトロイド（co-graphic matroid、グラフ的マトロイドの双対マトロイドを指す））は正則である[5]。逆に、任意の正則マトロイドは、1個以上のグラフ的マトロイドと、1個以上の補グラフ的マトロイドと、ある要素数10のグラフ的でも補グラフ的でもないマトロイドから、グラフ理論におけるクリーク和を一般化した接合操作によって得られる[6]。
正則マトロイドの基の数は、グラフ的マトロイドに対するキルヒホッフの定理を一般化した手法によって、対応する行列の行列式により計算できる[7]。
特徴付け
[編集]一様マトロイド (the four-point line) は正則でない。このマトロイドは（それ以外の全ての体の上では可能であるにもかかわらず）二元体 GF(2) 上のベクトル空間では実現できない（2値マトロイドでない）からである。
ファノ平面から導かれるマトロイド（階数3のマトロイドであって、7通りの点の三つ組が独立である）およびその双対マトロイドは、やはり正則でない。このマトロイドは GF(2) および任意の標数2 の体上で実現できるが、それ以外のどんな体上でも実現できない。
Tutte (1958) が示したように、これら3つの例は正則マトロイドの理論の基礎となる。任意の非正則マトロイドは、これら3つのマトロイドのうち少なくとも1つをマトロイドマイナーに持つ。よって、正則マトロイド全体は禁じられた3種、・ファノ平面・その双対、をマトロイドマイナーに持たないマトロイド全体とちょうど一致する[8]
マトロイドが正則であれば、明らかに2つの体、GF(2),GF(3) 上で実現されねばならない。この逆も真である。これら2つの体上で実現できるマトロイドは、正則マトロイドである。この結果は、これらの体上で実現できるマトロイドに対する不可能なマトロイドマイナーの特徴付けから得られるが、これはロタ予想によって体系化される一連の結果の一部である[9]。
正則マトロイドは、全ユニモジュラ行列（全ての正方小行列式が 0, 1, −1 のいずれかにである正方行列）によって定義できるマトロイドである。ここでベクトル集合の実現は、行列の行集合を選ぶことにより行うものとする。このことから、正則マトロイドはときにユニモジュラマトロイドとも呼ばれる[10]。正則マトロイドと全ユニモジュラ行列との等価性、および不可能なマトロイドマイナーによるそれらの特徴付けは、ウィリアム・トーマス・タットによる深い結果であり、タットのホモトピー定理を用いて最初に証明された[8]。 Gerards (1989) は後に、不可能なマトロイドマイナーによる全ユニモジュラ行列の特徴付けの、より簡単な別証明を与えた[11]。
アルゴリズム
[編集]独立性オラクルが与えられたとき、マトロイドが正則か否かを多項式時間で判定するアルゴリズムが存在する[12]。
脚注
[編集]- ^ a b Fujishige, Satoru (2005), Submodular Functions and Optimization, Annals of Discrete Mathematics, Elsevier, p. 24, ISBN 9780444520869.
- ^ Oxley, James G. (2006), Matroid Theory, Oxford Graduate Texts in Mathematics, 3, Oxford University Press, p. 209, ISBN 9780199202508.
- ^ Oxley (2006), p. 112.
- ^ Oxley (2006), p. 131.
- ^ Tutte, W. T. (1965), “Lectures on matroids”, Journal of Research of the National Bureau of Standards 69B: 1–47, doi:10.6028/jres.069b.001, MR0179781.
- ^ Seymour, P. D. (1980), “Decomposition of regular matroids”, Journal of Combinatorial Theory, Series B 28 (3): 305–359, doi:10.1016/0095-8956(80)90075-1, MR579077.
- ^ Maurer, Stephen B. (1976), “Matrix generalizations of some theorems on trees, cycles and cocycles in graphs”, SIAM Journal on Applied Mathematics 30 (1): 143–148, doi:10.1137/0130017, MR0392635.
- ^ a b Tutte, W. T. (1958), “A homotopy theorem for matroids. I, II”, Transactions of the American Mathematical Society 88: 144–174, doi:10.2307/1993244, MR0101526.
- ^ Seymour, P. D. (1979), “Matroid representation over GF(3)”, Journal of Combinatorial Theory, Series B 26 (2): 159–173, doi:10.1016/0095-8956(79)90055-8, MR532586.
- ^ Oxley (2006), p. 20.
- ^ Gerards, A. M. H. (1989), “A short proof of Tutte's characterization of totally unimodular matrices”, Linear Algebra and its Applications 114/115: 207–212, doi:10.1016/0024-3795(89)90461-8.
- ^ Truemper, K. (1982), “On the efficiency of representability tests for matroids”, European Journal of Combinatorics 3 (3): 275–291, doi:10.1016/s0195-6698(82)80039-5, MR679212.