正則マトロイドのソースを表示

[[数学]]における'''正則マトロイド'''（せいそくマトロイド、{{Lang-en-short|regular matroid}}）とは、任意の[[可換体|体]]の上で
[[表現 (数学)|表現]]できる[[マトロイド]]のことである。

==定義==
マトロイドは、[[有限集合]]の部分集合族でいくつかの[[公理]]を満たすものと定義される。マトロイドに属する部分集合は独立集合（independent set）と呼ばれる。マトロイドを構成する方法の一つは、ある[[ベクトル空間]]から有限個のベクトルを選び、それらの部分集合がマトロイドの意味で独立集合であるのは、それら（ベクトルの有限集合）がこのベクトル空間で[[線形独立]]であるとき、かつそのときに限ると定義することである。

この方法で構成される集合族は必ずマトロイドになるが、任意のマトロイドがこの方法で表現されるとは限らない。また、ベクトル空間の係数体を取り換えると、それに応じて構成されるマトロイドも変わり得る。

マトロイド <math>M</math> が正則であるとは、どのような体 <math>F</math> を選んでも、<math>M</math> が <math>F</math> 上のベクトル空間から上記の方法で構成できることを言う<ref name="sfo">{{citation
 | last = Fujishige | first = Satoru
 | isbn = 9780444520869
 | page = 24
 | publisher = Elsevier
 | series = Annals of Discrete Mathematics
 | title = Submodular Functions and Optimization
 | year = 2005}}.</ref><ref>{{citation
 | last = Oxley | first = James G. | authorlink = James Oxley
 | isbn = 9780199202508
 | page = 209
 | publisher = Oxford University Press
 | series = Oxford Graduate Texts in Mathematics
 | title = Matroid Theory
 | volume = 3
 | year = 2006}}.</ref>。

==性質==
マトロイドが正則であるとき、その{{仮リンク|双対マトロイド|en|dual matroid}}、および任意の{{仮リンク|マトロイドマイナー|en|matroid minor}}もまた正則である<ref name="sfo"/><ref>{{harvtxt|Oxley|2006}}, p. 112.</ref>。正則マトロイドの直和（direct sum）
はまた正則マトロイドになる<ref>{{harvtxt|Oxley|2006}}, p. 131.</ref>。

任意の{{仮リンク|グラフ的マトロイド|en|graphic matroid}}（および任意の補グラフ的マトロイド（co-graphic matroid、グラフ的マトロイドの双対マトロイドを指す））は正則である<ref>{{citation
 | last = Tutte | first = W. T.
 | journal = Journal of Research of the National Bureau of Standards
 | mr = 0179781
 | pages = 1–47
 | title = Lectures on matroids
 | url = http://cdm16009.contentdm.oclc.org/cdm/ref/collection/p13011coll6/id/66650
 | volume = 69B
 | year = 1965
 | doi=10.6028/jres.069b.001}}.</ref>。逆に、任意の正則マトロイドは、1個以上のグラフ的マトロイドと、1個以上の補グラフ的マトロイドと、ある要素数10のグラフ的でも補グラフ的でもないマトロイドから、[[グラフ理論]]における{{仮リンク|クリーク和|en|clique-sum}}を一般化した接合操作によって得られる<ref>{{citation
 | last = Seymour | first = P. D. | authorlink = Paul Seymour (mathematician)
 | doi = 10.1016/0095-8956(80)90075-1
 | issue = 3
 | journal = [[Journal of Combinatorial Theory]]
 | mr = 579077
 | pages = 305–359
 | series = Series B
 | title = Decomposition of regular matroids
 | volume = 28
 | year = 1980}}.</ref>。

正則マトロイドの基の数は、グラフ的マトロイドに対する{{仮リンク|キルヒホッフの定理|en|Kirchhoff's theorem|preserve=1}}を一般化した手法によって、対応する行列の[[行列式]]により計算できる<ref>{{citation
 | last = Maurer | first = Stephen B.
 | issue = 1
 | journal = SIAM Journal on Applied Mathematics
 | mr = 0392635
 | pages = 143–148
 | title = Matrix generalizations of some theorems on trees, cycles and cocycles in graphs
 | volume = 30
 | year = 1976
 | doi=10.1137/0130017}}.</ref>。

