Matching Complex

与えられたグラフの partial matching の集合は abstract simplicial complex になり, そのグラフの matching complex と呼ばれる。

Wachs の [Wac03] によると, matching complex は, Bouc の [Bou92] で初めて登場したらしい。 Bouc は, 有限群の\(p\)部分群の成す poset の order complex のホモトピー型を考えるために, matching complex を用いた。 この Wachs の survey では, chessboard complex (complete bipartite graph の matching complex) など関連した話題について, その歴史も含めて解説してある。

Poset からは, Hasse diagram としてグラフができるので, その matching complex が考えられるわけである。更に, simplicial complex \(K\) からは, face poset \(F(K)\) として poset ができるので, その matching complex を考えることができる。

Hasse diagram 上の partial matching と言えば, discrete Morse theory であるが, Chari と Joswig [CJ05] は, regular cell complex に対しその上の acyclic partial matching の集合を abstract simplicial complex と考え調べている。これは discrete Morse complex と呼ばれる。

• discrete Morse complex

Regular cell complex の上の acyclic partial matching とは, その face poset の Hasse diagram 上の acyclic partial matching のことなので, より一般に quiver に対しても, acyclic partial matching の成す matching complex の subcomplex として acyclic matching complex が定義される。

• acyclic matching complex

Discrete Morse complex と matching complex の関係は, Celoria と Yerolemou [CY22] により調べられている。

References

[Bou92]

S. Bouc. “Homologie de certains ensembles de \(2\)-sous-groupes des groupes symétriques”. In: J. Algebra 150.1 (1992), pp. 158–186. url: http://dx.doi.org/10.1016/S0021-8693(05)80054-7.

[CJ05]

Manoj K. Chari and Michael Joswig. “Complexes of discrete Morse functions”. In: Discrete Math. 302.1-3 (2005), pp. 39–51. arXiv: math/ 0011234. url: http://dx.doi.org/10.1016/j.disc.2004.07.027.

[CY22]

Daniele Celoria and Naya Yerolemou. “Filtered matchings and simplicial complexes”. In: Australas. J. Combin. 82 (2022), pp. 335–352. arXiv: 2011.02015.

[Wac03]

Michelle L. Wachs. “Topology of matching, chessboard, and general bounded degree graph complexes”. In: Algebra Universalis 49.4 (2003). Dedicated to the memory of Gian-Carlo Rota, pp. 345–385. url: http://dx.doi.org/10.1007/s00012-003-1825-1.