Matroidのデータから構成できるもの

Matroid は, graph や hyperplane arrangement など, 様々な組み合せ論的構造の一般化になっているので, それらの不変量の matroid への拡張も考えられている。 そのようなものの代表は, Tutte polynomial である。 他にも様々な多項式不変量が定義されている。

• polynomial invariants of matroids

代数的不変量としては, Orlik-Solomon algebra などの一般化がある。

• algebraic invariants of matroids

幾何学的対象, 特に, 多面体や単体的複体の構成も重要である。

• geometric invariants of matroids

Matroid と代数多様体の類似から, Chow ring などの代数多様体の不変量も matroid に一般化されてきている。

• Chow ring of matroid

特性類を matroid に一般化することも考えられている。López de Moderano と Rincón と Shaw の [LRS20] では, 超平面配置の complement の wonderful compactification に対する Chern class (MacPherson による Chern class の 特異点を持った多様体への一般化) を組み合せ論的に表し, それが任意の matroid に対し定義できることを示している。

Tutte polynomial は, グラフの不変量が matroid に拡張された例であるが, グラフに対しては, 彩色に関する不変量が色々定義されている。 それらを matroid に一般化することも考えられている。Lasoń の thesis [Las] の Introduction を見るとよい。

Oriented matroid の chromatic number は, Hochstättler と Nickel [HN07; HN08] により導入された。その元になっているのは, Tutte [Tut54] によるグラフの彩色の相対となる nowhere-zero flow の概念と, その Hochstättler and Neštřil [HN06] によるその oriented matroid への拡張である。

• oriented matroid の chromatic number

References

[HN06]

Winfried Hochstättler and Jaroslav Nešetřil. “Antisymmetric flows in matroids”. In: European J. Combin. 27.7 (2006), pp. 1129–1134. url: https://doi.org/10.1016/j.ejc.2006.06.018.

[HN07]

Winfried Hochstättler and Robert Nickel. “The flow lattice of oriented matroids”. In: Contrib. Discrete Math. 2.1 (2007), pp. 67–85. url: https://doi.org/10.11575/cdm.v2i1.61952.

[HN08]

Winfried Hochstättler and Robert Nickel. “On the chromatic number of an oriented matroid”. In: J. Combin. Theory Ser. B 98.4 (2008), pp. 698–706. url: https://doi.org/10.1016/j.jctb.2007.10.004.

[Las]

Michał Lasoń. Coloring games and algebraic problems on matroids. arXiv: 1501.00224.

[LRS20]

Lucía López de Medrano, Felipe Rincón, and Kristin Shaw. “Chern-Schwartz-MacPherson cycles of matroids”. In: Proc. Lond. Math. Soc. (3) 120.1 (2020), pp. 1–27. arXiv: 1707.07303. url: https://doi.org/10.1112/plms.12278.

[Tut54]

W. T. Tutte. “A contribution to the theory of chromatic polynomials”. In: Canadian J. Math. 6 (1954), pp. 80–91. url: https://doi.org/10.4153/cjm-1954-010-9.