\documentclass[finalversion]{FPSAC2020}
\articlenumber{96}
%% note that the class file already loads {amsmath, amsthm, amssymb}


\usepackage{enumitem}
\usepackage{caption}
\usepackage{subcaption}
\usepackage{float}
\usepackage{tikz}
\usepackage{etoolbox, calc}
\usetikzlibrary{patterns}
\usetikzlibrary{arrows}
\usetikzlibrary{calc}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}[section]
%\newtheorem{corollary}{Corollary}[theorem]
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{conjecture}[theorem]{Conjecture}

\newenvironment{claim}[1]{\par\noindent\textbf{Claim:}\space#1}{}
\newenvironment{claimproof}[1]{\par\noindent\emph{Proof of claim:}\space#1}{\leavevmode\unskip\penalty9999 \hbox{}\nobreak\hfill\quad\hbox{$\blacksquare$}}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{problem}[theorem]{Problem}

%\newenvironment{example}[1][]{\refstepcounter{theorem}\par\medskip
%   \noindent \textbf{Example~\thetheorem. #1} \rmfamily}{\leavevmode\unskip\penalty9999 \hbox{}\nobreak\hfill\quad\hbox{$\Diamond$}\medskip}
\newtheorem{application}[theorem]{Application}

\theoremstyle{remark}

\newtheorem{remark}[theorem]{Remark}

\numberwithin{equation}{section}

\newcommand{\R}{\mathbf{R}}
\newcommand{\N}{\mathbf{N}}
\newcommand{\Z}{\mathbf{Z}}

\newcommand{\m}{m_G}
\newcommand{\cb}{\mathcal{C}_B}
\newcommand{\cw}{\mathcal{C}_W}
\newcommand{\mc}{\mathcal{C}}
\newcommand{\mat}{\mathcal{M}}
\newcommand{\bp}{\mathcal{B}}

\newcommand{\ceil}[1]{\left\lceil#1\right\rceil}
\DeclareMathOperator{\nul}{null}
\DeclareMathOperator{\coker}{coker}
\DeclareMathOperator{\im}{im}
\DeclareMathOperator{\ch}{ch}
\DeclareMathOperator{\chdeg}{chdeg}
\DeclareMathOperator{\lcm}{lcm}
\DeclareMathOperator{\per}{per}

\newcounter{colsum}

\newcommand\vertices[4]{%
	\foreach \x in {#1,...,#3}
	\foreach \y in {#2,...,#4}
	{
		\setcounter{colsum}{\x+\y};
		
		\ifnumodd{\value{colsum}}{\def\altcol{white}}{\def\altcol{black}}
		\draw[fill=\altcol] (\x,\y) circle (.1);
	}
}

\title{Billiards, Channels, and Perfect Matching 2-Divisibility}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author{Grant T. Barkley\thanks{\href{mailto:gbarkle@ncsu.edu}{gbarkle@ncsu.edu}. Supported by a grant from the North Carolina State University Office of Undergraduate Research.}\addressmark{1} \and Ricky Ini Liu\thanks{\href{mailto:riliu@ncsu.edu}{riliu@ncsu.edu}. Partially supported by NSF grant DMS--1700302.}\addressmark{1}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Department of Mathematics, North Carolina State University, Raleigh, NC, USA }

%% put the date of submission here
\received{\today}

%% leave this blank until submitting a revised version
%\revised{}

%% put your English abstract here, or comment this out if you don't have one yet
%% please don't use custom commands in your abstract / resume, as these will be displayed online
%% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year)
\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 strengthen this result 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^{(\gcd(m+1,n+1)-1)/2}$ divides the number of domino tilings of the $m\times n$ rectangle.
}

%% put your French abstract here, or comment this out if you don't have one
%\resume{\lipsum[2]}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{perfect matchings, domino tilings, divisibility, billiard paths}

%% you can include your bibliography however you want, but using an external .bib file is STRONGLY RECOMMENDED and will make the editor's life much easier
%% regardless of how you do it, please use numerical citations, ie. [xx, yy] in the text

%% this sample uses biblatex, which (among other things) takes care of URLs in a more flexible way than bibtex
%% but you can use bibtex if you want
\addbibresource{fpsac.bib}
%% note the \printbibliography command at the end of the file which goes with these biblatex commands

\begin{document}

\maketitle
%% note that you DO NOT have to put your abstract here -- it is generated by \maketitle and the \abstract and \resume commands above

\section{Introduction}

Given a graph $G$, a \emph{perfect matching} of $G$ is a subset of edges $\mu$ such that each vertex of $G$ is contained in a unique edge in $\mu$. We let $\m$ denote the number of distinct perfect matchings of $G$. The problem of determining $\m$ arises in various mathematical contexts, particularly in tiling problems.
Exact formulas for $\m$ over an infinite family of graphs are quite rare. One notable exact formula is for $G=\mathcal R_{m\times n}$, the rectangular subgraph of the square lattice with $m$ rows of $n$ vertices. In this case, the famous result of Kasteleyn \cite{Kasteleyn1961} gives 
\[\m^4 = \prod_{j=1}^{n}\prod_{k=1}^{m} \left(4\cos^2\frac{j\pi }{n+1} + 4\cos^2\frac{k\pi}{m+1}\right). \]

From this product we may extract certain number theoretic information. In particular, $\m$ is always divisible by $2^{(\gcd(n+1,m+1)-1)/2}$ \cite{Pachter1997}. Studying similar 2-divisibility patterns is a common theme in the literature on domino tilings, which are equivalent to perfect matchings of subgraphs of the square lattice. It is often the case that the 2-component of the prime factorization of $\m$ follows a predictable pattern, even when an exact formula for $\m$ is elusive or unwieldy. In Propp's perfect matching problem anthology \cite{Propp1999}, he gives a number of conjectured and known power of 2 patterns for various graphs. 
Most results along these lines rely on a theorem of Ciucu \cite{Ciucu1996} that requires the graph have reflective symmetry, which excludes most graphs from consideration.
\iffalse
For example, the following is a refinement by Pachter \cite{Pachter1997} of one of these conjectures.

\begin{conjecture}[Deleting from step-diagonals] \label{step-diag-conj}
	Let $G$ be $\mathcal R_{2r\times 2r}$, the $2r\times 2r$ grid graph shown in \cref{fig:first}. If any $k$ of the highlighted edges are removed, then 
	$$\m = 2^{r-k}b$$
	for some odd integer $b$.
\end{conjecture}

\begin{figure}[htb]                                       
	\centering
	\begin{tikzpicture}[scale=.5]
	\draw (0,0) grid (7,7);
	\pgfmathsetmacro{\radius}{0.1}
	\foreach \x in {0, 1, 2, 3} {
		\draw[ultra thick, red] (\x,\x) -- ++(1,0);
	}
	
	\foreach \x in {0, 1,..., 7} {
		\foreach \y in {0, 1,..., 7} {
			\draw[fill=black] (\x,\y) circle (\radius);
		}
	}
	\end{tikzpicture}
	\caption{The step-diagonal for $r=4$.}
	\label{fig:first}
\end{figure}

The following theorem of Ciucu is perhaps the most widely used 2-divisibility result in the literature.
\begin{proposition} [Ciucu's Factorization Theorem \cite{Ciucu1996}]
	\label{ciucu}
	If a bipartite graph has a line of symmetry containing $2r$ vertices, and no edges lie on the line or connect two vertices on opposite sides of the line, then the number of perfect matchings of the graph is divisible by $2^r$.
\end{proposition}
\fi
The results we introduce here require only planarity and sometimes a degree condition, thus providing a uniform (partial) explanation of power of 2 patterns in terms of the geometry of the graph. Our foundational construction is based on the following result known to Lov\'asz. 

\begin{proposition}[{\cite[Problem 5.18]{Lovasz1993}}]\label{even}
	Let $G$ be any graph. Then $\m$ is even if and only if there is a nonempty vertex set $C\subseteq V$ such that every vertex in $G$ is adjacent to an even number of vertices in $C$.
\end{proposition}

Vertex sets $C$ satisfying the hypothesis of \cref{even} are called \emph{channels}. (We also count the empty set as a trivial channel.) Lov\'asz's result already shows the importance of channels for determining the parity of $\m$. The main theorem of this extended abstract shows that channels have even more to say for planar graphs.

\begin{theorem}[Channeling twos]\label{2ch}
    Let $G$ be a planar graph. Then the number of distinct channels in $G$ divides $\m^2$.
\end{theorem}

Since the number of channels will always be a power of 2, \cref{2ch} gives a lower bound on the power of 2 dividing $\m$ for any planar graph. We show the strength of this theorem in a number of examples throughout the abstract. In particular, we will show that $2^{(\gcd(n+1,m+1)-1)/2}$ divides $m_{\mathcal R_{m\times n}}$.

Many of our results are tailored for subgraphs of the square lattice, where perfect matchings are equivalent to domino tilings of a region. When possible, however, we will state results in greater generality. Our most fascinating result is a characterization of channels in terms of dynamical systems. We state the result here for subgraphs of the square lattice, and describe the general case in \cref{secbounce}.

Let $G$ be a full subgraph of the square lattice such that each internal (bounded) face of $G$ is a unit square. In the dual language of domino tilings, such graphs correspond to simply connected regions of the plane. Since $G$ is bipartite, we 2-color the vertices of $G$ black and white. An example of such a graph is shown in \cref{unitsqgraph}.


Now we define a \emph{billiard path} on $G$ to be any collection of paths traced out by billiard balls placed on black vertices of $G$ and launched at 45 degree angles. When a billiard ball reaches a wall, it reflects at a 90 degree angle and proceeds in its new direction, continuing until it is caught by a corner or returns to its start position. (If the billiard brushes past a corner or hits one head-on, the situation is more complicated---the path splits into two paths continuing in different directions. See \cref{secbounce} for a more precise definition.) 


% Path
\begin{figure}
    \centering
    \begin{tikzpicture}[scale=.5]
        \draw (0,0) grid (3,4);
        \draw (3,1) grid (4,4);
        \draw[blue, thick] (3,0) -- (0,3) -- (1,4) -- (4,1);
        \begin{scope}[shift={(-1,0)}]
        \vertices{1}{0}{4}{4};
        \vertices{5}{1}{5}{4};
        \end{scope}
        
        \begin{scope}[shift={(8,0)}]
        \draw (0,0) grid (3,4);
        \draw (3,1) grid (4,4);
        \draw[green, thick] (1,0) -- (0,1) -- (3,4) -- (4,3) -- (1,0);
        \begin{scope}[shift={(-1,0)}]
        \vertices{1}{0}{4}{4};
        \vertices{5}{1}{5}{4};
        \end{scope}
        \end{scope}
        
        \begin{scope}[shift={(16,0)}]
        \draw (0,0) grid (3,4);
        \draw (3,1) grid (4,4);
        \draw[blue, thick] (3,0) -- (0,3) -- (1,4) -- (4,1);
        \draw[green, thick] (1,0) -- (0,1) -- (3,4) -- (4,3) -- (1,0);
        \begin{scope}[shift={(-1,0)}]
        \vertices{1}{0}{4}{4};
        \vertices{5}{1}{5}{4};
        \end{scope}
        \end{scope}
    \end{tikzpicture}
    \caption{The three nonempty billiard paths in a full subgraph $G$ of the square lattice that is composed of unit squares.}
    \label{unitsqgraph}
\end{figure}

Remarkably, channels and billiard paths are intrinsically connected. Let $G'$ be the \emph{inner subgraph} of $G$, the subgraph formed by removing all vertices of $G$ which are incident to the unbounded face and all edges incident to those vertices. 

\begin{theorem}\label{billintro}
Let $G$ satisfy the assumptions described above, and let $G'$ be the inner subgraph of $G$. Further assume that the dual graph of $G$ is $2$-connected. Then the number of billiard paths in $G$ is twice the number of channels which use only the black vertices of $G'$. 
\end{theorem}

In particular, a bipartite version of channeling twos implies that the number of billiard paths for $G$ divides $2m_{G'}$. For the graph $G$ in \cref{unitsqgraph}, the inner subgraph $G'$ is shown in \cref{innerunsq}. Since $G$ has 4 billiard paths and satisfies the hypothesis of \cref{billintro}, it follows that $m_{G'}$ is divisible by 2. Indeed, there are 4 perfect matchings of $G'$.

\begin{figure}[H]
    \centering
    \begin{tikzpicture}[scale=.5]
        \begin{scope}[opacity=.1]
        \draw (0,0) grid (3,4);
        \draw (3,1) grid (4,4);
        \begin{scope}[shift={(-1,0)}]
        \vertices{1}{0}{4}{4};
        \vertices{5}{1}{5}{4};
        \end{scope}
        \end{scope}
        
        \draw (1,1) grid (2,3);
        \draw (3,2) grid (2,3);
        \begin{scope}[shift={(-1,0)}]
        \vertices{2}{1}{3}{3};
        \vertices{3}{2}{4}{3};
        \end{scope}
    \end{tikzpicture}
    \caption{The inner subgraph $G'$ of the graph $G$ defined in \cref{unitsqgraph}.}
    \label{innerunsq}
\end{figure}

The connection between 2-divisibility, channels, and dynamical systems explains both the sensitivity and the regularity of perfect matching 2-divisibility. Small changes to $G$ can result in entirely different billiard dynamics, with the effects visible in $m_{G'}$. 
\iffalse
For instance, if we take $G$ to be the graph in \cref{graphno2}, then there is only one nonempty billiard path.

\begin{figure}[H]
    \centering
    \begin{tikzpicture}[scale=.5, rotate=-90]
        \draw (0,0) grid (3,4);
        \draw[blue, thick] (3,0) -- (0,3) -- (1,4) -- (3,2) -- (1,0) -- (0,1) -- (3,4);
        \begin{scope}[shift={(-1,0)}]
        \vertices{1}{0}{4}{4};
        \end{scope}
        
        \begin{scope}[shift={(0,6)}]
        \begin{scope}[opacity=.1]
        \draw (0,0) grid (3,4);
        \begin{scope}[shift={(-1,0)}]
        \vertices{1}{0}{4}{4};
        \end{scope}
        \end{scope}
        \draw (1,1) grid (2,3);
        \begin{scope}[shift={(-1,0)}]
        \vertices{2}{1}{3}{3};
        \end{scope}
        \end{scope}
    \end{tikzpicture}
    \caption{A graph $G$ which has only one nonempty billiard path, along with its inner subgraph $G'$.}
    \label{graphno2}
\end{figure}

Since $G$ has 2 billiard paths, by \cref{billintro} the inner subgraph $G'$ has no nonempty channels on black vertices. Since $G'$ has the same number of black and white vertices, this will imply (by \cref{sqbipart}) that $G'$ has no nonempty channels at all. Thus by \cref{even}, $G'$ has an odd number of perfect matchings --- in this case $3$. 
\fi
The dynamics can also induce a regularity in the 2-divisibility of $\m$. The well-known theory of arithmetic billiards describes billiard paths for rectangles in terms of divisibility properties of the rectangle side lengths. In \cref{arithmetic}, we exploit these results to explain the factor of $2^{(\gcd(m+1,n+1)-1)/2}$ dividing $\m$ for the $m\times n$ grid graph.

Billiard paths give a global explanation of channel structure for many graphs. Sometimes we are instead interested in local behavior. For instance, we may have a family of graphs which are globally similar, but differ locally. To relate these graphs, we introduce in \cref{secmoves} a set of channel-preserving graph operations and show that they may be applied repeatedly to reduce many graphs to a set of independent vertices.

The paper is organized as follows. \cref{secchannel} gives definitions and context for \cref{2ch}. In \cref{secmoves}, we discuss certain graph moves that always preserve the number of channels in a graph. \cref{secdiag} introduces a useful graph move called \emph{diagonal contraction}. We describe an application of diagonal contraction and channels to the Aztec diamond family of graphs. \cref{secbounce} describes billiard paths for a large class of graphs called \emph{inner semi-Eulerian graphs}. The results described in the introduction are applied to the rectangle grid graph, connecting its 2-divisibility to the theory of arithmetic billiards. In the full version \cite{Barkley2019} of this extended abstract, we also give a combinatorial proof of \cref{even}, a fast algorithm using billiard paths for determining the 2-divisibility of certain graphs, and a number of additional examples and theorems. 


\section{Channels}\label{secchannel}
All graphs in this paper are undirected, finite, and contain no self-loops. If a graph is bipartite, we will consider its vertices to be colored black and white. Additionally, all matchings discussed will be perfect matchings, and thus the word ``perfect'' will be omitted in the future for brevity. For a graph $G=(V,E)$, $V$ denotes the vertex set, $E$ denotes the edge set, and $A$ denotes the adjacency matrix. 

Sometimes we will be interested in planar graphs $G$. Such graphs admit a dual graph, with vertices given by the faces of $G$ and edges between faces separated by an edge in $G$. If the same face is on both sides of an edge of $G$, then that edge corresponds to a self-loop in the dual graph. The \emph{external face} of $G$ is the face which is unbounded, and all other faces are \emph{internal faces} of $G$. The \emph{reduced dual graph} of $G$ is the dual graph of $G$ with the vertex corresponding to the external face of $G$ removed. We say a vertex of $G$ is \emph{external} if it is incident to the external face, and we say it is \emph{internal} otherwise.

Let $G$ be a graph with adjacency matrix $A$. The 2-kernel $\ker_2 A$ is the kernel of $A$ considered as a matrix over $\Z/2\Z$. Then a vector $x$ in $\ker_2 A$ has entries in $\Z/2\Z$ and can be lifted to a vector $\tilde x$ with entries $0,1\in \Z$. The condition $Ax = 0$ then becomes $A\tilde x = 2y$ for some integral vector $y$. Because each row of $x$ corresponds to a vertex in $G$, we may interpret $x$ as the indicator function for a vertex set $C$, where a row with a $1$ indicates the vertex is in $C$ and a row with a $0$ indicates the vertex is not in $C$. This leads to the following interpretation of 2-kernel elements.

\begin{definition}
	Let $G = (V, E)$ be any graph. A \emph{channel} is a set $C$ of vertices such that every vertex in $G$ is adjacent to an even number of vertices in $C$. In other words, a channel satisfies
	$$|\{(v,v') \in E \mid v'\in C \}| \text{ is even for all $v\in V$}.$$
	Let the set of channels in $G$ be denoted $\mathcal{C}(G)$. If $G$ is bipartite, let $\cb(G)$ (resp. $\cw(G)$) be the subspace of $\mc(G)$ consisting of channels that use only black (resp. white) vertices.
\end{definition}

The 2-kernel also has an additive structure as a $\Z/2\Z$ vector space. This transfers to $\mc(G)$ by defining the sum of $C_1,C_2\in\mc(G)$ to be the symmetric difference of $C_1$ and $C_2$.
%$$C_1 \oplus C_2 := (C_1\cup C_2)-(C_1\cap C_2)\text{, the symmetric difference of $C_1$ and $C_2$} .$$

\begin{figure}[htb]
    \centering
    \begin{tikzpicture}[scale=.5]
        \pgfmathsetmacro{\radius}{0.1}
        \node (a) at (0,0){};
        \node (b) at (0.5,1){};
        \node (c) at (2,1){};
        \node (d) at (3,-0.5){};
        \node (e) at (2,-1.5){};
        \node (f) at (1,-1){};
        \draw (a.center) -- (c.center) -- (d.center) -- (a.center);
        \draw (a.center) -- (b.center);
        \draw (b.center) -- (c.center);
        \draw (b.center) -- (f.center);
        \draw (e.center) -- (f.center);
        \draw (f.center) -- (d.center);
        \draw[fill,orange] (a) circle (2*\radius);
        \draw[fill=black] (a) circle (\radius);
        \draw[fill=black] (b) circle (\radius);
        \draw[fill,orange] (c) circle (2*\radius);
        \draw[fill,orange] (d) circle (2*\radius);
        \draw[fill,orange] (e) circle (2*\radius);
        \draw[fill=black] (c) circle (\radius);
        \draw[fill=black] (d) circle (\radius);
        \draw[fill=black] (e) circle (\radius);
        \draw[fill=black] (f) circle (\radius);
    \end{tikzpicture} \hspace{3em}
    \begin{tikzpicture}[scale=.5]
        \pgfmathsetmacro{\radius}{0.1}
        \node (a) at (0,0){};
        \node (b) at (0.5,1){};
        \node (c) at (2,1){};
        \node (d) at (3,-0.5){};
        \node (e) at (2,-1.5){};
        \node (f) at (1,-1){};
        \draw (a.center) -- (c.center) -- (d.center) -- (a.center);
        \draw (a.center) -- (b.center);
        \draw (b.center) -- (c.center);
        \draw (b.center) -- (f.center);
        \draw (e.center) -- (f.center);
        \draw (f.center) -- (d.center);
        \draw[fill,orange] (b) circle (2*\radius);
        \draw[fill,orange] (d) circle (2*\radius);
        \draw[fill=black] (a) circle (\radius);
        \draw[fill=black] (b) circle (\radius);
        \draw[fill=black] (c) circle (\radius);
        \draw[fill=black] (d) circle (\radius);
        \draw[fill=black] (e) circle (\radius);
        \draw[fill=black] (f) circle (\radius);
    \end{tikzpicture} \hspace{3em}
    \begin{tikzpicture}[scale=.5]
        \pgfmathsetmacro{\radius}{0.1}
        \node (a) at (0,0){};
        \node (b) at (0.5,1){};
        \node (c) at (2,1){};
        \node (d) at (3,-0.5){};
        \node (e) at (2,-1.5){};
        \node (f) at (1,-1){};
        \draw (a.center) -- (c.center) -- (d.center) -- (a.center);
        \draw (a.center) -- (b.center);
        \draw (b.center) -- (c.center);
        \draw (b.center) -- (f.center);
        \draw (e.center) -- (f.center);
        \draw (f.center) -- (d.center);
        \draw[fill,orange] (a) circle (2*\radius);
        \draw[fill,orange] (b) circle (2*\radius);
        \draw[fill,orange] (c) circle (2*\radius);
        \draw[fill,orange] (e) circle (2*\radius);
        \draw[fill=black] (a) circle (\radius);
        \draw[fill=black] (b) circle (\radius);
        \draw[fill=black] (c) circle (\radius);
        \draw[fill=black] (d) circle (\radius);
        \draw[fill=black] (e) circle (\radius);
        \draw[fill=black] (f) circle (\radius);
    \end{tikzpicture}
    \caption{A graph $G$ with its three nonempty channels indicated by shading. Any two of these form a basis for the space $\mc(G)$.}
    \label{fig:channelexample}
\end{figure}

For planar graphs $G$, there exists a matrix $K$ (called a \emph{Kasteleyn matrix} \cite{Kasteleyn1963} of $G$ ) obtained from $A$ by adding signs to some entries such that $\det K = m_G^2$. We note that $K$ and $A$ are equivalent modulo 2 and thus have the same 2-kernel. The next theorem follows by analyzing the Smith normal form of $K$ and identifying 2-kernels with channels (see \cite{Barkley2019} for more details).

\begin{theorem}[Channeling twos]\label{twos}
	If $\{C_1,...,C_n\}$ is a linearly independent set of channels in a graph $G$ with a Kasteleyn matrix (in particular, for planar $G$), then 
	$$2^n \text{ divides } m_G^2.$$
	If additionally $G$ is bipartite, and $\{C_1,...,C_n\}\subseteq \cb(G)$, then
	$$2^n \text{ divides } m_G.$$
\end{theorem}

\begin{remark}
	Despite the fact that \cref{even} holds for an arbitrary graph, \cref{twos} does not. For example, the complete bipartite graph $K_{3,3}$ has $|\cb(K_{3,3})| = 2^2$, but $m_{K_{3,3}}=6$ is not divisible by $2^2$. Thus the assumption of a Kasteleyn matrix for $G$ cannot be weakened much further.
\end{remark}


\subsection{Channel-preserving moves}\label{secmoves}
In this section, we describe a set of local graph moves which unconditionally preserve channels and (for two of the moves) perfect matchings of our graph. In many cases we can reduce the graph to a collection of vertices via these moves. We begin by introducing our operations of interest.

A \emph{2-valent vertex contraction} may be applied to any vertex $v$ of degree two that is adjacent to distinct vertices $v_1,v_2$. The resulting graph is formed by contracting the edges incident to $v$ and deleting self-loops if they occur.
\begin{figure}[H]
	\centering
	\begin{tikzpicture}
	\draw[white] (-1.5,0) (9,0);
	
	\pgfmathsetmacro{\radius}{0.1}
	\draw[red,fill] (1,0) circle (.1);
	\draw[red] (0,0) -- (1,0) -- (2,0);
	\node (a) at (1,0) {};
	\draw[green,thick,->] (0,0) to[out=60,in=120] (a);
	\draw[green,thick,->] (2,0) to[out=120,in=60] (a);
	\draw[fill = black] (0,0) circle (\radius) (2,0) circle (\radius);
	\node at (1,-.4) {$v$};
	\node at (0,-.4) {$v_1$};
	\node at (2,-.4) {$v_2$};
	\draw[dashed] (-1,-.5) -- (-.5,-.25);
	\draw (-.5,-.25) -- (0,0);
	\draw[dashed] (-1,0) -- (-.5,0);
	\draw (-.5,0) -- (0,0);
	\draw[dashed] (-1,.5) -- (-.5,.25);
	\draw (-.5,.25) -- (0,0);
	\draw[dashed] (3,-.5) -- (2.5,-.25);
	\draw (2.5,-.25) -- (2,0);
	\draw[dashed] (3,0) -- (2.5,0);
	\draw (2.5,0) -- (2,0);
	\draw[dashed] (3,.5) -- (2.5,.25);
	\draw (2.5,.25) -- (2,0);
	
	\draw (4,0) node[scale=2]{$\implies$};
	\draw (3.9,.4) node{VC};
	
	\begin{scope}[shift={(7,0)}]
	
	\pgfmathsetmacro{\radius}{0.1}
	\draw[fill = black] (0,0) circle (\radius);
	%\node at (0,-.4) {$v'$};
	\draw[dashed] (-1,-.5) -- (-.5,-.25);
	\draw (-.5,-.25) -- (0,0);
	\draw[dashed] (-1,0) -- (-.5,0);
	\draw (-.5,0) -- (0,0);
	\draw[dashed] (-1,.5) -- (-.5,.25);
	\draw (-.5,.25) -- (0,0);
	\draw[dashed] (1,-.5) -- (0.5,-.25);
	\draw (0.5,-.25) -- (0,0);
	\draw[dashed] (1,0) -- (0.5,0);
	\draw (0.5,0) -- (0,0);
	\draw[dashed] (1,.5) -- (0.5,.25);
	\draw (0.5,.25) -- (0,0);
	
	\end{scope}
	
	\end{tikzpicture}
\end{figure}

A \emph{doubled edge deletion} may be applied to any pair of edges $e_1,e_2$ that share the same endpoints. This operation removes $e_1$ and $e_2$ from the graph.
\begin{figure}[H]
	\centering
	\begin{tikzpicture}
	\draw[white] (-1.5,0) (9,0);
	\draw[red] (0,0)  to[out=30, in=150] (2,0);
	\draw[red] (0,0) to[out=-30, in=-150] (2,0);
	\node at (1,-.6) {$e_1$};
	\node at (1,.6) {$e_2$};
	\draw[fill=black] (0,0) circle (.1) (2,0) circle (.1);
	\draw[dashed] (-1,-.5) -- (-.5,-.25);
	\draw (-.5,-.25) -- (0,0);
	\draw[dashed] (-1,0) -- (-.5,0);
	\draw (-.5,0) -- (0,0);
	\draw[dashed] (-1,.5) -- (-.5,.25);
	\draw (-.5,.25) -- (0,0);
	\draw[dashed] (3,-.5) -- (2.5,-.25);
	\draw (2.5,-.25) -- (2,0);
	\draw[dashed] (3,0) -- (2.5,0);
	\draw (2.5,0) -- (2,0);
	\draw[dashed] (3,.5) -- (2.5,.25);
	\draw (2.5,.25) -- (2,0);
	
	\draw (4,0) node[scale=2]{$\implies$};
	\draw (3.9,.4) node{ED};
	
	\begin{scope}[shift={(6,0)}]
	
	\pgfmathsetmacro{\radius}{0.1}
	\draw[fill=black] (0,0) circle (.1) (2,0) circle (.1);
	\draw[dashed] (-1,-.5) -- (-.5,-.25);
	\draw (-.5,-.25) -- (0,0);
	\draw[dashed] (-1,0) -- (-.5,0);
	\draw (-.5,0) -- (0,0);
	\draw[dashed] (-1,.5) -- (-.5,.25);
	\draw (-.5,.25) -- (0,0);
	\draw[dashed] (3,-.5) -- (2.5,-.25);
	\draw (2.5,-.25) -- (2,0);
	\draw[dashed] (3,0) -- (2.5,0);
	\draw (2.5,0) -- (2,0);
	\draw[dashed] (3,.5) -- (2.5,.25);
	\draw (2.5,.25) -- (2,0);
	
	\end{scope}
	\end{tikzpicture}
\end{figure}

A \emph{forced vertex pair removal} may be applied to distinct adjacent vertices $v_1,v_2$ such that $v_1$ has degree one. The resulting graph is formed by removing $v_1,v_2$ and all edges incident to these vertices.
\begin{figure}[H]
	\centering
	\begin{tikzpicture}
	\draw[white] (-1.5,0) (9,0);
	\pgfmathsetmacro{\radius}{0.1}
	\draw (1,0) -- (2,0);
	\node at (1,-.4) {$v_1$};
	\node at (2,-.4) {$v_2$};
	\draw[dashed] (3,-.5) -- (2.5,-.25);
	\draw (2.5,-.25) -- (2,0);
	\draw[dashed] (3,0) -- (2.5,0);
	\draw (2.5,0) -- (2,0);
	\draw[dashed] (3,.5) -- (2.5,.25);
	\draw (2.5,.25) -- (2,0);
	\draw[fill, red] (1,0) circle (\radius) (2,0) circle (\radius);
	
	\draw (4,0) node[scale=2]{$\implies$};
	\draw (3.9,.4) node{FV};
	
	
	
	\end{tikzpicture}
\end{figure}

We call these three moves \emph{channel-preserving moves}. As the name suggests, applying a channel-preserving move to a graph preserves the number of channels in that graph. A graph is called \emph{reducible} if it can be reduced to a set of degree 0 vertices using only channel-preserving moves. 
\begin{theorem}
	Let $G$ be a reducible graph. Then the number of degree 0 vertices remaining after $G$ has been fully reduced is the dimension of $\mc(G)$. In particular, this number is independent of the choice of channel-preserving moves used to reduce the graph. 
\end{theorem}

\begin{example}
	The graph $G$ shown in \cref{fig:channelexample} is a reducible graph. \cref{reduce} shows a possible sequence of channel-preserving moves. Because $G$ reduces to two vertices of degree 0, $G$ must have $2^2$ channels. This is indeed the case; \cref{fig:channelexample} shows the three nonempty channels.
\end{example}
	\begin{figure}[H]
		\centering
		\begin{tikzpicture}[scale=.5, every node/.style={transform shape}]
		\pgfmathsetmacro{\radius}{0.1}
		\node (a) at (0,0){};
		\node (b) at (0.5,1){};
		\node (c) at (2,1){};
		\node (d) at (3,-0.5){};
		\node (e) at (2,-1.5){};
		\node (f) at (1,-1){};
		\draw (a.center) -- (c.center) -- (d.center) -- (a.center);
		\draw (a.center) -- (b.center);
		\draw (b.center) -- (c.center);
		\draw (b.center) -- (f.center);
		\draw (e.center) -- (f.center);
		\draw (f.center) -- (d.center);
		\draw[fill=black] (a) circle (\radius);
		\draw[fill=black] (b) circle (\radius);
		\draw[fill=black] (c) circle (\radius);
		\draw[fill=black] (d) circle (\radius);
		\draw[red,fill=red] (e) circle (\radius);
		\draw[red,fill=red] (f) circle (\radius);
		
		\draw (5,0) node[scale=2]{$\implies$};
		\draw (4.9,.4) node{FV};
		
		\begin{scope}[shift={(7,0)}]
		
		\node (a) at (0,0){};
		\node (b) at (0.5,1){};
		\node (c) at (2,1){};
		\node (d) at (3,-0.5){};
		\draw (a.center) -- (c.center) -- (d.center) -- (a.center);
		\draw[red] (a.center) -- (b.center);
		\draw[red] (b.center) -- (c.center);
		\draw[fill=black] (a) circle (\radius);
		\draw[red,fill=red] (b) circle (\radius);
		\draw[fill=black] (c) circle (\radius);
		\draw[fill=black] (d) circle (\radius);
		\end{scope}
		
		\draw (12,0) node[scale=2]{$\implies$};
		\draw (11.9,.4) node{VC};
		
		\begin{scope}[shift={(13,0)}]
		
		\node (b) at (0.5,1){};
		\node (d) at (3,-0.5){};
		\draw[red] (d.center) to[out=120, in=0] (b) to[out=-90, in=180] (d);
		\draw[fill=black] (0.6,1) circle (\radius);
		\draw[fill=black] (d) circle (\radius);
		\end{scope}
		
		\draw (18,0) node[scale=2]{$\implies$};
		\draw (17.9,.4) node{ED};
		\draw[fill=black] (20,1) circle (\radius);
		\draw[fill=black] (22.5,-.5) circle (\radius);
		\end{tikzpicture} 
		\caption{Reducing a graph to independent vertices.}\label{reduce}
	\end{figure}


One structural property that implies reducibility is the following. We call a planar graph called \emph{inner Eulerian} if all internal vertices have even degree. (In particular, this property holds for many subgraphs of the square lattice.)


\begin{theorem}
	Let $G$ be an inner Eulerian bipartite graph. Then $G$ is reducible.
\end{theorem}

\iffalse
\begin{example}
	Not all graphs are reducible. \cref{nonreduce} shows a planar bipartite graph which admits no channel-preserving moves. 
\end{example}
	
	\begin{figure}
		\centering
		\begin{tikzpicture}[scale=.5]
		\pgfmathsetmacro{\radius}{0.1}
		\draw[fill=black] (-2,-2) circle (\radius)--
						  (2,-2) circle (\radius)--
						  (2,2) circle (\radius)--
						  (-2,2) circle (\radius)--(-2,-2);
		\draw[fill=black] (-1,-1) circle (\radius)--
		(1,-1) circle (\radius)--
		(1,1) circle (\radius)--
		(-1,1) circle (\radius)--(-1,-1);
		\draw[fill=black] (1,-1)--(2,-2);
		\draw[fill=black] (1,1)--(2,2);
		\draw[fill=black] (-1,1)--(-2,2);
		\draw[fill=black] (-1,-1)--(-2,-2);
		\draw[fill=white] (-1,1) circle (.1) (1,-1) circle(.1)
		 (2,2) circle (.1) (-2,-2) circle (.1);
		\end{tikzpicture}
		\caption{A graph which is not reducible.}
		\label{nonreduce}
	\end{figure}
\fi

\subsection{Contracting diagonals}\label{secdiag}
When our region is a subgraph of the square lattice, there is a useful sequence of channel-preserving moves available called a \emph{diagonal contraction}. Pick a degree 2 vertex $v$ that is a corner of the graph. Then $v$ defines a unique diagonal passing through it, as in the first step of \cref{diagid}. 

\begin{figure}
	\centering
	\begin{tikzpicture}[scale=.5, every node/.style={transform shape}]
	\iffalse
	\draw (0,0) grid (1,3);
	\draw (0,0) grid (5,1);
	\draw (3,0) grid (5,3);
	\vertices{0}{0}{1}{3};
	\vertices{0}{0}{5}{1};
	\vertices{3}{0}{5}{3};
	\fi
	\draw (0,0) grid (5,3);
	\begin{scope}[shift={(-1,0)}]
	\vertices{1}{0}{6}{3};
	\end{scope}
	\draw[red,fill] (0,3) circle (.1);
	\draw[red,fill] (1,2) circle (.1);
	\draw[red,fill] (2,1) circle (.1);
	\draw[red,fill] (3,0) circle (.1);
	\draw[red] (-.5,3.5) -- (3.5,-.5);
	\node at (-.3,3) {$v$};
	\node at (3,-.3) {$w$};
	\vspace{1cm}
	
	\begin{scope}[shift={(7,0)}]
	\draw (-1,1.5) node[scale=2]{$\implies$};
	\node (a) at (1,3){};
	\draw[thick, green,->] (0,2) -- (a);
	\node (b) at (2,2){};
	\draw[thick, green,->] (1,1) -- (b);
	\node (c) at (3,1){};
	\draw[thick, green,->] (2,0) -- (c);
	\node (d) at (4,0){};
	\draw[thick, green,->] (3,-1) -- (d);
	\draw (0,0) grid (5,3);
	\begin{scope}[shift={(-1,0)}]
	\vertices{1}{0}{6}{3};
	\end{scope}
	\draw[red,fill] (0,3) circle (.1);
	\draw[red,fill] (1,2) circle (.1);
	\draw[red,fill] (2,1) circle (.1);
	\draw[red,fill] (3,0) circle (.1);
	%\draw[red] (-.5,3.5) -- (3.5,-.5);
	\node at (-.3,3) {$v$};
	\node at (3,-.3) {$w$};
	
	\draw[red, very thick] (3-.1, -1-.1) -- (3+.1,-1+.1);
	\draw[red, very thick] (3+.1, -1-.1) -- (3-.1,-1+.1);
	
	\draw (6,1.5) node[scale=2]{$\implies$};
	%\draw (8.9,.4) node{VC};
	
	\begin{scope}[shift={(7,0)}]
	\draw[opacity=.5,gray, dotted] (0,0) grid (5,3);
	\node (a) at (1,3){};
	\draw[thick, green,->] (0,2) -- (a);
	\node (b) at (2,2){};
	\draw[thick, green,->] (1,1) -- (b);
	\node (c) at (3,1){};
	\draw[thick, green,->] (2,0) -- (c);
	\node (d) at (4,0){};
	\draw[thick, green,->] (3,-1) -- (d);
	\draw (0,0) grid (1,1);
	\draw (1,3) grid (5,3);
	\draw (2,2) grid (5,2);
	\draw (3,1) grid (5,1);
	\draw (4,0) grid (5,0);
	\draw (0,0) grid (0,2);
	\draw (0,0) grid (2,0);
	
	\draw (2,3) grid (5,2);
	\draw (3,2) grid (5,1);
	\draw (4,1) grid (5,0);
	\begin{scope}[shift={(-1,0)}]
	\vertices{1}{0}{2}{1};
	\vertices{1}{2}{1}{2};
	\vertices{3}{0}{3}{0};
	\vertices{2}{3}{6}{3};
	\vertices{3}{2}{6}{2};
	\vertices{4}{1}{6}{1};
	\vertices{5}{0}{6}{0};
	\end{scope}
	
	\draw[red, very thick] (3-.1, -1-.1) -- (3+.1,-1+.1);
	\draw[red, very thick] (3+.1, -1-.1) -- (3-.1,-1+.1);
	
	
	\begin{scope}[shift={(7,0)}]
	\draw (-1,1.5) node[scale=2]{$\implies$};
	\draw[opacity=.5,gray,dotted] (0,0) grid (5,3);
	\draw (1,1) grid (5,3);
	\draw (5,0) grid (5,1);
	\begin{scope}[shift={(-1,0)}]
	\vertices{2}{1}{6}{3};
	\vertices{6}{0}{6}{0};
	\end{scope}
	\draw[red, very thick] (4-.1, 0-.1) -- (4+.1,0+.1);
	\draw[red, very thick] (4+.1, 0-.1) -- (4-.1,0+.1);
	\end{scope}
	
	\end{scope}
	\end{scope}
	
	\end{tikzpicture}
	\caption{Contracting the highlighted diagonal by deleting the diagonal vertices and merging the vertices immediately opposite.}\label{diagid}
\end{figure}

We say that the diagonal is \emph{contractible} if each internal vertex and each internal face it intersects have degree 4. In this case, diagonal contraction proceeds by selecting all vertices on the diagonal between $v$ and $w$, the last vertex on the diagonal before it reaches the external face. For each selected vertex $v_1$, delete $v_1$ and combine each neighbor of $v_1$ with its mirror image across the diagonal, as shown in \cref{diagid}. If a vertex combines with a missing vertex (denoted by a red ``x'' in the figure), then that vertex is deleted.


\begin{theorem}\label{diagthm}
	Let $G$ be a subgraph of the square lattice. Let $G'$ be the result of applying a diagonal contraction to a contractible diagonal from a black corner vertex $v$ to a vertex $w$. If $w$ has degree 2, then 
	$$|\cb(G)| = 2|\cb(G')|  \text{ and } |\cw(G)|=|\cw(G')|.$$
	Otherwise,
	$$|\cb(G)| = |\cb(G')|  \text{ and } |\cw(G)|=|\cw(G')|.$$
\end{theorem}


\begin{example}\label{aztec}
	Let us apply diagonal contraction to the a well-known class of graphs. The \emph{Aztec diamond} of rank $n$ is a diamond of side length $n$ in the square lattice. The Aztec diamonds of rank 1, 2, and 3 are shown in \cref{aztecex}.
	
	\begin{figure}[H]
		\centering
		\begin{tikzpicture}[scale=.5]
		\draw (0,0) grid (1,1);
		\vertices{0}{0}{1}{1};
		
		\begin{scope}[shift={(4,0)}]
		\draw (0,-1) grid (1,2);
		\draw (-1,0) grid (2,1);
		\vertices{0}{-1}{1}{2};
		\vertices{-1}{0}{2}{1};
		\end{scope}
		
		\begin{scope}[shift={(10,0)}]
		\draw (0,-2) grid (1,3);
		\draw (-2,0) grid (3,1);
		\draw (-1,-1) grid (2,2);
		\vertices{0}{-2}{1}{3};
		\vertices{-2}{0}{3}{1};
		\vertices{-1}{-1}{2}{2};
		\end{scope}
		\end{tikzpicture}
		\caption{The Aztec diamonds of rank 1, 2, and 3.}
		\label{aztecex}
	\end{figure}

	Let $G_n$ be the rank $n$ Aztec diamond. Performing two diagonal contractions as shown below reduces $G_n$ to $G_{n-1}$. 
	

	
	\begin{figure}[H]
		\centering
	\begin{tikzpicture}[scale=.5]
		%\draw[red] (-2.2,-.2) -- (1.2,3.2);
		
		\node (a) at (-1,0){};
		\draw[green,thick, ->] (-2,1)-- (a);
		\node (a) at (0, 1){};
		\draw[green,thick,->] (-1,2) -- (a);
		\node (a) at (1, 2){};
		\draw[green,thick,->] (0,3) -- (a);
		
		\draw (0,-2) grid (1,3);
		\draw (-2,0) grid (3,1);
		\draw (-1,-1) grid (2,2);
		\vertices{0}{-2}{1}{3};
		\vertices{-2}{0}{3}{1};
		\vertices{-1}{-1}{2}{2};
		
		\draw[fill,red] (-2,0) circle (.1) (-1,1) circle (.1) (0, 2) circle (.1)
		(1, 3) circle (.1);
		
		\begin{scope}[shift={(10,0)}]
		\draw (-4.5, .5) node[scale=1]{$\implies$};
		
		\node (a) at (1,1) {};
		\draw[green, thick, ->] (2,2) -- (a);
		\node (a) at (2,0) {};
		\draw[green, thick, ->] (3,1) -- (a);
		
		\draw[gray,opacity=.5,dotted] (0,-2) grid (1,3);
		\draw[gray,opacity=.5,dotted] (-2,0) grid (3,1);
		\draw[gray,opacity=.5,dotted] (-1,-1) grid (2,2);
		
		\draw (0,-2) grid (1,1);
		\draw (1,0) grid (2,2);
		\draw (-1,-1) grid (2,0);
		\draw (2,0) grid (3,1);
		\vertices{0}{-2}{1}{1};
		\vertices{1}{0}{2}{2};
		\vertices{2}{0}{3}{1};
		\vertices{-1}{-1}{2}{0};
		
		\draw[fill,red] (1,2) circle (.1) (2,1) circle (.1) (3,0) circle (.1);
		\end{scope}
		
		\begin{scope}[shift={(20,0)}]
		\draw (-4.5, .5) node[scale=1]{$\implies$};
		
		\draw[gray,opacity=.5,dotted] (0,-2) grid (1,3);
		\draw[gray,opacity=.5,dotted] (-2,0) grid (3,1);
		\draw[gray,opacity=.5,dotted] (-1,-1) grid (2,2);
		
		\draw (0,-2) grid (1,1);
		\draw (-1,-1) grid (2,0);
		\vertices{0}{-2}{1}{1};
		\vertices{-1}{-1}{2}{0};
		\end{scope}
		
		
	\end{tikzpicture}
\end{figure}
	
Since both diagonal contractions end on a vertex of degree 2, 
$|\mathcal C(G_n)| = 2^2|\mathcal C(G_{n-1})|.$ An easy induction argument then shows that
$$|\mathcal C (G_n)| = 2^{2n}.$$
Since there are $2^{2n}$ channels in $G_n$, by channeling twos it follows that $2^n$ divides the number of matchings of $G_n$. Indeed, it is well-known that $G_n$ has $2^{\binom{n+1}{2}}$ matchings.
\end{example}



\section{Billiards and Channels}\label{secbounce}

For an arbitrary graph, it is not clear how to identify all channels contained within it. 
In this section we give a geometric approach to channel construction based on a phenomenon that can be observed in the channels of a rectangle grid graph. 

\subsection{Billiard paths}

In the rectangle, we note that channels tend to form along diagonal lines as in the following figure. This pattern was studied by Tomei and Vieira in \cite{Tomei2002}, where they described it in terms of polygonal tilings of the rectangle. We propose an alternative description. 
By extending these diagonals, we find that these lines form a path which reflects off the edges of a larger rectangle, as shown below. The channel vertices are vertices in the interior of this larger rectangle which intersect exactly one line from this path.
\begin{figure}[H]
	\centering
	\begin{tikzpicture}[scale=.5]
	\draw[dotted, opacity=.5] (-1,-1) grid (8,5);
	\draw (0,0) grid (7,4);
	\pgfmathsetmacro{\chr}{0.2}
	
	\draw[red] (-1,-1) -- (5,5)--(8,2)--(5,-1)--(-1,5);
	
	\foreach \coord in %
	{(0,0),(1,1),(1,3),(0,4),(3,1),(3,3),(4,0),(4,4),(6,0),(6,4),(7,1),(7,3)}
	\draw[fill,orange] \coord circle (\chr);
	
	\vertices{0}{0}{7}{4}
	
	\begin{scope}[shift={(13,0)}]
	\node at (-3,2) {$\iff$};
	\draw[dotted, opacity=.5] (-1,-1) grid (8,5);
	\draw (0,0) grid (7,4);
	\pgfmathsetmacro{\chr}{0.2}
	
	\foreach \x in {-1, 0, ..., 4}
	\fill[opacity = .1, red] (\x,\x) rectangle ++(1,1);
	\foreach \x in {-1, 0, ..., 4}
	\fill[opacity = .1, red] (\x,3-\x) rectangle ++(1,1);
	\foreach \x in {-1, 0, ..., 1}
	\fill[opacity = .1, red] (6+\x,\x) rectangle ++(1,1);
	\foreach \x in {-1, 0, ..., 1}
	\fill[opacity = .1, red] (6+\x,3-\x) rectangle ++(1,1);
	%(-1,-1) -- (5,5)--(8,2)--(5,-1)--(-1,5);
	
	\foreach \coord in %
	{(0,0),(1,1),(1,3),(0,4),(3,1),(3,3),(4,0),(4,4),(6,0),(6,4),(7,1),(7,3)}
	\draw[fill,orange] \coord circle (\chr);
	
	\vertices{0}{0}{7}{4}
	
	\end{scope}
	
	\end{tikzpicture}
\end{figure}

Notice that we may recover the path, given that it was a path through black vertices, by remembering just the faces that it passes through. This viewpoint of the path will allow us to define a similar structure on a wide class of graphs called inner semi-Eulerian graphs. 

\begin{definition}\label{def:bp}
		We say that a bipartite planar graph $G$ is \emph{inner semi-Eulerian} if every internal black vertex of $G$ has even degree. Let $G$ be inner semi-Eulerian and let $F$ denote the set of internal faces in $G$. We say that a subset of faces $B \subseteq F$ of $G$ is a \emph{billiard path} if the following hold:
		\begin{itemize}
		    \item if $b$ is an internal black vertex, then either all faces incident to $b$ are in $B$, no faces incident to $b$ are in $B$, or every second face incident to $b$ is in $B$.
			
			\item if $b$ is an external black vertex, then either all internal faces incident to $b$ are in $B$ or no internal faces incident to $b$ are in $B$. 
		\end{itemize}
		Denote the set of billiard paths in $G$ by $\bp(G)$.
\end{definition}
When $G$ is a full subgraph of the square lattice with all internal faces being unit squares, this agrees with the intuitive notion of billiard paths as the paths traced out by a collection of billiard balls. Note that $\varnothing$ and $F$ are trivially billiard paths for every graph. As with channels, we may define the sum of two billiard paths to be their symmetric difference, making $\bp(G)$ a vector space over $\Z/2\Z$. 


We have a canonical basis for $\bp(G)$ such that the basis billiard paths are mutually disjoint. Indeed, define a graph $G_\bp$ with vertex set $F$ and edges between $f$ and $f'$ if they satisfy one of the following:
\begin{itemize}
	\item $f$ and $f'$ are incident to the same internal black vertex $b$ and are separated by an odd number of faces incident to $b$.
	
	\item $f$ and $f'$ are incident to the same external black vertex $b$.
\end{itemize}
Then the connected components of $G_\bp$ are independent billiard paths that span $\bp(G)$. This is called the \emph{path basis} for $G$. This is particularly useful since as we shall soon see, billiard paths in $G$ are equivalent to channels in a subgraph of $G$.


\begin{definition}
	Let $G$ be inner semi-Eulerian. Then the \emph{inner subgraph} of $G$, denoted $G'$, is the induced subgraph on the internal vertices of $G$. Given any inner semi-Eulerian graph $H$, an \emph{outer completion} of $H$ is an inner semi-Eulerian graph $G$ such that $G' = H$.
\end{definition}

\begin{figure}
		\centering
	\begin{tikzpicture}[scale=.5]
	\draw[ black] (0,0) grid (3,5);
	\draw (0,0) grid (5,3);
	
	\fill[opacity = .1, red] (0,0) rectangle ++(1,1);
	\fill[opacity = .1, red] (1,1) rectangle ++(1,1);
	\fill[opacity = .1, red] (2,2) rectangle ++(1,1);
	\fill[opacity = .1, red] (2,3) rectangle ++(1,1);
	\fill[opacity = .1, red] (1,4) rectangle ++(1,1);
	\fill[opacity = .1, red] (0,4) rectangle ++(1,1);
	\fill[opacity = .1, red] (0,3) rectangle ++(1,1);
	\fill[opacity = .1, red] (1,2) rectangle ++(1,1);
	\fill[opacity = .1, red] (2,1) rectangle ++(1,1);
	\fill[opacity = .1, red] (3,0) rectangle ++(1,1);
	\fill[opacity = .1, red] (4,0) rectangle ++(1,1);
	\fill[opacity = .1, red] (4,1) rectangle ++(1,1);
	\fill[opacity = .1, red] (3,2) rectangle ++(1,1);
	
	
	\draw[red] (0,0) -- (3,3) -- (1,5) -- (0,4) -- (4,0)--(5,1)--(3,3);
	
	%\pgfmathsetmacro{\radius}{0.1}
	
	\vertices{0}{0}{3}{5}
	\vertices{4}{0}{5}{3}
	
	\begin{scope}[shift={(10,0)}]
	\draw[ black] (0,0) grid (3,5);
	\draw (0,0) grid (5,3);
	
	\fill[opacity = .1, red] (0,1) rectangle ++(1,1);
	\fill[opacity = .1, red] (0,2) rectangle ++(1,1);
	\fill[opacity = .1, red] (1,3) rectangle ++(1,1);
	\fill[opacity = .1, red] (2,4) rectangle ++(1,1);
	\fill[opacity = .1, red] (1,0) rectangle ++(1,1);
	\fill[opacity = .1, red] (2,0) rectangle ++(1,1);
	\fill[opacity = .1, red] (3,1) rectangle ++(1,1);
	\fill[opacity = .1, red] (4,2) rectangle ++(1,1);
	
	
	\draw[red] (3,5) -- (0,2) -- (2,0) -- (5,3);
	
	%\pgfmathsetmacro{\radius}{0.1}
	
	\vertices{0}{0}{3}{5}
	\vertices{4}{0}{5}{3}
	\end{scope}
	
	
	\begin{scope}[shift={(20,0)}]
	
    \begin{scope}[opacity=.1]
	\draw (0,0) grid (3,5);
	\draw (0,0) grid (5,3);
    \vertices{0}{0}{3}{5}
	\vertices{4}{0}{5}{3}
    \end{scope}
    
	\fill[opacity = .1, red] (0,0) rectangle ++(1,1);
	\fill[opacity = .1, red] (1,1) rectangle ++(1,1);
	\fill[opacity = .1, red] (2,2) rectangle ++(1,1);
	\fill[opacity = .1, red] (2,3) rectangle ++(1,1);
	\fill[opacity = .1, red] (1,4) rectangle ++(1,1);
	\fill[opacity = .1, red] (0,4) rectangle ++(1,1);
	\fill[opacity = .1, red] (0,3) rectangle ++(1,1);
	\fill[opacity = .1, red] (1,2) rectangle ++(1,1);
	\fill[opacity = .1, red] (2,1) rectangle ++(1,1);
	\fill[opacity = .1, red] (3,0) rectangle ++(1,1);
	\fill[opacity = .1, red] (4,0) rectangle ++(1,1);
	\fill[opacity = .1, red] (4,1) rectangle ++(1,1);
	\fill[opacity = .1, red] (3,2) rectangle ++(1,1);
	\begin{scope}[shift={(1,1)}]
	\draw[ black] (0,0) grid (1,3);
	\draw (0,0) grid (3,1);
	
	%\draw[red] (-1,3)--(0,4);
	%\draw[red] (-1,-1)--(2,2);
	%\draw[red] (3,-1)--(4,0);
	%\draw[red] (3,-1)--(-1,3);
	%\draw[red] (0,4)--(4,0);
	
	\pgfmathsetmacro{\chr}{0.2}
	\draw[fill,orange] (0,0) circle (\chr);
	\draw[fill,orange] (0,2)  circle (\chr);
	\draw[fill,orange] (1,3)  circle (\chr);
	\draw[fill,orange] (2,0)  circle (\chr);
	\draw[fill,orange] (3,1) circle (\chr);

	\vertices{0}{0}{1}{3}
	\vertices{2}{0}{3}{1}
	\end{scope}
	\end{scope}
	
	\end{tikzpicture}
	\caption{A graph with its two path basis elements (shown formally as the set of shaded faces and informally as the path drawn above it). To the right we show the corresponding channel on the inner subgraph. } 
	\label{algex}
\end{figure}

Given an inner semi-Eulerian graph $H$, we may always construct an outer completion $G$ such that $G'=H$ by taking a copy of the boundary of $H$, expanding it so that $H$ lies within it, and adding edges between the two copies of the boundary as needed to make the graph inner semi-Eulerian. Given a billiard path in $G$, we may construct an associated channel in $G'$ as follows. Let $B \in \bp(G)$ be a billiard path. Define
$$\ch\colon \bp(G) \longrightarrow \cb(G') $$
by setting the vertices in $\ch(B)$ to be the internal black vertices $b$ of $G$ for which exactly half of the faces incident to $b$ are in $B$.

\begin{lemma}
	The map $\ch$ is a group homomorphism from $\bp(G)$ to $\cb(G')$.
\end{lemma}

We can now state our main result on billiard paths. Recall that the reduced dual graph of $G$ is the dual graph with the vertex corresponding to the external face of $G$ removed.

\begin{theorem}\label{bounce}
	Let $G$ be inner semi-Eulerian and let $G'$ be the inner subgraph of $G$. Let $c$ be the number of connected components of the reduced dual graph of $G$. Then 
	$$|\bp(G)| = 2^c|\cb(G')|. $$
	In particular,
	$2^{-c}|\bp(G)|$ divides the number of matchings of $G'$.
\end{theorem}

\iffalse
\begin{remark}
	The argument we use to show surjectivity of $\ch\colon \bp(G) \rightarrow \cb(G')$ above essentially uses the fact that the first homology group of $G$ is 0, which follows since $G$ is simply connected as a planar graph. The difficulty with directly applying this interpretation arises from our treatment of the external edges.
\end{remark}
\fi


Thus our study of channels in appropriate graphs $H$ (in particular, 
all inner semi-Eulerian graphs) reduces to the study of billiard paths in an outer completion $G$. Billiard paths are considerably easier to work with since every face of $G$ is contained in a unique element of the path basis of $G$. In general there is no such basis for the channels of $H$; vertices of $H$ may be contained in no channel and there may be no channel basis for $H$ with pairwise disjoint elements. However, any path basis element can be found by starting with a face of $G$ and adding additional faces as required by the definition of billiard paths. In \cite{Barkley2019}, we use this to give an algorithm for constructing the path basis for certain grid graphs which is almost linear in the perimeter of the graph.

\subsection{Arithmetic billiards}\label{arithmetic}
Let us find the billiard paths for the rectangle grid graph $\mathcal R_{m+1\times n+1}$, an outer completion of $\mathcal R_{m-1\times n-1}$. For this graph, we may use our interpretation of billiard paths as the paths traced out by billiard balls travelling at 45 degree angles. We begin by straightening out the billiard paths; to do so, we tile the plane with copies of our rectangle.

\begin{figure}[H]
	\centering
	\begin{tikzpicture}[scale=.5]
	\draw (0,0) rectangle (3,2);
	
	\draw[thick, red] (0,0) -- (2,2) -- (3,1)
		-- (2,0) -- (0,2);
		
	\draw[fill, blue!50!brown] (0,0) circle (.1);
	\draw[fill, orange!50!brown] (3,0) circle (.1);
	\draw[fill, green!50!brown] (0,2) circle (.1);
	\draw[fill, yellow!50!brown] (3,2) circle (.1);
	
	\begin{scope}[shift={(6,-2)}]
	\draw (-1.5, 3) node[scale=1]{$\iff$};
	\begin{scope}[xscale=3,yscale=2]
	\draw (0,0) grid (2,3);
	\end{scope}
	\draw[thick, red] (0,0) -- (3*2,2*3);
	\foreach \x in {0,2} {
	\foreach \y in {0,2} {
	\draw[fill, blue!50!brown] (3*\x,2*\y) circle (.1);
	}}
	\foreach \x in {1} {
		\foreach \y in {0,2} {
			\draw[fill, orange!50!brown] (3*\x,2*\y) circle (.1);
	}}
	\foreach \x in {0,2} {
		\foreach \y in {1,3} {
			\draw[fill, green!50!brown] (3*\x,2*\y) circle (.1);
	}}
	\foreach \x in {1} {
		\foreach \y in {1,3} {
			\draw[fill, yellow!50!brown] (3*\x,2*\y) circle (.1);
	}}
	\end{scope}
	\end{tikzpicture}
	\caption{A rectangle used to tile the plane. The coloring is provided as a visual indicator of the rectangle's orientation in the tessellation. Any billiard path on the left corresponds to a line of slope 1 on the right and vice versa.}
\end{figure}
We can then lift the billiard path to a straight line of slope 1 in the tessellation. A billiard path between two corners of $\mathcal R_{m+1\times n+1}$ will lift to the diagonal of a square in the tessellation. Since $\mathcal R_{m+1 \times n+1}$ has side lengths $m$ and $n$, this square will have side length $\lcm(m,n)$, so the path will pass through $\lcm(m,n)$ faces.

Suppose at least one of $m+1$ and $n+1$ is even so that exactly two corners of $\mathcal R_{m+1 \times n+1}$ are black. Of the billiard paths on black vertices, one passes through both of the black corners of the rectangle and passes through $\lcm(m,n)$ faces. The others lift to a diagonal of a square of side length $2 \lcm(m,n)$ (twice as long since they must return to their starting point) and hence pass through $2 \lcm(m,n)$ squares. Since every internal face is part of a unique path basis element, we may now count the billiard paths for $\mathcal R_{m+1\times n+1}$.


\begin{theorem}
	The rectangle grid graph $\mathcal R_{m+1\times n+1}$ with $(m+1)(n+1)$ even has a path basis of size
	$$\frac{\gcd(m,n)+1}{2} .$$
\end{theorem}
\begin{proof}
	There are $mn$ total internal faces in $\mathcal R_{m+1\times n+1}$. From the above, $mn-\lcm(m,n)$ of these are part of a path basis element not passing through a corner. Each such basis element uses $2\lcm(m,n)$ internal faces. Thus there are
	$$\frac{mn - \lcm(m,n)}{2\lcm(m,n)}
		= \frac{\gcd(m,n)-1}{2}$$
	non-corner path basis elements. Adding back the last path basis element gives the claim.
\end{proof}

\begin{corollary}
	The rectangle grid graph $\mathcal R_{m-1\times n-1}$ with $(m-1)(n-1)$ even has
	$$|\cb(\mathcal R_{m-1\times n-1})| = 2^{\frac{\gcd(m,n)-1}{2}}. $$
\end{corollary}
\begin{proof}
	The inner subgraph of $\mathcal R_{m+1\times n+1}$ is $\mathcal R_{m-1 \times n-1}$, and the reduced dual graph of $\mathcal R_{m\times n}$ is connected. Thus the result follows by \cref{bounce}.
\end{proof}

\begin{corollary}
	The number of matchings of $\mathcal R_{m-1\times n-1}$ is divisible by
	$$2^{\frac{\gcd(m,n)-1}{2}}. $$
\end{corollary}
\begin{proof}
	If $m-1$ and $n-1$ are both odd, then $\m=0$ and the claim follows. Otherwise, the hypothesis of the previous corollary holds, and we may channel twos to arrive at the result.
\end{proof}

%% if you use biblatex then this generates the bibliography
%% if you use some other method then remove this and do it your own way
\printbibliography



\end{document}
