Numerical Invariants of Matroids

Matroid は, graph の一般化であるので, 様々な graph の不変量の matroid への拡張が考えられている。

まずは, chromatic number の類似であるが, Lasoń が, [Las15] や thesis [Las] で考えているものがある。ただし, それは graph では, 頂点ではなく, 辺の色付けに対応するものである。

• Lasoń の chromatic number

頂点の色付けに対応するものは, Lindström の [Lin78] で characteristic polynomial を使って定義されている。

• Lindström の chromatic number

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

他にも, 以下のような matroid の不変量がある。 たまたま目にしたものを記録しただけであるが。

• amalgam width [MT13]
• fixing number and the distinguishing number [GMN16]
• anti-Ramsey number に関連した不変量 [MM18],

References

[GMN16]

Gary Gordon, Jennifer McNulty, and Nancy Ann Neudauer. “Fixing numbers for matroids”. In: Graphs Combin. 32.1 (2016), pp. 133–146. arXiv: 1307.7460. url: https://doi.org/10.1007/s00373-015-1540-7.

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

[Las15]

Michał Lasoń. “List coloring of matroids and base exchange properties”. In: European J. Combin. 49 (2015), pp. 265–268. arXiv: 1412.3341. url: https://doi.org/10.1016/j.ejc.2015.04.004.

[Lin78]

Bernt Lindström. “On the chromatic number of regular matroids”. In: J. Combin. Theory Ser. B 24.3 (1978), pp. 367–369. url: https://doi.org/10.1016/0095-8956(78)90057-6.

[MM18]

Criel Merino and Juan José Montellano-Ballesteros. “Some heterochromatic theorems for matroids”. In: Discrete Math. 341.10 (2018), pp. 2694–2699. arXiv: 1708.08562. url: https://doi.org/10.1016/j.disc.2018.06.030.

[MT13]

Lukáš Mach and Tomáš Toufar. “Amalgam width of matroids”. In: Parameterized and exact computation. Vol. 8246. Lecture Notes in Comput. Sci. Springer, Cham, 2013, pp. 268–280. arXiv: 1304.0299. url: https://doi.org/10.1007/978-3-319-03898-8_23.

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