Generalizing the divisibility property of rectangle domino tilings

zbMATH Open1339.05326arXiv1406.0669MaRDI QIDQ726665FDOQ726665

Authors: Forest Tong 

Publication date: 13 July 2016

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

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.

Full work available at URL: https://arxiv.org/abs/1406.0669

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

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

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)

Cites Work

• The statistics of dimers on a lattice. I: The number of dimer arrangements on a quadratic lattice
• Title not available (Why is that?)
• Enumeration of perfect matchings in graphs with reflective symmetry
• Applications of graphical condensation for enumerating matchings and tilings
• Lectures on Dimers
• Title not available (Why is that?)
• Graphical condensation for enumerating perfect matchings
• A reciprocity theorem for domino tilings

Cited In (5)

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

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)