様々な matroid

Matroid には, 様々な変種が定義され, 用いられている。

• oriented matroid
• symplectic matroid, Lagrangian symplectic matroid [BGW98], oriented Lagrangian matroid [BBG; Boo+01]
• orthogonal matroid [VW01]
• flag matroid
• Coxeter matroid [BGW03]
• \(\Delta \)-matroid [Bou88]
• valuated matroid [DW92]
• valuated \(\Delta \)-matroid [DW91b]
• simplicial matroid [CR71; CLL09]
• poset matroid [BNP98]
• matroid scheme [Bib]

Symplectic matroid や orthogonal matroid は, \(\Delta \)-matroid, よって Coxeter matroid の特別な場合である。

Rincón [Rin12] によると, \(\Delta \)-matroid については, Bouchet の [Bou87; Bou88; Bou97; Bou98] と Borovik, Gel\('\)fand, White の Coxeter matroid の本 [BGW03] を見るとよいようである。

Chun, Moffatt, Noble, Rueckriemen [Chu+19] によると, matroid が graph の一般化になっているように, \(\Delta \)-matroid は, ribbon graph の一般化になっているようである。 よっ て Bollobás-Riordan polynomial なども \(\Delta \)-matroid に拡張できる。

Matroid scheme は, Abelian variety の中の subvariety の成す arrangement の組み合せ論的構造を表すものとして, Bibby により導入されたものである。

超平面配置では, 実超平面配置の複素化が重要であり, oriented matroid の複素版もいくつか考えられている。 「複素化」されたものに限定するなら, oriented matroid の sign vector の取る値 \(\{0,\pm 1\}\) を \(\{0, \pm 1, \pm i\}\) にすればよい。これは, Björner と Zieger の [BZ92a] で詳しく調べられている。一方, 実数から来ていないものを考えるには, \(\{0\}\cup S^1\) に値を持つ sign vector を考えるべきだとする立場もある。Anderson と Delucchi [AD12] により詳しく調べられている。 Anderson と Delucchi の導入したものは, [DHS] では phased matroid と呼ばれている。元の論文では, complex matroid と呼ばれているが, その名前は Ziegler により [Zie93] で使われているから名前を変えたのだろう。 より一般には, fuzzy ring に係数を持つ matroid を Dress [Dre86; DW89; DW91a] が定義 している。

• phased matroid
• fuzzy ring に係数を持つ matroid

それらの一般化として, Matthew Baker [BB] が hyperfield を用いた matroid over a hyperfield を導入している。

• matroid over a hyperfield

この2つを比較するために, Giansiracusa, Jun, Lorscheid [GJL17] が hyperfield の category を fuzzy ring の category へ埋め込んでいる。このように見ると Baker の hyperfield 上の matroid は, Dress の fuzzy ring に係数を持つ matroid とみなせるようである。

その更なる一般化として, Baker と Bowler [BB19] は, tract という構造を導入し, matroid over tracts という概念を導入している。

• matroid over tracts

D’Adderio と Moci [DM13] は, toric arrangement に関連したものとして, arithmetic matroid を定義している。 Moci は, Fink と共に [FM16] その一般化として matroid over a ring という拡張を導入している。 Pagaria [Pag20] は, oriented arithmetic matroid を定義している。

• arithmetic matroid
• matroid over a ring
• oriented arithmetic matroid

Fink と Moci の [FM19] によると, matroid over a ring は, valuated matroid の一般化にもなっているようである。

一般化として greedoid というものもある。

• greedoid

1980年代に, Korte と Lovász により導入された。Björner と Ziegler の解説 [BZ92b] がある。Korte と Lovász と Schrader による本 [KLS91] もある。 その oriented version として, Saliola と Thomas が oriented interval greedoid というものを [ST12] で定義している。

無限 matroid も考えられているが, Bruhn と Wollan の [BW12] によると, 色々誤解があるようである。Oxley の [Oxl78; Oxl92] が有名であるが, Bruhn と Wollan によると, それより前に Higgs [Hig69a; Hig69b; Hig69c] により定義されていたらしい。 Oxley の定義の方が単純なので, そちらが有名になって Higgs のが忘れられていたようであるが, Bruhn らの [Bru+13; BD11] で有限の場合と平行な議論ができることが主張されている。

• finitary matroid
• infinite matroid の公理

Aigner-Horev, Carmesin, Fröhlich の[ACF] によると, 一般には infinite matroid の union は matroid にはならない。彼等は, finitary matroid の union はまた finitary matroid になることを示している。また [ACF18] では, finitary matroid より大きな nearly finitary matroid という class を定義している。

Multiset 版として polymatroid というものもある。

• polymatroid

Tropical hyperplane arrangement に対応したものもある。Ardila と Develin の[AD09] や Dochtermann, Joswig, Sanyal の [DJS12] など。

• tropical oriented matroid

Horn [Hora; Horb] は, Folkman と Lawrence による oriented matroid の topological representation theorem [FL78] の tropical 版を証明している。

Brennan と Epstein [BE11] は, 位相空間と matroid を合わせたものを generic matroid として定義しているが, その motivation は 可換環論のようである。

Lawrence [Law83] により導入された lopsided set というものもある。それと oriented matroid を合せた一般化が combinatorial oriented matroid として Bandelt と Chepoi と Knauer [BCK18] により提案されている。

• lopsided set
• combinatorial oriented matroid

Jurrius と Pellikaan [JP18] は matroid の \(q\)-analogue として, \(q\)-matroid の概念を導入している。Jurrius は, Gorla, López, Ravagnani と共に [Gor+20] で, \(q\)-polymatroid も導入している。

• \(q\)-matroid や \(q\)-polymatroid

References

[ACF]

Elad Aigner-Horev, Johannes Carmesin, and Jan-Oliver Fröhlich. Infinite matroid union. arXiv: 1111.0602.

[ACF18]

Elad Aigner-Horev, Johannes Carmesin, and Jan-Oliver Fröhlich. “On the intersection of infinite matroids”. In: Discrete Math. 341.6 (2018), pp. 1582–1596. arXiv: 1111.0606. url: https://doi.org/10.1016/j.disc.2018.02.018.

[AD09]

Federico Ardila and Mike Develin. “Tropical hyperplane arrangements and oriented matroids”. In: Math. Z. 262.4 (2009), pp. 795–816. arXiv: 0706.2920. url: http://dx.doi.org/10.1007/s00209-008-0400-z.

[AD12]

Laura Anderson and Emanuele Delucchi. “Foundations for a theory of complex matroids”. In: Discrete Comput. Geom. 48.4 (2012), pp. 807–846. arXiv: 1005.3560. url: https://doi.org/10.1007/s00454-012-9458-9.

[BB]

Matthew Baker and Nathan Bowler. Matroids over hyperfields. arXiv: 1601.01204.

[BB19]

Matthew Baker and Nathan Bowler. “Matroids over partial hyperstructures”. In: Adv. Math. 343 (2019), pp. 821–863. arXiv: 1709.09707. url: https://doi.org/10.1016/j.aim.2018.12.004.

[BBG]

Richard F. Booth, Alexandre V. Borovik, and Israel Gelfand. Lagrangian Matroids associated with Maps on Orientable Surfaces. arXiv: math/0010236.

[BCK18]

Hans-Jürgen Bandelt, Victor Chepoi, and Kolja Knauer. “COMs: complexes of oriented matroids”. In: J. Combin. Theory Ser. A 156 (2018), pp. 195–237. arXiv: 1507 . 06111. url: https://doi.org/10.1016/j.jcta.2018.01.002.

[BD11]

Henning Bruhn and Reinhard Diestel. “Infinite matroids in graphs”. In: Discrete Math. 311.15 (2011), pp. 1461–1471. arXiv: 1011.4749. url: http://dx.doi.org/10.1016/j.disc.2010.12.015.

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

[BGW03]

Alexandre V. Borovik, I. M. Gelfand, and Neil White. Coxeter matroids. Vol. 216. Progress in Mathematics. Boston, MA: Birkhäuser Boston Inc., 2003, pp. xxii+264. isbn: 0-8176-3764-8. url: http://dx.doi.org/10.1007/978-1-4612-2066-4.

[BGW98]

Alexandre V. Borovik, Israel Gelfand, and Neil White. “Symplectic matroids”. In: J. Algebraic Combin. 8.3 (1998), pp. 235–252. url: http://dx.doi.org/10.1023/A:1008610715466.

[Bib]

Christin Bibby. Matroid schemes and geometric posets. arXiv: 2203. 15094.

[BNP98]

Marilena Barnabei, Giorgio Nicoletti, and Luigi Pezzoli. “Matroids on partially ordered sets”. In: Adv. in Appl. Math. 21.1 (1998), pp. 78–112. url: http://dx.doi.org/10.1006/aama.1998.0583.

[Boo+01]

Richard F. Booth, Alexandre V. Borovik, Israel M. Gelfand, and Neil White. “Oriented Lagrangian matroids”. In: European J. Combin. 22.5 (2001). Combinatorial geometries (Luminy, 1999), pp. 639–656. arXiv: math / 0010237. url: http://dx.doi.org/10.1006/eujc.2000.0485.

[Bou87]

André Bouchet. “Greedy algorithm and symmetric matroids”. In: Math. Programming 38.2 (1987), pp. 147–159. url: http://dx.doi.org/10.1007/BF02604639.

[Bou88]

A. Bouchet. “Representability of \(\triangle \)-matroids”. In: Combinatorics (Eger, 1987). Vol. 52. Colloq. Math. Soc. János Bolyai. Amsterdam: North-Holland, 1988, pp. 167–182.

[Bou97]

André Bouchet. “Multimatroids. I. Coverings by independent sets”. In: SIAM J. Discrete Math. 10.4 (1997), pp. 626–646. url: http://dx.doi.org/10.1137/S0895480193242591.

[Bou98]

André Bouchet. “Multimatroids. II. Orthogonality, minors and connectivity”. In: Electron. J. Combin. 5 (1998), Research Paper 8, 25 pp. (electronic). url: http://www.combinatorics.org/Volume_5/Abstracts/v5i1r8.html.

[Bru+13]

Henning Bruhn, Reinhard Diestel, Matthias Kriesell, Rudi Pendavingh, and Paul Wollan. “Axioms for infinite matroids”. In: Adv. Math. 239 (2013), pp. 18–46. arXiv: 1003.3919. url: http://dx.doi.org/10.1016/j.aim.2013.01.011.

[BW12]

Henning Bruhn and Paul Wollan. “Finite connectivity in infinite matroids”. In: European J. Combin. 33.8 (2012), pp. 1900–1912. arXiv: 1101.5621. url: http://dx.doi.org/10.1016/j.ejc.2012.05.006.

[BZ92a]

Anders Björner and Günter M. Ziegler. “Combinatorial stratification of complex arrangements”. In: J. Amer. Math. Soc. 5.1 (1992), pp. 105–149. url: http://dx.doi.org/10.2307/2152753.

[BZ92b]

Anders Björner and Günter M. Ziegler. “Introduction to greedoids”. In: Matroid applications. Vol. 40. Encyclopedia Math. Appl. Cambridge: Cambridge Univ. Press, 1992, pp. 284–357. url: http://dx.doi.org/10.1017/CBO9780511662041.009.

[Chu+19]

Carolyn Chun, Iain Moffatt, Steven D. Noble, and Ralf Rueckriemen. “Matroids, delta-matroids and embedded graphs”. In: J. Combin. Theory Ser. A 167 (2019), pp. 7–59. arXiv: 1403.0920. url: https://doi.org/10.1016/j.jcta.2019.02.023.

[CLL09]

Raul Cordovil, Manoel Lemos, and Cláudia Linhares Sales. “Dirac’s theorem on simplicial matroids”. In: Ann. Comb. 13.1 (2009), pp. 53–63. arXiv: math/0609119. url: http://dx.doi.org/10.1007/s00026-009-0012-2.

[CR71]

Henry H. Crapo and Gian-Carlo Rota. “Simplicial geometries”. In: Combinatorics (Proc. Sympos. Pure Math., Vol. XIX, Univ. California, Los Angeles, Calif., 1968). Providence, R.I.: Amer. Math. Soc., 1971, pp. 71–75.

[DHS]

Emanuele Delucchi, Linard Hoessly, and Elia Saini. Realization spaces of matroids over hyperfields. arXiv: 1504.07109.

[DJS12]

Anton Dochtermann, Michael Joswig, and Raman Sanyal. “Tropical types and associated cellular resolutions”. In: J. Algebra 356 (2012), pp. 304–324. arXiv: 1001 . 0237. url: http://dx.doi.org/10.1016/j.jalgebra.2011.12.028.

[DM13]

Michele D’Adderio and Luca Moci. “Arithmetic matroids, the Tutte polynomial and toric arrangements”. In: Adv. Math. 232 (2013), pp. 335–367. arXiv: 1105.3220. url: http://dx.doi.org/10.1016/j.aim.2012.09.001.

[Dre86]

Andreas W. M. Dress. “Duality theory for finite and infinite matroids with coefficients”. In: Adv. in Math. 59.2 (1986), pp. 97–123. url: http://dx.doi.org/10.1016/0001-8708(86)90047-2.

[DW89]

Andreas W. M. Dress and Walter Wenzel. “Geometric algebra for combinatorial geometries”. In: Adv. Math. 77.1 (1989), pp. 1–36. url: http://dx.doi.org/10.1016/0001-8708(89)90013-3.

[DW91a]

Andreas Dress and Walter Wenzel. “Grassmann-Plücker relations and matroids with coefficients”. In: Adv. Math. 86.1 (1991), pp. 68–110. url: http://dx.doi.org/10.1016/0001-8708(91)90036-7.

[DW91b]

Andreas W. M. Dress and Walter Wenzel. “A greedy-algorithm characterization of valuated \(\Delta \)-matroids”. In: Appl. Math. Lett. 4.6 (1991), pp. 55–58. url: http://dx.doi.org/10.1016/0893-9659(91)90075-7.

[DW92]

Andreas W. M. Dress and Walter Wenzel. “Valuated matroids”. In: Adv. Math. 93.2 (1992), pp. 214–250. url: http://dx.doi.org/10.1016/0001-8708(92)90028-J.

[FL78]

Jon Folkman and Jim Lawrence. “Oriented matroids”. In: J. Combin. Theory Ser. B 25.2 (1978), pp. 199–236. url: http://dx.doi.org/10.1016/0095-8956(78)90039-4.

[FM16]

Alex Fink and Luca Moci. “Matroids over a ring”. In: J. Eur. Math. Soc. (JEMS) 18.4 (2016), pp. 681–731. arXiv: 1209.6571. url: https://doi.org/10.4171/JEMS/600.

[FM19]

Alex Fink and Luca Moci. “Polyhedra and parameter spaces for matroids over valuation rings”. In: Adv. Math. 343 (2019), pp. 448–494. arXiv: 1707.01026. url: https://doi.org/10.1016/j.aim.2018.11.009.

[GJL17]

Jeffrey Giansiracusa, Jaiung Jun, and Oliver Lorscheid. “On the relation between hyperrings and fuzzy rings”. In: Beitr. Algebra Geom. 58.4 (2017), pp. 735–764. arXiv: 1607 . 01973. url: https://doi.org/10.1007/s13366-017-0347-5.

[Gor+20]

Elisa Gorla, Relinde Jurrius, Hiram H. López, and Alberto Ravagnani. “Rank-metric codes and \(q\)-polymatroids”. In: J. Algebraic Combin. 52.1 (2020), pp. 1–19. arXiv: 1803 . 10844. url: https://doi.org/10.1007/s10801-019-00889-4.

[Hig69a]

D. A. Higgs. “Infinite graphs and matroids”. In: Recent Progress in Combinatorics (Proc. Third Waterloo Conf. on Combinatorics, 1968). Academic Press, New York, 1969, pp. 245–253.

[Hig69b]

D. A. Higgs. “Matroids and duality”. In: Colloq. Math. 20 (1969), pp. 215–220. url: https://doi.org/10.4064/cm-20-2-215-220.

[Hig69c]

Denis Higgs. “Equicardinality of bases in \(B\)-matroids”. In: Canad. Math. Bull. 12 (1969), pp. 861–862. url: https://doi.org/10.4153/CMB-1969-112-6.

[Hora]

Silke Horn. A Topological Representation Theorem for Tropical Oriented Matroids: Part I. arXiv: 1212.0714.

[Horb]

Silke Horn. A Topological Representation Theorem for Tropical Oriented Matroids: Part II. arXiv: 1212.2080.

[JP18]

Relinde Jurrius and Ruud Pellikaan. “Defining the \(q\)-analogue of a matroid”. In: Electron. J. Combin. 25.3 (2018), Paper No. 3.2, 32. arXiv: 1610.09250. url: https://doi.org/10.37236/6569.

[KLS91]

Bernhard Korte, László Lovász, and Rainer Schrader. Greedoids. Vol. 4. Algorithms and Combinatorics. Berlin: Springer-Verlag, 1991, pp. viii+211. isbn: 3-540-18190-3. url: http://dx.doi.org/10.1007/978-3-642-58191-5.

[Law83]

Jim Lawrence. “Lopsided sets and orthant-intersection by convex sets”. In: Pacific J. Math. 104.1 (1983), pp. 155–173. url: http://projecteuclid.org/euclid.pjm/1102723824.

[Oxl78]

James G. Oxley. “Infinite matroids”. In: Proc. London Math. Soc. (3) 37.2 (1978), pp. 259–272. url: http://dx.doi.org/10.1112/plms/s3-37.2.259.

[Oxl92]

James Oxley. “Infinite matroids”. In: Matroid applications. Vol. 40. Encyclopedia Math. Appl. Cambridge: Cambridge Univ. Press, 1992, pp. 73–90.

[Pag20]

Roberto Pagaria. “Orientable arithmetic matroids”. In: Discrete Math. 343.6 (2020), pp. 111872, 8. arXiv: 1805 . 11888. url: https://doi.org/10.1016/j.disc.2020.111872.

[Rin12]

Felipe Rincón. “Isotropical linear spaces and valuated Delta-matroids”. In: J. Combin. Theory Ser. A 119.1 (2012), pp. 14–32. arXiv: 1004. 4950. url: https://doi.org/10.1016/j.jcta.2011.08.001.

[ST12]

Franco Saliola and Hugh Thomas. “Oriented interval greedoids”. In: Discrete Comput. Geom. 47.1 (2012), pp. 64–105. arXiv: 0909. 1300. url: http://dx.doi.org/10.1007/s00454-011-9383-3.

[VW01]

Andrew Vince and Neil White. “Orthogonal matroids”. In: J. Algebraic Combin. 13.3 (2001), pp. 295–315. url: http://dx.doi.org/10.1023/A:1011212331779.

[Zie93]

Günter M. Ziegler. “Higher Bruhat orders and cyclic hyperplane arrangements”. In: Topology 32.2 (1993), pp. 259–279. url: http://dx.doi.org/10.1016/0040-9383(93)90019-R.