Abstract:
We define an operation of chip removal that generalizes the Urban Renewal trick of Kuperberg and Propp. This operation replaces a subgraph $H$ of a graph $G$ with a small collection of weighted edges so that the equalty $\mathrm{Pf}(G)=\mathrm{Pf}(H)\mathrm{Pf}(G')$ holds (here $G'$ is the graph obtained after the replacement). We explain how to calculate the weights of the new edges in terms of the Pfaffians of the chip. We give several applications of this construction. One of these applications is to “Arnold's snakes”, which are graphs with the number of perfect matchings equal to Euler–Bernoulli numbers.
Key words and phrases:Pfaffian, matching number, graphical condensation.