Simplicial Complexes Constructed From Matroids

Matroid からは, 様々な simplicial complex が定義される。 例えば, Björner の [Bjö92] を見るとよい。

そもそも matroid の定義として independence set に関する公理を用いると, independence set の集合として abstract simplicial complex ができるので, matroid 自身 simplicial complex の一種と思うこともできる。

他にも, 目にしたものを挙げると以下のようになる。 Oriented matroid の場合も含めている。

• matroid の independence complex
• matroid の broken circuit complex
• matroid の Bergman complex や Bergman fan
• MacPhersonian or matroid Grassmannian [And98; And99b; And99a; AD02]
• Salvetti complex of oriented matroid
• matroid Steiner complex [CP89; Cha00]
• external activity complex [ACS16]
• extension space [SZ93]
• standard complex [ESS22]

Dinh [Le16] によると, broken circuit complex のアイデアは, Whitney の [Whi32] まで遡るらしい。その後, Rota [Rot64], Wilf [Wil76], Brylawski [Bry77] などにより調べられた。

References

[ACS16]

Federico Ardila, Federico Castillo, and José Alejandro Samper. “The topology of the external activity complex of a matroid”. In: Electron. J. Combin. 23.3 (2016), Paper 3.8, 20. arXiv: 1410.3870. url: https://doi.org/10.37236/5042.

[AD02]

Laura Anderson and James F. Davis. “Mod 2 cohomology of combinatorial Grassmannians”. In: Selecta Math. (N.S.) 8.2 (2002), pp. 161–200. arXiv: math/9911158. url: http://dx.doi.org/10.1007/s00029-002-8104-4.

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

[And99a]

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.

[And99b]

Laura Anderson. “Topology of combinatorial differential manifolds”. In: Topology 38.1 (1999), pp. 197–221. url: http://dx.doi.org/10.1016/S0040-9383(98)00011-1.

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

[Bry77]

Tom Brylawski. “The broken-circuit complex”. In: Trans. Amer. Math. Soc. 234.2 (1977), pp. 417–433. url: http://dx.doi.org/10.2307/1997928.

[Cha00]

Manoj K. Chari. “On discrete Morse functions and combinatorial decompositions”. In: Discrete Math. 217.1-3 (2000). Formal power series and algebraic combinatorics (Vienna, 1997), pp. 101–113. url: http://dx.doi.org/10.1016/S0012-365X(99)00258-7.

[CP89]

Charles J. Colbourn and William R. Pulleyblank. “Matroid Steiner problems, the Tutte polynomial and network reliability”. In: J. Combin. Theory Ser. B 47.1 (1989), pp. 20–31. url: http://dx.doi.org/10.1016/0095-8956(89)90062-2.

[ESS22]

Alexander Engström, Raman Sanyal, and Christian Stump. “Standard complexes of matroids and lattice paths”. In: Vietnam J. Math. 50.3 (2022), pp. 763–779. arXiv: 1911.12290. url: https://doi.org/10.1007/s10013-021-00546-z.

[Le16]

Dinh Van Le. “Broken circuit complexes of series-parallel networks”. In: European J. Combin. 51 (2016), pp. 12–36. arXiv: 1404.1728. url: https://doi.org/10.1016/j.ejc.2015.04.009.

[Rot64]

Gian-Carlo Rota. “On the foundations of combinatorial theory. I. Theory of Möbius functions”. In: Z. Wahrscheinlichkeitstheorie und Verw. Gebiete 2 (1964), 340–368 (1964).

[SZ93]

Bernd Sturmfels and Günter M. Ziegler. “Extension spaces of oriented matroids”. In: Discrete Comput. Geom. 10.1 (1993), pp. 23–45. url: http://dx.doi.org/10.1007/BF02573961.

[Whi32]

Hassler Whitney. “A logical expansion in mathematics”. In: Bull. Amer. Math. Soc. 38.8 (1932), pp. 572–579. url: http://dx.doi.org/10.1090/S0002-9904-1932-05460-X.

[Wil76]

Herbert S. Wilf. “Which polynomials are chromatic?” In: Colloquio Internazionale sulle Teorie Combinatorie (Roma, 1973), Tomo I. Rome: Accad. Naz. Lincei, 1976, 247–256. Atti dei Convegni Lincei, No. 17.