Matroid

Matroid は, Whitney により [Whi35] でベクトルの一次従属性を抽象化するものとして導入されたものである, と思っていたのだが, 筑波大学数学系にあった「中澤武雄の業績」というページ (今は存在しない) によると, どうやら同じ1935年に日本でも独立に matroid の概念が発見されていたらしい。この中澤武雄という数学者については, Springer (Birkhäuser) から本 [NK09] が出た。

誰が最初に発見したかはともかく, matroid は 組み合せ論では重要な概念である。 特に, 符号付き matroid とも言うべき oriented matroid は, トポロジーにも色々応用がある。例えば, Gel\('\)fand と MacPherson の Pontrjagin class の公式などで使われている。

5人組の oriented matroid 本 [Bjö+99] に挙げてある (oriented でない) matroid の参考文献は, Welsh の [Wel76], Aigner の [Aig79], White の [Whi86; Whi87; Whi92], Oxley の [Oxl92] である。 代数幾何学者を対象にした survey として Eric Katz の [Kat16] もある。

• matroid と oriented matroid の基本

この代数幾何学との関連 (類似) は, June Huh の仕事 [Huh12] に依るところが大きい。Katz の解説は, Huh との characteristic polynomial の log-concavity の証明 [HK12] を目標にしている。 また, Adiprasito との [AHK18] では, matroid の Chow ring に対し Hodge theory の類似が展開されている。 他にも, matroid に対しては, 超平面配置やグラフなどに対して定義されていた不変量の拡張が各種定義されている。

• matroid の不変量
• matroid の応用

そして, oriented matroid 以外にも, 実に様々な matroid の変種が定義されていて面白い。

• 様々な matroid

References

[AHK18]

Karim Adiprasito, June Huh, and Eric Katz. “Hodge theory for combinatorial geometries”. In: Ann. of Math. (2) 188.2 (2018), pp. 381–452. arXiv: 1511.02888. url: https://doi.org/10.4007/annals.2018.188.2.1.

[Aig79]

Martin Aigner. Combinatorial theory. Vol. 234. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]. Berlin: Springer-Verlag, 1979, pp. viii+483. isbn: 0-387-90376-3.

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

[HK12]

June Huh and Eric Katz. “Log-concavity of characteristic polynomials and the Bergman fan of matroids”. In: Math. Ann. 354.3 (2012), pp. 1103–1116. arXiv: 1104 . 2519. url: https://doi.org/10.1007/s00208-011-0777-6.

[Huh12]

June Huh. “Milnor numbers of projective hypersurfaces and the chromatic polynomial of graphs”. In: J. Amer. Math. Soc. 25.3 (2012), pp. 907–927. arXiv: 1008 . 4749. url: https://doi.org/10.1090/S0894-0347-2012-00731-0.

[Kat16]

Eric Katz. “Matroid theory for algebraic geometers”. In: Nonarchimedean and tropical geometry. Simons Symp. Springer, [Cham], 2016, pp. 435–517. arXiv: 1409.3503.

[NK09]

Hirokazu Nishimura and Susumu Kuroda, eds. A lost mathematician, Takeo Nakasawa. The forgotten father of matroid theory. Basel: Birkhäuser Verlag, 2009, pp. xii+234. isbn: 978-3-7643-8572-9. url: http://dx.doi.org/10.1007/978-3-7643-8573-6.

[Oxl92]

James G. Oxley. Matroid theory. Oxford Science Publications. New York: The Clarendon Press Oxford University Press, 1992, p. xii 532. isbn: 0-19-853563-5.

[Wel76]

D. J. A. Welsh. Matroid theory. L. M. S. Monographs, No. 8. London: Academic Press [Harcourt Brace Jovanovich Publishers], 1976, pp. xi+433.

[Whi35]

Hassler Whitney. “On the Abstract Properties of Linear Dependence”. In: Amer. J. Math. 57.3 (1935), pp. 509–533. url: http://dx.doi.org/10.2307/2371182.

[Whi86]

Neil White, ed. Theory of matroids. Vol. 26. Encyclopedia of Mathematics and its Applications. Cambridge University Press, Cambridge, 1986, pp. xviii+316. isbn: 0-521-30937-9. url: http://dx.doi.org/10.1017/CBO9780511629563.

[Whi87]

Neil White, ed. Combinatorial geometries. Vol. 29. Encyclopedia of Mathematics and its Applications. Cambridge University Press, Cambridge, 1987, pp. xii+212. isbn: 0-521-33339-3.

[Whi92]

Neil White, ed. Matroid applications. Vol. 40. Encyclopedia of Mathematics and its Applications. Cambridge University Press, Cambridge, 1992, pp. xii+363. isbn: 0-521-38165-7. url: http://dx.doi.org/10.1017/CBO9780511662041.