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

Zap. Nauchn. Sem. POMI, 2015 Volume 432, Pages 5–29 (Mi znsl6107)

This article is cited in 2 papers

Chip removal. Urban Renewal revisited

V. E. Aksenov, K. P. Kokhas

St. Petersburg National Research University of Information Technologies, Mechanics and Optics, St. Petersburg, Russia

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.

Key words and phrases: determinant of adjacency matrix, matching number, “Urban Renewal”, pfaffian, combinatorial linear algebra.

UDC: 519.148

Received: 05.11.2014


 English version:
Journal of Mathematical Sciences (New York), 2015, 209:6, 809–825

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024