RUS  ENG
Full version
JOURNALS // Zapiski Nauchnykh Seminarov POMI // Archive

Zap. Nauchn. Sem. POMI, 2015 Volume 436, Pages 5–33 (Mi znsl6157)

Calculation of Pfaffians by a chip removal

V. E. Aksenova, K. P. Kokhasbc

a St. Petersburg National Research University of Information Technologies, Mechanics and Optics, St. Petersburg, Russia
b St. Petersburg National Research University of Information Technologies, Mechanics and Optics, St. Petersburg, Russia
c St. Petersburg State University, St. Petersburg, Russia

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.

UDC: 519.148+519.177.3

Received: 12.09.2015


 English version:
Journal of Mathematical Sciences (New York), 2016, 215:6, 631–648

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024