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

Zap. Nauchn. Sem. POMI, 2014 Volume 421, Pages 5–18 (Mi znsl5745)

This article is cited in 1 paper

Domino tilings and determinants

V. Aksenova, K. Kokhasb

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

Abstract: Consider an arbitrary simply connected squared figure $F$ on the plane and its dual graph (vertices correspond to cells, edges correspond to cells sharing a common side). We investigate the relationship between the determinant of the adjacency matrix of the graph and the domino tilings of the figure $F$. We prove that in the case where all the tilings can be splitted into pairs such that the numbers of vertical dominos in each pair differ by 1, then $\operatorname{det}A_F=0$. And in the case where all the tilings except one can be splitted into such pairs, $\operatorname{det}A_F=(-1)^s$, where $s$ is half the area of the figure $F$.

Key words and phrases: domino tilings, pfaffian, combinatorial linear algebra.

UDC: 519.148

Received: 09.12.2013


 English version:
Journal of Mathematical Sciences (New York), 2014, 200:6, 647–653

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024