Geometric Invariants of Matroids

Matroid からは, 様々な simplicial complex が定義される。 そもそも matroid の定義として independence set に関する公理を用いると, independence set の集合として abstract simplicial complex ができるので, matroid 自身 simplicial complex の一種と思うこともできる。

他にも Bergman complex, broken circuit complex, external activity complex などがある。

• matroid の independence complex
• matroid の broken circuit complex
• matroid の Bergman complex や Bergman fan
• matroid Steiner complex [CP89; Cha00]
• external activity complex [ACS16]
• extension space [SZ93]

Dinh [Din] によると, broken circuit complex のアイデアは, Whitney の [Whi32] まで遡るらしい。その後, Rota [Rot64], Wilf [Wil76], Brylawski [Bry77] などにより調べられた。

Oriented matroid は, 点の configuration の一般化と考えることができるので, 多面体の一般化とみなすこともできる。 よって多面体に対する概念を matroid に一般化しようという試みもある。 例えば, oriented matroid の “triangulation” を考えることもできる。Santos [San02] に依る。多面体の頂点の affine 従属性からできる oriented matroid の場合, 元の 多面体の triangulation と一致する。 多面体のグラフ (\(1\)-skeleton) の matroid 版もある。Matroid polytope という種類の oriented matroid に対し定義される。“Polytope matroid” という名前にした方が誤解を招かなくてよいと思うのだが。

• matroid polytope
• matroid polytope のグラフ
• simple matroid polytope の face lattice はそのグラフから決まる (Cordovil [Cor])

多面体のグラフと言えば, realization space であるが, oriented matroid の realization space については, 有名な Mnëv の universality theorem [Mnë85; Mnë88] がある。どんな semi-algebraic set もある oriented matroid の realization space と stably equivalent になるということで, 驚くべきことだと思う。

• oriented matroid の realization space と Mnëv の universality theorem

実超平面配置の Salvetti complex は, 本質的には oriented matroid に対して定義されたものである。

• oriented matroid の Salvetti complex

実超平面配置からは, 半空間の共通部分で与えられる空間, つまり polyhedron の類似が考えられる。 そして polyhedral complex の一般化も考えることができる。例えば, Reading の [Rea12]など。

• oriented matroid の中の polyhedral complex

References

[ACS16]

Federico Ardila, Federico Castillo, and José Alejandro Samper. “The topology of the external activity complex of a matroid”. In: Electron. J. Combin. 23.3 (2016), Paper 3.8, 20. arXiv: 1410.3870. url: https://doi.org/10.37236/5042.

[Bry77]

Tom Brylawski. “The broken-circuit complex”. In: Trans. Amer. Math. Soc. 234.2 (1977), pp. 417–433. url: http://dx.doi.org/10.2307/1997928.

[Cha00]

Manoj K. Chari. “On discrete Morse functions and combinatorial decompositions”. In: Discrete Math. 217.1-3 (2000). Formal power series and algebraic combinatorics (Vienna, 1997), pp. 101–113. url: http://dx.doi.org/10.1016/S0012-365X(99)00258-7.

[Cor]

Raul Cordovil. Kalai orientations on matroid polytopes. arXiv: math/ 0504326.

[CP89]

Charles J. Colbourn and William R. Pulleyblank. “Matroid Steiner problems, the Tutte polynomial and network reliability”. In: J. Combin. Theory Ser. B 47.1 (1989), pp. 20–31. url: http://dx.doi.org/10.1016/0095-8956(89)90062-2.

[Din]

Le Van Dinh. Broken circuit complexes of series-parallel networks. arXiv: 1404.1728.

[Mnë85]

N. E. Mnëv. “Varieties of combinatorial types of projective configurations and convex polyhedra”. In: Dokl. Akad. Nauk SSSR 283.6 (1985), pp. 1312–1314.

[Mnë88]

N. E. Mnëv. “The universality theorems on the classification problem of configuration varieties and convex polytopes varieties”. In: Topology and geometry—Rohlin Seminar. Vol. 1346. Lecture Notes in Math. Berlin: Springer, 1988, pp. 527–543. url: http://dx.doi.org/10.1007/BFb0082792.

[Rea12]

Nathan Reading. “Coarsening polyhedral complexes”. In: Proc. Amer. Math. Soc. 140.10 (2012), pp. 3593–3605. arXiv: 1004.4194. url: http://dx.doi.org/10.1090/S0002-9939-2012-11194-3.

[Rot64]

Gian-Carlo Rota. “On the foundations of combinatorial theory. I. Theory of Möbius functions”. In: Z. Wahrscheinlichkeitstheorie und Verw. Gebiete 2 (1964), 340–368 (1964).

[San02]

Francisco Santos. “Triangulations of oriented matroids”. In: Mem. Amer. Math. Soc. 156.741 (2002), pp. viii+80. url: http://dx.doi.org/10.1090/memo/0741.

[SZ93]

Bernd Sturmfels and Günter M. Ziegler. “Extension spaces of oriented matroids”. In: Discrete Comput. Geom. 10.1 (1993), pp. 23–45. url: http://dx.doi.org/10.1007/BF02573961.

[Whi32]

Hassler Whitney. “A logical expansion in mathematics”. In: Bull. Amer. Math. Soc. 38.8 (1932), pp. 572–579. url: http://dx.doi.org/10.1090/S0002-9904-1932-05460-X.

[Wil76]

Herbert S. Wilf. “Which polynomials are chromatic?” In: Colloquio Internazionale sulle Teorie Combinatorie (Roma, 1973), Tomo I. Rome: Accad. Naz. Lincei, 1976, 247–256. Atti dei Convegni Lincei, No. 17.