Matroid の応用や関連した分野

Matroid は, もともと graph の cycle の集合やベクトルの一次従属性などの構造を抽象化したものなので, 当然, グラフや線形代数に関連したことには, 様々な応用がある。

Matroid や oriented matroid の幾何学的な応用としては, やはり Gel\('\)fand と MacPherson の [GM92] をまず第一に挙げるべきだろう。それを発展 (抽象化) し, MacPherson は [Mac93] で combinatorial differential manifold と combinatorial vector bundle という概念を定義している。Combinatorial vector bundle は, Anderson の [And99] のように matroid bundle とも呼ばれる。

• matroid bundle

Vector bundle と matroid bundle の比較は自然な問題である。例えば, matroid bundle の分類空間である, combinatorial Grassmannian や matroid Grassmannian や MacPhersonian と呼ばれる poset がある。

• combinatorial Grassmannian or matroid Grassmannian or MacPhersonian

別の方向から matroid と bundle の類似を調べている人もいる。Falk と Proudfoot の [FP02] など。

Igusa は [Igu] で, base を fix したときの matroid の成す category の分類空間のホモトピー型を調べることを提案している。Higher torsion や mapping class group など, 様々な幾何学的応用を念頭に置いているようである。

代数への応用としては, Novik と Postnikov と Sturmfels の [NPS02] がある。Bayer と Sturmfels は, [BS98] で多変数多項式環の monomial ideal \(M\) と CW複体 \(X\) から chain complex \(C_*(X,M)\) を作り,これが \(M\) の free resolution になっているための条件を求めたが, そのような \(M\) と \(X\) の組を oriented matroid を用いて作っている。 可換環論との関係については, Brennan と Epstein の [BE11] を見るとよい。

Matroid の base の上に確率測度を考えているのは, Lyons [Lyo09] である。そしてそれを CW複体の cellular chain complex の boundary に適用している。

Khovanov homology とも関連があるようである。 Champanerkar と Kofman は, link diagram から作られる Tait graph の matroid と Khovanov homology の関係を [CK08] で調べている。

低次元トポロジーとの関係では, 他にも Vassiliev 不変量との関係について調べ た Lando と Zhukov の [LZ] などがある。

複素平面の半平面上で \(0\) にならない多項式を half-plane property を持つ多項式という。最近 Choe と Oxley と Sokal と Wagner [Cho+04] により matroid と関係があることが発見された。その後, 様々な人により研究されている。

Feichtner と Sturmfels の [FS05] の最初に matroid polytope についての解説があることからも分かるように, tropical mathematics とも関係がある。

線型部分空間との関係で, (tropical) Grassmann 多様体との関連もある。 Speyer の [Spe09] など。

基本的な構造なので, 数学以外にも現われる。 数理物理学では, Nieto が中心になって, Chern-Simons theory, 2D-gravity, string theory, supergravity, quantum information theory [NM00; Nie04b; NM03; Nie04a] などへの応用を考えている。 Brunnemann と Rideout は, [BR10] で loop quantum gravity に現われる組み合せ論的構造とよく合うと言っている。

化学 (あるいは生物学?) では, Oliveira らの [Oli+01; BGO] など。

References

[And98]

L. Anderson. “Homotopy groups of the combinatorial Grassmannian”. In: Discrete Comput. Geom. 20.4 (1998), pp. 549–560. url: http://dx.doi.org/10.1007/PL00009401.

[And99]

Laura Anderson. “Matroid bundles”. In: New perspectives in algebraic combinatorics (Berkeley, CA, 1996–97). Vol. 38. Math. Sci. Res. Inst. Publ. Cambridge: Cambridge Univ. Press, 1999, pp. 1–21.

[BE11]

Joseph P. Brennan and Neil Epstein. “Noether normalizations, reductions of ideals, and matroids”. In: Proc. Amer. Math. Soc. 139.8 (2011), pp. 2671–2680. arXiv: 1008 . 0156. url: https://doi.org/10.1090/S0002-9939-2011-10719-6.

[BGO]

C. G. Bailey, D. W. Gull, and J. S. Oliveira. Hypergraphic Oriented Matroid Relational Dependency Flow Models of Chemical Reaction Networks. arXiv: 0902.0847.

[BR10]

Johannes Brunnemann and David Rideout. “Oriented matroids—combinatorial structures underlying loop quantum gravity”. In: Classical Quantum Gravity 27.20 (2010), pp. 205008, 50. arXiv: 1003.2348. url: http://dx.doi.org/10.1088/0264-9381/27/20/205008.

[BS98]

Dave Bayer and Bernd Sturmfels. “Cellular resolutions of monomial modules”. In: J. Reine Angew. Math. 502 (1998), pp. 123–140. arXiv: alg-geom/9711023. url: http://dx.doi.org/10.1515/crll.1998.083.

[Cho+04]

Young-Bin Choe, James G. Oxley, Alan D. Sokal, and David G. Wagner. “Homogeneous multivariate polynomials with the half-plane property”. In: Adv. in Appl. Math. 32.1-2 (2004). Special issue on the Tutte polynomial, pp. 88–187. arXiv: math/0202034. url: http://dx.doi.org/10.1016/S0196-8858(03)00078-2.

[CK08]

Abhijit Champanerkar and Ilya Kofman. “On mutation and Khovanov homology”. In: Commun. Contemp. Math. 10.suppl. 1 (2008), pp. 973–992. arXiv: 0801.4937. url: http://dx.doi.org/10.1142/S0219199708003113.

[FP02]

Michael J. Falk and Nicholas J. Proudfoot. “Parallel connections and bundles of arrangements”. In: Topology Appl. 118.1-2 (2002). Arrangements in Boston: a Conference on Hyperplane Arrangements (1999), pp. 65–83. arXiv: math / 0002094. url: http://dx.doi.org/10.1016/S0166-8641(01)00042-6.

[FS05]

Eva Maria Feichtner and Bernd Sturmfels. “Matroid polytopes, nested sets and Bergman fans”. In: Port. Math. (N.S.) 62.4 (2005), pp. 437–468. arXiv: math/0411260.

[GM92]

I. M. Gel\('\)fand and R. D. MacPherson. “A combinatorial formula for the Pontrjagin classes”. In: Bull. Amer. Math. Soc. (N.S.) 26.2 (1992), pp. 304–309. arXiv: math / 9204231. url: http://dx.doi.org/10.1090/S0273-0979-1992-00282-3.

[Igu]

Kiyoshi Igusa. Families of regular matroids. arXiv: 0911.2014.

[Lyo09]

Russell Lyons. “Random complexes and \(l^2\)-Betti numbers”. In: J. Topol. Anal. 1.2 (2009), pp. 153–175. arXiv: 0811.2933. url: http://dx.doi.org/10.1142/S1793525309000072.

[LZ]

Sergey Lando and Vyacheslav Zhukov. Delta-matroids and Vassiliev invariants. arXiv: 1602.00027.

[Mac93]

Robert MacPherson. “Combinatorial differential manifolds”. In: Topological methods in modern mathematics (Stony Brook, NY, 1991). Houston, TX: Publish or Perish, 1993, pp. 203–221.

[Nie04a]

J. A. Nieto. “Matroids and \(p\)-branes”. In: Adv. Theor. Math. Phys. 8.1 (2004), pp. 177–188. arXiv: hep-th/0310071. url: http://projecteuclid.org/euclid.atmp/1091475316.

[Nie04b]

J. A. Nieto. “Searching for a connection between matroid theory and string theory”. In: J. Math. Phys. 45.1 (2004), pp. 285–301. arXiv: hep-th/0212100. url: http://dx.doi.org/10.1063/1.1625416.

[NM00]

J. A. Nieto and M. C. Marín. “Matroid theory and Chern-Simons”. In: J. Math. Phys. 41.12 (2000), pp. 7997–8005. arXiv: hep-th/ 0005117. url: http://dx.doi.org/10.1063/1.1319518.

[NM03]

J. A. Nieto and M. C. Marín. “Search for a “gravitoid” theory”. In: Internat. J. Modern Phys. A 18.28 (2003), pp. 5261–5276. arXiv: hep - th / 0302193. url: http://dx.doi.org/10.1142/S0217751X0301591X.

[NPS02]

Isabella Novik, Alexander Postnikov, and Bernd Sturmfels. “Syzygies of oriented matroids”. In: Duke Math. J. 111.2 (2002), pp. 287–317. arXiv: math/0009241. url: http://dx.doi.org/10.1215/S0012-7094-02-11124-7.

[Oli+01]

Joseph Oliveira, Colin Bailey, Janet Jones-Oliveira, and David Dixon. “An algebraic-combinatorial model for the identification and mapping of biochemical pathways”. In: Bulletin of Mathematical Biology 63.6 (Nov. 2001), pp. 1163–1196. url: http://dx.doi.org/10.1006/bulm.2001.0263.

[Spe09]

David E. Speyer. “A matroid invariant via the \(K\)-theory of the Grassmannian”. In: Adv. Math. 221.3 (2009), pp. 882–913. arXiv: math/0603551. url: http://dx.doi.org/10.1016/j.aim.2009.01.010.