Matroids

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] に依るところが大きい。 Huh が Fields medal を授与された 2022年の ICM の Proceedings には, この Huh の仕事についていくつかの解説が掲載されている。Okounkov の [Oko23], Kalai の [Kal23], Huh 自身の [Huh23] など。

• 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

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

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

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

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

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