Calculation of Pfaffians by a Chip Removal
- Authors: Aksenov V.E.1, Kokhas K.P.1,2
-
Affiliations:
- ITMO University
- St.Petersburg State University
- Issue: Vol 215, No 6 (2016)
- Pages: 631-648
- Section: Article
- URL: https://journals.rcsi.science/1072-3374/article/view/237691
- DOI: https://doi.org/10.1007/s10958-016-2870-6
- ID: 237691
Cite item
Abstract
We describe a new combinatorial-algebraic transformation on graphs which we call “chip removal.” It generalizes the well-known Urban Renewal trick of Propp and Kuperberg. The chip removal is useful in calculations of determinants of adjacency matrices and matching numbers of graphs. A beautiful example of this technique is a theorem on removing four-contact chips, which generalizes Kuo’s graphical condensation method. Numerous examples are given. Bibliography: 10 titles.
Keywords
About the authors
V. E. Aksenov
ITMO University
Email: kpk@arbital.ru
Russian Federation, St. Petersburg
K. P. Kokhas
ITMO University; St.Petersburg State University
Author for correspondence.
Email: kpk@arbital.ru
Russian Federation, St. Petersburg; St. Petersburg