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 も様々な場面で登場する。 例として基本的なのは, グラフから作られるものと, ベクトルの一次従属性から定義されるものであるが, 他にも様々なものがある。

• examples and important classes of matroids

上に挙げた例から分かるように, 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.

[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.