Channels, billiards, and perfect matching 2-divisibility (Q2034082)

In this paper, the authors study channels, billiards, and perfect matching of a graph modulo 2. They introduce a number of combinatorial tools for determining the parity of perfect matchings and for giving a lower bound to the power of 2 dividing perfect matching numbers. Moreover, they study the channels which correspond to elements in the kernel of the adjacency matrix of a graph modulo 2, they give a new combinatorial proof of this result and strengthen it by showing that the number of channels gives a lower bound to the power of 2 dividing the perfect matching number when \(G\) is a planar graph, and describe a number of local graph operations which preserve the number of channels. Finally, they establish a surprising connection between 2-divisibility of the perfect matching number and dynamical systems by showing an equivalency between channels and billiard paths, and use billiard paths to give a fast algorithm for counting channels in simply connected regions of the square grid.