Billiards, channels, and perfect matching 2-divisibility

MaRDI QIDQ2199904zbMATH OpenFDO

Authors Grant T. Barkley, Ricky Ini Liu

Publication date 14 September 2020

Published in Séminaire Lotharingien de Combinatoire (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1911.08102, http://www.mat.univie.ac.at/~slc/wpapers/FPSAC2020//96.html

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

domino tilingsperfect matchingsdivisibilitybilliard paths

Mathematics Subject Classification ID

Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: Let $m_G$ denote the number of perfect matchings of the graph $G$. We introduce a number of combinatorial tools for determining the parity of $m_G$ and giving a lower bound on the power of 2 dividing $m_G$. In particular, we introduce certain vertex sets called channels, which correspond to elements in the kernel of the adjacency matrix of $G$ modulo $2$. A result of Lov'asz states that the existence of a nontrivial channel is equivalent to $m_G$ being even. We give a new combinatorial proof of this result and strengthen it by showing that the number of channels gives a lower bound on the power of $2$ dividing $m_G$ when $G$ is planar. We describe a number of local graph operations which preserve the number of channels. We also establish a surprising connection between 2-divisibility of $m_G$ and dynamical systems by showing an equivalency between channels and billiard paths. We exploit this relationship to show that $2^{fracgcd(m+1,n+1)-12}$ divides the number of domino tilings of the $mimesn$ rectangle. We also use billiard paths to give a fast algorithm for counting channels (and hence determining the parity of the number of domino tilings) in simply connected regions of the square grid.

Recommendations

• Channels, billiards, and perfect matching 2-divisibility
• Perfect matchings of cellular graphs
• Perfect matchings and perfect squares
• A note on the number of perfect matchings of bipartite graphs
• Generalizing the divisibility property of rectangle domino tilings

Cites work

• scientific article; zbMATH DE number 487720 (Why is no real title available?)
• scientific article; zbMATH DE number 1405497 (Why is no real title available?)
• Combinatorial approaches and conjectures for 2-divisibility problems concerning domino tilings of polyominoes
• Enumeration of perfect matchings in graphs with reflective symmetry
• The statistics of dimers on a lattice. I: The number of dimer arrangements on a quadratic lattice

Cited in

(1)

• Channels, billiards, and perfect matching 2-divisibility

This page was built for publication: Billiards, channels, and perfect matching 2-divisibility

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