Séminaire Lotharingien de Combinatoire, 84B.96 (2020), 12 pp.
Grant T. Barkley and Ricky Ini Liu
Billiards, Channels, and Perfect Matching 2-Divisibility
Abstract.
Let mG denote the number of perfect matchings of the graph $G. We introduce a number of combinatorial tools for determining the parity of mG and giving a lower bound on the power of 2 dividing mG. 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ász states that the existence of a nontrivial channel is equivalent to mG being even. We strengthen this result by showing that the number of channels gives a lower bound on the power of 2 dividing mG 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 mG and dynamical systems by showing an equivalency between channels and billiard paths. We exploit this relationship to show that 2(gcd(m+1,n+1)-1)/2 divides the number of domino tilings of the m x n rectangle.
Received: November 20, 2019.
Accepted: February 20, 2020.
Final version: April 30, 2020.
The following versions are available: