Simplicial Complexes Defined by Matchings on Graphs

与えられた グラフの 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] により調べられている。

Matching complex は, maximal matching を最大次元の単体として定義される abstract simplicial complex であるが, perfect matching を最大次元の単体とすると, perfect matching complex と呼ばれる simplicial complex が得られる。

• perfect matching complex

Bayer と Milutinović と Vega の [BMV] で honeycomb graph の場合が, Chandrakar と Singh の [CS] で polygonal line tiling の場合が調べられている。

References

[BMV]

Margaret Bayer, Marija Jelić Milutinović, and Julianne Vega. Perfect Matching Complexes of Honeycomb Graphs. arXiv: 2209.02803.

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

[CS]

Himanshu Chandrakar and Anurag Singh. Perfect Matching Complexes of Polygonal Line Tiling. arXiv: 2407.05809.

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