Generalizing the divisibility property of rectangle domino tilings

MaRDI QIDQ726665zbMATH OpenFDO

Authors Forest Tong

Publication date 13 July 2016

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1406.0669, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i3p5

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

Ciucu's factorization theoremKasteleyn theoremPropp's enumeration of matchings

Mathematics Subject Classification ID

Combinatorial aspects of tessellation and tiling problems (05B45) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph operations (line graphs, products, etc.) (05C76)

Abstract: We introduce a class of graphs called compound graphs, generalizing rectangles, which are constructed out of copies of a planar bipartite base graph. The main result is that the number of perfect matchings of every compound graph is divisible by the number of matchings of its base graph. Our approach is to use Kasteleyn's theorem to prove a key lemma, from which the divisibility theorem follows combinatorially. This theorem is then applied to provide a proof of Problem 21 of Propp's Enumeration of Matchings, a divisibility property of rectangles. Finally, we present a new proof, in the same spirit, of Ciucu's factorization theorem.

Recommendations

• Counting domino tilings of rectangles via resultants
• The complexity of generalized domino tilings
• A reciprocity theorem for domino tilings
• Domino tilings and determinants
• Tromino tilings of domino-deficient rectangles
• Combinatorial approaches and conjectures for 2-divisibility problems concerning domino tilings of polyominoes
• Tiling of rectangles with squares and related problems via Diophantine approximation
• A note on tiling with integer-sided rectangles
• Tilings of rectangles with T-tetrominoes
• scientific article; zbMATH DE number 1741011

Cites work

• A reciprocity theorem for domino tilings
• Applications of graphical condensation for enumerating matchings and tilings
• Enumeration of perfect matchings in graphs with reflective symmetry
• Graphical condensation for enumerating perfect matchings
• scientific article; zbMATH DE number 1405497 (Why is no real title available?)
• scientific article; zbMATH DE number 3326387 (Why is no real title available?)
• Lectures on Dimers
• The statistics of dimers on a lattice. I: The number of dimer arrangements on a quadratic lattice

Cited in

(5)

• A note on divisibility of the number of matchings of a family of graphs
• Combinatorial approaches and conjectures for 2-divisibility problems concerning domino tilings of polyominoes
• Channels, billiards, and perfect matching 2-divisibility
• Billiards, channels, and perfect matching 2-divisibility
• The complexity of generalized domino tilings

This page was built for publication: Generalizing the divisibility property of rectangle domino tilings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q726665)