Matchings on Graphs

グラフ上の matching は, トポロジーとの関係では, まず 離散モース理論で登場する。 Regular CW complex 上の離散 Morse 関数を考えることとその face poset の Hasse diagram の上の acyclic partial matching を考えることが, 本質的に同じだからである。

• partial matching
• acyclic partial matching
• perfect matching

他にも graph を扱うときは, その上でのmatching を考えることは基本的である。 Matching については, Lovász と Plummer の本 [LP09] がある。

Turaev [Tur] は, perfect matching のことを dimer covering と呼んでいる。 1960年代以降 統計物理学で, Kasteleyn [Kas63] や Temperley と Fisher [TF61] により研究が始められ, そこで使われている用語のようである。

Cohen, Dasbach, Russel [CDR14] は, dimer covering については Kuperberg の論文 [Kup94; Kup98; Kup02] を参照している。

References

[CDR14]

Moshe Cohen, Oliver T. Dasbach, and Heather M. Russell. “A twisted dimer model for knots”. In: Fund. Math. 225.1 (2014), pp. 57–74. arXiv: 1010.5228. url: https://doi.org/10.4064/fm225-1-4.

[Kas63]

P. W. Kasteleyn. “Dimer statistics and phase transitions”. In: J. Mathematical Phys. 4 (1963), pp. 287–293.

[Kup02]

Greg Kuperberg. “Kasteleyn cokernels”. In: Electron. J. Combin. 9.1 (2002), Research Paper 29, 30. arXiv: math/0108150. url: http://www.combinatorics.org/Volume_9/Abstracts/v9i1r29.html.

[Kup94]

Greg Kuperberg. “Symmetries of plane partitions and the permanent-determinant method”. In: J. Combin. Theory Ser. A 68.1 (1994), pp. 115–151. arXiv: math/9410224. url: http://dx.doi.org/10.1016/0097-3165(94)90094-9.

[Kup98]

Greg Kuperberg. “An exploration of the permanent-determinant method”. In: Electron. J. Combin. 5 (1998), Research Paper 46, 34 pp. (electronic). arXiv: math/9810091. url: http://www.combinatorics.org/Volume_5/Abstracts/v5i1r46.html.

[LP09]

László Lovász and Michael D. Plummer. Matching theory. Corrected reprint of the 1986 original [MR0859549]. AMS Chelsea Publishing, Providence, RI, 2009, pp. xxxiv+554. isbn: 978-0-8218-4759-6.

[TF61]

H. N. V. Temperley and Michael E. Fisher. “Dimer problem in statistical mechanics—an exact result”. In: Philos. Mag. (8) 6 (1961), pp. 1061–1063.

[Tur]

Vladimir Turaev. Dimer spaces and gliding systems. arXiv: 1211.3975.