==特徴付け==
{{仮リンク|一様マトロイド|en|uniform matroid}} <math>U{}^2_4</math> (the four-point line) は正則でない。このマトロイドは（それ以外の全ての体の上では可能であるにもかかわらず）[[有限体|二元体]] GF(2) 上のベクトル空間では実現できない（{{仮リンク|2値マトロイド|en|binary matroid}}でない）からである。

{{仮リンク|ファノ平面|en|Fano plane}}から導かれるマトロイド（階数3のマトロイドであって、7通りの点の三つ組が独立である）およびその双対マトロイドは、やはり正則でない。このマトロイドは GF(2) および任意の[[標数]]2 の体上で実現できるが、それ以外のどんな体上でも実現できない。

{{harvtxt|Tutte|1958}} が示したように、これら3つの例は正則マトロイドの理論の基礎となる。任意の非正則マトロイドは、これら3つのマトロイドのうち少なくとも1つをマトロイドマイナーに持つ。よって、正則マトロイド全体は禁じられた3種、<math>U{}^2_4</math>・ファノ平面・その双対、をマトロイドマイナーに持たないマトロイド全体とちょうど一致する<ref name="t58">{{citation
 | last = Tutte | first = W. T. | authorlink = W. T. Tutte
 | journal = Transactions of the American Mathematical Society
 | mr = 0101526
 | pages = 144–174
 | title = A homotopy theorem for matroids. I, II
 | volume = 88
 | year = 1958
 | doi=10.2307/1993244}}.</ref>

マトロイドが正則であれば、明らかに2つの体、GF(2),GF(3) 上で実現されねばならない。この逆も真である。これら2つの体上で実現できるマトロイドは、正則マトロイドである。この結果は、これらの体上で実現できるマトロイドに対する不可能なマトロイドマイナーの特徴付けから得られるが、これは{{仮リンク|ロタ予想|en|Rota's conjecture}}によって体系化される一連の結果の一部である<ref>{{citation
 | last = Seymour | first = P. D. | authorlink = Paul Seymour (mathematician)
 | doi = 10.1016/0095-8956(79)90055-8
 | issue = 2
 | journal = [[Journal of Combinatorial Theory]]
 | mr = 532586
 | pages = 159–173
 | series = Series B
 | title = Matroid representation over GF(3)
 | volume = 26
 | year = 1979}}.</ref>。

正則マトロイドは、[[ユニモジュラ行列|全ユニモジュラ行列]]（全ての正方小行列式が 0, 1, &minus;1 のいずれかにである正方行列）によって定義できるマトロイドである。ここでベクトル集合の実現は、行列の行集合を選ぶことにより行うものとする。このことから、正則マトロイドはときに'''ユニモジュラマトロイド'''とも呼ばれる<ref>{{harvtxt|Oxley|2006}}, p. 20.</ref>。正則マトロイドと全ユニモジュラ行列との等価性、および不可能なマトロイドマイナーによるそれらの特徴付けは、{{仮リンク|ウィリアム・トーマス・タット|en|W. T. Tutte}}による深い結果であり、{{仮リンク|タットのホモトピー定理|en|Tutte homotopy theorem}}を用いて最初に証明された<ref name="t58"/>。 {{harvtxt|Gerards|1989}} は後に、不可能なマトロイドマイナーによる全ユニモジュラ行列の特徴付けの、より簡単な別証明を与えた<ref>{{citation|last=Gerards|first=A. M. H.|year=1989|title=A short proof of Tutte's characterization of totally unimodular matrices|journal=Linear Algebra and its Applications|volume=114/115|pages=207&ndash;212|doi=10.1016/0024-3795(89)90461-8}}.</ref>。

==アルゴリズム==
独立性オラクルが与えられたとき、マトロイドが正則か否かを[[多項式時間]]で判定するアルゴリズムが存在する<ref>{{citation
 | last = Truemper | first = K.
 | issue = 3
 | journal = European Journal of Combinatorics
 | mr = 679212
 | pages = 275–291
 | title = On the efficiency of representability tests for matroids
 | volume = 3
 | year = 1982
 | doi=10.1016/s0195-6698(82)80039-5}}.</ref>。

==脚注==
{{reflist|colwidth=30em}}

{{DEFAULTSORT:せいそくまとろいと}}
[[Category:マトロイド理論]]
[[Category:数学に関する記事]]