Matroids

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

誰が最初に発見したかはともかく, 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] である。

他にも様々な本や解説が書かれている。目についたものを挙げると以下のようになる。

• Welsh の本 [Wel76]
• Kung の本 [Kun86]
• Björner の [Bjö92]
• Reiner の lecture notes [Rei]
• Ardila の enumerative combinatorics の 解説 [Ard15] の第7章
• 代数幾何学者を対象にした Eric Katz の survey [Kat16]
• Michałek と Sturmfels の本 [MS21] の Chapter 13
• Ardila による Notices of A.M.S. の記事 [Ard18]
• Ardila の ICM 2022 のための survey [Ard23]

Eric Katz の survey の 代数幾何学的視点は, 元々は, Gel\('\)fand, Goresky, MacPherson, Serganova の [Gel+87] により導入されたようであるが, 当然最近の June Huh の仕事 [Huh12] に依るところも大きい, と思う。

Huh が Fields medal を授与された 2022年の ICM の Proceedings には, この Huh の仕事についていくつかの解説が掲載されている。Okounkov の [Oko23], Kalai の [Kal23], Huh 自身の [Huh23] など。

Matroid と oriented matroid に関する基本的なことについては, 次のページにまとめた。

• matroid と oriented matroid の基本

Huh の仕事では, matroid の Chow ring が重要な役割を果すが, このようなmatroidの不変量やmatroidの応用については, 次にまとめた。

• matroid の不変量
• matroid の応用

当然であるが, matroid 全体を category とみなすことができる。

• category of matroids

Category とみなす以外にも, matroid 全体を考える方法はいくつかある。 例えば, matroid の不変量として, valuation であるもの, つまり

をみたすものは数多くあるが, この valuative であるという性質に関し universal な群として valuative group が定義される。 例えば, Eur, Huh, Larson の [EHL23] に定義がある。

• valuative group of matroids

より古くは, Schmitt [Sch94] が Hopf algebra を構成することを考えている。 Crapo と Schmitt [CS05; CS08] により調べられている。

• Schmitt の matroid-minor Hopf algebra

これらの代数的構造は, matroid に対する操作を記述するものである。既存の matroid から新しい matroid を作る方法は, 他にも色々考えられている。

• derived matroid [FJK23]

そして, 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.

[Ard15]

Federico Ardila. “Algebraic and geometric methods in enumerative combinatorics”. In: Handbook of enumerative combinatorics. Discrete Math. Appl. (Boca Raton). CRC Press, Boca Raton, FL, 2015, pp. 3–172. arXiv: 1409.2562.

[Ard18]

Federico Ardila. “The geometry of matroids”. In: Notices Amer. Math. Soc. 65.8 (2018), pp. 902–908.

[Ard23]

Federico Ardila-Mantilla. “The geometry of geometries: matroid theory, old and new”. In: ICM—International Congress of Mathematicians. Vol. VI. Sections 12–14. EMS Press, Berlin, [2023] ©2023, pp. 4510–4541. arXiv: 2111.08726.

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

[Bjö92]

Anders Björner. “The homology and shellability of matroids and geometric lattices”. In: Matroid applications. Vol. 40. Encyclopedia Math. Appl. Cambridge Univ. Press, Cambridge, 1992, pp. 226–283. url: http://dx.doi.org/10.1017/CBO9780511662041.008.

[CS05]

Henry Crapo and William Schmitt. “A free subalgebra of the algebra of matroids”. In: European J. Combin. 26.7 (2005), pp. 1066–1085. arXiv: math/0409028. url: http://dx.doi.org/10.1016/j.ejc.2004.05.006.

[CS08]

Henry Crapo and William Schmitt. “Primitive elements in the matroid-minor Hopf algebra”. In: J. Algebraic Combin. 28.1 (2008), pp. 43–64. arXiv: math/0511033. url: http://dx.doi.org/10.1007/s10801-007-0066-3.

[EHL23]

Christopher Eur, June Huh, and Matt Larson. “Stellahedral geometry of matroids”. In: Forum Math. Pi 11 (2023), Paper No. e24, 48. arXiv: 2207.10605. url: https://doi.org/10.1017/fmp.2023.24.

[FJK23]

Ragnar Freij-Hollanti, Relinde Jurrius, and Olga Kuznetsova. “Combinatorial derived matroids”. In: Electron. J. Combin. 30.2 (2023), Paper No. 2.8, 28. arXiv: 2206.06881. url: https://doi.org/10.37236/11327.

[Gel+87]

I. M. Gel\('\)fand, R. M. Goresky, R. D. MacPherson, and V. V. Serganova. “Combinatorial geometries, convex polyhedra, and Schubert cells”. In: Adv. in Math. 63.3 (1987), pp. 301–316. url: http://dx.doi.org/10.1016/0001-8708(87)90059-4.

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

[Huh23]

June Huh. “Combinatorics and Hodge theory”. In: ICM—International Congress of Mathematicians. Vol. 1. Prize lectures. EMS Press, Berlin, [2023] ©2023, pp. 212–239.

[Kal23]

Gil Kalai. “The work of June Huh”. In: ICM—International Congress of Mathematicians. Vol. 1. Prize lectures. EMS Press, Berlin, [2023] ©2023, pp. 50–65.

[Kat16]

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

[Kun86]

Joseph P. S. Kung. A source book in matroid theory. With a foreword by Gian-Carlo Rota. Birkhäuser Boston, Inc., Boston, MA, 1986, p. 413. isbn: 0-8176-3173-9. url: https://doi.org/10.1007/978-1-4684-9199-9.

[MS21]

Mateusz Michałek and Bernd Sturmfels. Invitation to nonlinear algebra. Vol. 211. Graduate Studies in Mathematics. American Mathematical Society, Providence, RI, [2021] ©2021, pp. xiii+226. isbn: 978-1-4704-5367-1. url: https://doi.org/10.1090/gsm/211.

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

[Oko23]

Andrei Okounkov. “Combinatorial geometry takes the lead”. In: ICM—International Congress of Mathematicians. Vol. 1. Prize lectures. EMS Press, Berlin, [2023] ©2023, pp. 414–458. arXiv: 2207.03875.

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

[Rei]

Victor Reiner. Lectures on Matroids and Oriented Matroids. url: https://www-users.cse.umn.edu/~reiner/Talks/Vienna05/Lectures.pdf.

[Sch94]

William R. Schmitt. “Incidence Hopf algebras”. In: J. Pure Appl. Algebra 96.3 (1994), pp. 299–330. url: http://dx.doi.org/10.1016/0022-4049(94)90105-8.

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