Matroid と oriented matroid の基本

Matroid と oriented matroid のどちらから勉強するのがよいのだろうか。トポロジーに関連した話題だと, hyperplane arrangement のように oriented matroid の方が関係が深いものが多いような気がする。

5人組の oriented matroid の本 [Bjö+99] では, 定義の前に様々な例により oriented matroid について説明してある。 Matroid を勉強する際にも, まずはできるだけ多くの例を自分の手を動かして理解するのがよい, ということなのだろう。 [Bjö+99] の第1章から例を挙げると以下のようなものがある。

• quiver (directed graph) の oriented circuit から成る oriented matroid
• 実ベクトル空間の中の有限個のベクトルの configuration から定義される oriented matroid
• 実affine 空間の点の configuration から定義される oriented matroid
• 実 hyperplane arrangement から定義される oriented matroid
• pseudosphere arrangement の oriented matroid

そして, 具体例に慣れてから定義 (公理) を見るようになっている。Oriented matroid の定義には, いくつもの一見異なるが同値なものがあり, それらの内どれを使うかをよく考えないといけない。5人組の oriented matroid の本 [Bjö+99] には以下の「公理」がある。また最近でも, Delucchi の [Del11] のように新しいものが提案されている。

• circuit axioms
• axioms for dual pairs (orthogonality axioms)
• painting axioms
• basis orientation - pivoting property
• chirotope axioms
• \(3\)-term Grassmann-Plücker relations
• vector axioms
• maximal vector axioms
• convex closure axioms
• Lawrence’s axioms
• da Silva’s axioms
• covector axioms

例えば, その名前からも想像できるように, circuit axioms は, 有向グラフ (quiver) の例で理解するのがよい。 名前からは分からないが, real hyperplane arrangement を扱うときには, covector axioms が有用だろう。Covector とは real hyperplane arrangement の face の類似である。

逆に任意の oriented matroid に対し, その「幾何学的意味付け」がある, というのが, Folkman と Lawrence [FL78] の topological representation theorem である。より正確には, pseudosphere arrangement として実現できるのである。

• topological representation theorem

Bokowski の本 [Bok06] では, この pseudosphere arrangement による特徴付けを sphere system として公理として用いている。 また他にもいくつかの公理が挙げてある。例えば以下のもの:

• sphere system [FL78]
• hyperline sequence [Bok+05]
• order function
• 代数多様体を用いたもの [BGR91]
• hull system [Knu92]

そのときの matroidのmorphism としては, weak map が使われている。他に oriented matorid の間の写像としては, strong map と呼ばれるものもある。

• category of matroids

Unoriented matroid も様々な場面で登場する。 当然代表的なものは次のものである。

• graph の cycle から定義される unoriented matroid
• ベクトルの集合の1次従属性あるいや1次独立性から定義される unoriented matroid

最初の例の方法で graph から作られる matroid を graphic matroid という。 どのような matroid が graphic か, という問題が考えられるが, これについては Seymour の論文 [Sey81] がある。 これを元に Geelen ら [GGW18] により quasi-graphic matroid という matroid の class が定義されている。

2番目の例で, unoriented matroid だと \(\R \) 以外の体上のベクトル空間を考えることができる。体 \(k\) 上のベクトル空間のベクトルの有限集合の1次独立性で定義される matroid と同値になる matroid は, \(k\) 上 representable であるという。特に \(\F _2\) 上 representable な matroid を binary matroid という。

• 体 \(k\) 上 representable な matroid
• binary matroid

よって, 体を変えたときの representability について考えることもできる。 例えば, Pendavingh と van Zwam の [PZ10b; PZ10a] など。 それによると, 有名なのは Tutte の [Tut65] の結果のようである。

線形独立性の他にも代数的独立性からも matroid が得られる。体の拡大 \(K/k\) と \(K\) の有限集合 \(E\) が与えられたとき, \(E\) の 部分集合 \(I\) で \(k\) 上代数的独立であることを independent とすると matroid が得られる。 このような matroid を algebraic matroid と呼ぶようである。 あまり良い名前とは思えないが。そして algebraic matroid として実現できるとき, algebraically representable と呼ぶ。

• algebraic matroid
• algebraic representability

上に挙げた例から分かるように, matroidと 各種 arrangement は関係が深い。特に, hyperplane arrangement に関する様々な構成は, matroid に一般化されることが多い。 これらは matroid の不変量と考えてもよいだろう。

• matroid の不変量

References

[BGR91]

Jürgen Bokowski, António Guedes de Oliveira, and Jürgen Richter-Gebert. “Algebraic varieties characterizing matroids and oriented matroids”. In: Adv. Math. 87.2 (1991), pp. 160–185. url: http://dx.doi.org/10.1016/0001-8708(91)90070-N.

[Bjö+99]

Anders Björner, Michel Las Vergnas, Bernd Sturmfels, Neil White, and Günter M. Ziegler. Oriented matroids. Second. Vol. 46. Encyclopedia of Mathematics and its Applications. Cambridge: Cambridge University Press, 1999, pp. xii+548. isbn: 0-521-77750-X. url: http://dx.doi.org/10.1017/CBO9780511586507.

[Bok+05]

Jürgen Bokowski, Simon King, Susanne Mock, and Ileana Streinu. “The topological representation of oriented matroids”. In: Discrete Comput. Geom. 33.4 (2005), pp. 645–668. url: http://dx.doi.org/10.1007/s00454-005-1164-4.

[Bok06]

Jürgen G. Bokowski. Computational oriented matroids. Equivalence classes of matrices within a natural framework. Cambridge: Cambridge University Press, 2006, pp. xiv+323. isbn: 978-0-521-84930-2; 0-521-84930-6.

[Del11]

Emanuele Delucchi. “Modular elimination in matroids and oriented matroids”. In: European J. Combin. 32.3 (2011), pp. 339–343. arXiv: 1002.2357. url: http://dx.doi.org/10.1016/j.ejc.2010.10.013.

[FL78]

Jon Folkman and Jim Lawrence. “Oriented matroids”. In: J. Combin. Theory Ser. B 25.2 (1978), pp. 199–236. url: http://dx.doi.org/10.1016/0095-8956(78)90039-4.

[GGW18]

Jim Geelen, Bert Gerards, and Geoff Whittle. “Quasi-graphic matroids”. In: J. Graph Theory 87.2 (2018), pp. 253–264. arXiv: 1512.03005. url: https://doi.org/10.1002/jgt.22177.

[Knu92]

D. E. Knuth. Axioms and hulls. Vol. 606. Lecture Notes in Computer Science. Berlin: Springer-Verlag, 1992, pp. x+109. isbn: 3-540-55611-7.

[PZ10a]

R. A. Pendavingh and S. H. M. van Zwam. “Confinement of matroid representations to subsets of partial fields”. In: J. Combin. Theory Ser. B 100.6 (2010), pp. 510–545. arXiv: 0806.4487. url: https://doi.org/10.1016/j.jctb.2010.04.002.

[PZ10b]

R. A. Pendavingh and S. H. M. van Zwam. “Lifts of matroid representations over partial fields”. In: J. Combin. Theory Ser. B 100.1 (2010), pp. 36–67. arXiv: 0804 . 3263. url: https://doi.org/10.1016/j.jctb.2009.03.006.

[Sey81]

P. D. Seymour. “Recognizing graphic matroids”. In: Combinatorica 1.1 (1981), pp. 75–78. url: http://dx.doi.org/10.1007/BF02579179.

[Tut65]

W. T. Tutte. “Lectures on matroids”. In: J. Res. Nat. Bur. Standards Sect. B 69B (1965), pp. 1–47.