\documentclass{article}
\usepackage{amsthm, amsmath, amssymb, amsfonts, graphics}
\def\EE{\mathcal{E}}
\def\FF{\mathcal{F}}
\def\LL{\mathcal{L}}
\def\II{\mathcal{I}}
\def\UU{\mathcal{U}}
\def\GG{\mathcal{G}}
\def\Copen{\breve{C}}
\def\Cbound{\partial C}
\def\ZZ{\mathbb{Z}}
\def\RR{\mathbb{R}}
\def\C{\mathbf{C}}
\def\N{\mathbf{N}}
\def\E{\mathbf{E}}
\def\S{\mathbf{S}}
\def\W{\mathbf{W}}
\def\NE{\N\E}
\def\NW{\N\W}
\def\NW{\N\W}
\def\SE{\S\E}
\def\SW{\S\W}
\def\q{\mathbf{?}}
\def\tC{\widetilde{\mathbf{C}}}
\def\tN{\widetilde{\mathbf{N}}}
\def\tE{\widetilde{\mathbf{E}}}
\def\tS{\widetilde{\mathbf{S}}}
\def\tW{\widetilde{\mathbf{W}}}
\def\tNE{\widetilde{\N\E}}
\def\tNW{\widetilde{\N\W}}
\def\tNW{\widetilde{\N\W}}
\def\tSE{\widetilde{\S\E}}
\def\tSW{\widetilde{\S\W}}
\def\lfloortwo{\lfloor \lfloor}
\def\rfloortwo{\rfloor \rfloor}
\def\lceiltwo{\lceil \lceil}
\def\rceiltwo{\rceil \rceil}
\def\cont{\ensuremath{\Rightarrow \Leftarrow}}
\def\maps{\colon}
\def\gwof{graph with open faces }
\def\gwofs{graphs with open faces }
\setlength{\unitlength}{1 pt}
\def\cross {
\begin{picture}(10, 10)
\put(0,5){\line(1,0){10}}
\put(5,0){\line(0,1){10}}
\end{picture} }
\def\backwrench{
\begin{picture}(10, 10)
\put(8,0) {\line(0,1){2}}
\put(0,8) {\line(1,0){2}}
\put(2,10) {\line(0,-1){2}}
\put(10,2) {\line(-1,0){2}}
\put(2,8) {\line(1,-1){4}}
\end{picture} }
\def\wrench{
\begin{picture}(10,10)
\put(2,0) {\line(0,1){2}}
\put(0,2) {\line(1,0){2}}
\put(8,10) {\line(0,-1){2}}
\put(10,8) {\line(-1,0){2}}
\put(8,8) {\line(-1,-1){4}}
\end{picture}}
\newtheorem*{MT1}{The Main Theorem (First Statement)}
\newtheorem*{MT2}{The Main Theorem (Second Statement)}
\newtheorem*{MT}{The Main Theorem}
\newtheorem*{MTinf}{The Main Theorem (Using Infinite Completions)}
\newtheorem*{GR}{The Gale-Robinson Theorem}
\newtheorem*{URT}{The Urban Renewal Theorem}
\newtheorem*{Kuo}{The Condensation Theorem}
\newtheorem{Definition}{Definition}
\newtheorem{Proposition}{Proposition}
\newtheorem{Lemma}{Lemma}
\newtheorem{Case}{Case}
\newcommand{\setleftmargin}[1]{
\addtolength{\textwidth}{\oddsidemargin}
\addtolength{\textwidth}{1in}
\addtolength{\textwidth}{-#1}
\setlength{\oddsidemargin}{-1in}
\addtolength{\oddsidemargin}{#1}
\setlength{\evensidemargin}{\oddsidemargin}
}
\newcommand{\setrightmargin}[1]{
\setlength{\textwidth}{8.5in}
\addtolength{\textwidth}{-\oddsidemargin}
\addtolength{\textwidth}{-1in}
\addtolength{\textwidth}{-#1}
}
\newcommand{\settopmargin}[1]{
\addtolength{\textheight}{\topmargin}
\addtolength{\textheight}{1in}
\addtolength{\textheight}{\headheight}
\addtolength{\textheight}{\headsep}
\addtolength{\textheight}{-#1}
\setlength{\topmargin}{-1in}
\addtolength{\topmargin}{-\headheight}
\addtolength{\topmargin}{-\headsep}
\addtolength{\topmargin}{#1}
}
\newcommand{\setbottommargin}[1]{
\setlength{\textheight}{11in}
\addtolength{\textheight}{-\topmargin}
\addtolength{\textheight}{-1in}
\addtolength{\textheight}{-\footskip}
\addtolength{\textheight}{-#1}
}
\newcommand{\setallmargins}[1]{
\settopmargin{#1}
\setbottommargin{#1}
\setleftmargin{#1}
\setrightmargin{#1}
}
\setallmargins{1 in}
\begin{document}
\section{Introduction and Terminology} \label{Intro}
In rough sketch, the main object of this paper is a function $f$ defined on a three dimensional lattice by a certain recurrence. We denote the set of initial conditions from which $f$ is generated by $\II$ and consider varying the shape of $\II$ inside this lattice. It turns out that the values $f$ are Laurent polynomials in the initial variables where every term has coefficient 1. We are able further more to find families of graphs such that $f$ gives generating functions for the perfect matchings of these graphs. Special cases of this result include being able to choose $\II$ so that $f$ gives us the values of three term Gale-Robinson seqeunces or such that the families of graphs are Aztec Diamonds, Fortresses and other common families of graphs with simple formulas for the number of their matchings.
In the next subsection, we introduce the vocabularly necesary to define $f$. In the following section, we introduce the vocabularly necessary to define the families of graphs.
\subsection{The Recurrence}
Set
$$\LL = \{ (n,i,j) \in \ZZ^3,\ n=i+j \mod 2 \}$$
and set
\begin{eqnarray*}
\EE &=& \{ (i,j,?) \in \ZZ^2 \times \{a,b,c,d\},\ i+j=1 \mod 2 \} \\
\FF &=& \{ (i,j) \in \ZZ^2 \}
\end{eqnarray*}
where $?$ denotes one of the four symbols $a$, $b$, $c$ and $d$.
We call $(i_1, j_1)$ and $(i_2, j_2) \in \FF$ ``lattice-adjacent'' if $|(i_1-i_2)|+|(j_1-j_2)|=1$. (Another notion of adjacency will arise later.)
For $(n,i,j) \in \LL$, let $C_{(n,i,j)}$ be the set of $(n',i',j') \in \LL$ such that
$$n+i \geq n'+i',\ n-i \geq n'-i',\ n+j \geq n'+j' \mathrm{\ and\ } n-j \geq n'-j'.$$
Let $\Copen_{(n,i,j)}$ be the set of $(n',i',j') \in \LL$ such that
$$n+i > n'+i',\ n-i > n'-i',\ n+j > n'+j' \mathrm{\ and\ } n-j > n'-j'.$$
Let $\Cbound=C \setminus \Copen$. We will call $C$, $\Copen$ and $\Cbound$ the ``cone'', ``inner cone'' and ``outer cone'' of $(n,i,j)$ respectively.
Let $h \maps \FF \mapsto \ZZ$ and define
\begin{eqnarray*}
\II &=& \{ (i,j,n) \in \LL,\ n = h(i,j) \} \\
\UU &=& \{ (i,j,n) \in \LL,\ n > h(i,j) \}.
\end{eqnarray*}
Assume that
\begin{enumerate}
\item $|h(i_1,j_1)-h(i_2,j_2)|=1$ if $(i_1,j_1)$ and $(i_2, j_2)$ are lattice-adjacent.
\item $(h(i,j),i,j) \in \LL.$
\item For any $(n,i,j) \in \LL$, $C_(n,i,j) \cap \UU$ is finite.
\end{enumerate}
Let $K$ be the field of formal rational functions in the following infinite families of variables: the family $x(i,j)$, $i$, $j \in \ZZ^2$ and the families $a(i,j)$, $b(i,j)$, $c(i,j)$, $d(i,j)$ where $i$, $j \in \ZZ^2$ and $i+j=0 \mod 2$. (Clearly, $\FF$ indexes the $x$'s and $\EE$ indexes the $a$'s, $b$'s, $c$'s and $d$'s. Let $R \subset K$ be the ring
$$\ZZ[x(i,j), 1/x(i,j), a(i,j), b(i,j), c(i,j), d(i,j)].$$
For reasons to appear later, we call the $x$'s the ``face variables'' and the $a$'s, $b$'s, $c$'s and $d$'s the ``edge variables.''
We define a function $f \maps \II \cup \UU \mapsto K$ $f(n,i,j)=x(i,j)$ for $(n,i,j) \in \II$ and
\begin{eqnarray*}
f(n,i,j) &=& \left( a(i+n-1,j)c(i-n+1,j)f(n-1,i,j+1)f(n-1,i,j-1) + \right. \\
& & \left. b(i,j+n-1)d(i,j-n+1)f(n-1,i+1,j)f(n-1,i-1,j) \right) / f(n-2,i,j)
\end{eqnarray*}
for $(n,i,j) \in \UU$. Our third condition on $h$ makes sure that this recurrence will terminate.
The main result of this paper is
\begin{MT1}
$f(n,i,j) \in R$ and, when written as a Laurent polynomial, each term appears with coefficient 1. Moreover, the exponent of each face variable is between $-1$ and $3$ (inclusive) and the exponent of each edge variable is $0$ or $1$.
\end{MT1}
To describe our result more precisely, we need to introduce some graph-theoretic terminology.
\subsection{Graphs With Open Faces}
Let $G_0$ be a connected finite planar graph with a specified embedding in the plane and let $e_1$, $e_2$, \dots $e_n$ be the edges of the outer face in cyclic order. (We write an edge twice if it occurs twice.) We define a ``graph with open faces'' to be such a graph $G_0$ with a given partition of the cycle $e_1$, \ldots $e_n$ into edge disjoint paths $e_i$, $e_{i+1}$, \dots $e_j$. (If an edge appears twice, it appears in two such paths, or else twice in one.)
Denote by $G$ the graph with open faces associated to $G_0$ and the partition above. We call a path $e_i$, \ldots $e_j$ in the given partition an ``open face'' of $G$. We denote the open faces of $G$ by $F_o(G)$. We refer an interior face of $G_0$ as a ``closed face'' of $G$ and denote the set of them by $F_c(G)$. We set $F(G)=F_o(G) \cup F_c(G)$ and call a member of $F(G)$ a face of $G$. Note that the exterior face of $G_0$ is \emph{not} a face of $G$.
We will refer to an edge or vertex of $G_0$ as an edge or vertex (respectively) of $G$. We say that an edge $e$ borders an open face $f$ of $G$ if $e$ lies in the associated path $e_i$, \dots $e_j$. All other incidence terminology (endpoint, adjacency of faces, etc.) should be intuitive by analogy to ordinary planar graphs. We use $E(G)$ and $V(G)$ to denote the edges and vertices of $G$.
The image associated to a \gwof is that open disks have had portions of their boundary glued to the outside of $G_0$ along the paths $e_i$, \dots $e_j$ with some additional boundary left hanging off into space. We will draw \gwofs as shown below
\includegraphics{diagram1.eps}
By a map $G' \hookrightarrow G$ we mean a triple of injections $V(G') \hookrightarrow V(G)$, $E(G') \hookrightarrow E(G)$ and $F(G') \hookrightarrow F(G)$ compatible with the adjacency relations. We say $G'$ is a sub-\gwof if such a map exists.
A matching of a \gwof $G$ is a collection of edges $M$ such that every vertex lies on exactly one edge of $M$. Let $R(G)$ be the ring $\ZZ[x_f, 1/x_f, y_e]$ where $x_f$ are formal variables indexed by $f \in F(G)$ and $y_e$ are formal variables indexed by $e \in E(G)$.
For $e\in E(G)$, set $\delta(e)=1$ if $e \in M$, $0$ otherwise. For $f \in F(G)$ and $M$ a matching of $G$, let $a$ be the number of edges of $f$ that lie $M$ and $b$ the number of edges of $f$ not in $M$. If $f \in F_c(G)$, set
$$\epsilon(f)=\left\lceil \frac{b-a}{2} \right\rceil-1 ;$$
if $f \in f_o(G)$ set
$$\epsilon(f)=\left\lceil \frac{b-a}{2} \right\rceil.$$
(Note that $\epsilon(f) \geq -1$.)
For any matching $M$, set
$$m(M)=\prod_e y_e^{\delta(e)} \prod_f x_f^{\epsilon(f)}.$$
For any \gwof $G$, set
$$m(G)=\sum_M m(M)$$
where the sum is over all matchings of $G$. We call $m(M)$ the matching monomial of $M$ and $m(G)$ the matching polynomial of $G$.
It will turn out that the actual graphs to which we will apply this definition are bipartite, so every closed face has an even number of edges and we may omit the $\lceil \ \rceil$ in this case. However, it will be convenient to have a definition that is valid for all graphs.
We can now give our second statement of the Main Theorem.
\begin{MT2}
For any $h$ subject to the conditions above and any $(n,i,j) \in \UU$, we can find a \gwof $G$, a decomposition $E(G)=E_w \sqcup E_u$ and injective maps $\alpha \maps E_w \mapsto \EE$, $\alpha \maps F \mapsto \FF$ such that, if we define $\alpha \maps R(G) \to R$ by $\alpha(x_f)=x(\alpha(f))$ for $f \in F(G)$, $\alpha(y_e)=?(i,j)$ where $\alpha(e)=(i,j,?)$ for $e \in E_w$ and $\alpha(y_e)=1$ for $e \in E_u$, then
$$f(n,i,j)=\alpha(m(G)).$$
\end{MT2}
Clearly, this will imply the previous statement, except for the bounds on the exponents and the claim that the coefficients are 1. The first will follow by showing as well that every closed face of $G$ has $\leq 8$ edges, and each open face of $G$ has $\leq 2$ edges. The second will follow by showing that the edges of $E_u$ are vertex disjoint, so a matching $M$ is uniquely determined by $M \cap E_w$.
\subsection{History}
One case of this was known explicitly prior to this paper: if $h(i,j)=0$ for $i+j=0 \mod 2$ and $h(i,j)=1$ for $i+j=1 \mod 2$ then we have replicated the theory of condensation of Aztec Diamond matchings \cite{Kuo}. Jim Propp in \cite{Propp} noted that a special case of the theorem (with many of the variables set equal to 1) would imply the (three term) Gale-Robinson theorem:
\begin{GR}
Given positive integers $k$, $a$ and $b$ with $a$, $bk$$
and $S_0=S_2=\cdots=S_{k-1}=1$. Then the $S_n$ are all positive integers.
\end{GR}
Note that the cases $(k,a,b)=(4,1,2)$ and $(5,1,2)$ are the fourth and fifth Somos sequence. No combinatorial proof of the Gale-Robinson theorem has previously been found, even for these small cases.
Propp computed $f(n,i,j)$ for the Somos-4 and Somos-5 case and conjectured essentially our first statement of the Main Theorem in this case. (Propp's recurrence is related to ours by applying various linear changes of variable and combining all of the edge variables into a single family $y(i,j)$.) Propp also conjectured that the terms of $f(n,i,j)$ would be in bijection with the matchings of a graph, with the $x$'s related in some manner to the faces and the $y$'s (our $a$'s, $b$'s, $c$'s and $d's$) related to the edges.
It is also also already known at least implicitly that the $f(n,i,j)$ lie in the ring $R$, but not that their coefficients are 1 or even that they are positive; nor that any combinatorial significance could be attached to them. This has been proven using the method of Cluster Algebra's \cite{FumZel} and was used to deduce the Gale-Robinson theorem above.
\subsection{Plan of the Paper}
In Section~\ref{Algorithm}, we will describe explicitly an algorithm we refer to as ``the method of crosses and wrenches'' for finding the graphs $G$. We will postpone proving the correctness of the algorithm to present applications of the theory in Section~\ref{Examples}. In particular, we will carry out the examples of Somos-4 and Somos-5 and show explicitly the families of graphs associated to them; we will also do the early steps of the computation for the general Gale-Robinson theorem. We will also show that, by choosing certain periodic functions for $h$, we can create fortress graphs \cite{Fort} and families of graphs studied by Chris Douglass \cite{Doug} and Matt Blum \cite{Blum}. The number of matchings of these graphs are powers of 5, 2 and 3 respectively, in each case we will give a rapid proof of this by induction from our Main Theorem.
In the Section~\ref{Urban}, we will give a proof that works by varying $\II$ and holding $(n,i,j)$ fixed. In the process, we will recover variants of the ``Urban Renewal''operations of \cite{Ciciu} and thus motivate his definitions. In Section~\ref{Kuo}, we will give a second proof, inspired by a proof of \cite{Kuo} for the Aztec Diamond case, that works by holding $\II$ fixed and varying $(n,i,j)$. We will here present a variation of Kuo's condensation result that has proven very useful.
\subsection{A Note on Simplification of Results}
One might wonder whether one could remove some of the complications of the statements of the theorems by setting some of the variables equal to 1. We could with no harm set the edge variables to 1 throughout this paper. We could also set the face variables equal to 1 as well, except for one place: our first proof of the Main Theorem is inductive and can introduce cases where the face variables are not 1 even if they all start as 1. (Of course, if we set both sets of variables equal to 1, the polynomials would collapse to integers, so the claim that all coefficients are 1 would become false.)
\section{The Method of ``Crosses and Wrenches''} \label{Algorithm}
In this section we describe how to find the graph $G$ discussed above. We perform no examples here as there will be many in Section~\ref{Examples}.
\subsection{An Infinite Graph in Which our Graphs Embed}
Let $h(i,j)$ be as defined in the previous section. We will associate to $h(i,j)$ an infinite planar graph $\GG$, inside which all of our \gwofs for the $f(n,i,j)$ will be embedded. The faces of $\GG$ will be indexed by the elements $(n,i,j)$ of $\II$, centered at the corresponding points $(i,j)$ in $\RR^2$. If $(i_1, j_1)$ and $(i_2, j_2)$ are lattice-adjacent (i.e. $|(i_1-i_2)-(j_1-j_2)|=1$) then $(n_1, i_1, j_2)$ borders $(n_2, i_2, j_2)$. In addition, if $|i_1-i_2|=|j_1-j_2|=1$ then $(n_1, i_1, j_1)$ borders $(n_2, i_2, j_2)$ iff $h(i_1, j_2) \neq h(i_2, j_1)$. No other pairs of faces border.
We refer to this method of finding $\GG$ as the ``method of crosses and wrenches'' because it can be describe geometrically by the following procedure: any quadruple of values
$$\begin{pmatrix}
h(i,j) & h(i+1, j) \\
h(i,j+1) & h(i+1,j+1)
\end{pmatrix}$$
must be of one of the following six types:
\begin{alignat*}{10}
{\begin{pmatrix}
h & h+1 \\
h+1 & h
\end{pmatrix}} \quad &
{\begin{pmatrix}
h+1 & h \\
h & h+1
\end{pmatrix}} \quad &
{\begin{pmatrix}
h & h+1 \\
h+1 & h+2
\end{pmatrix}} \\
{\begin{pmatrix}
h+2 & h+1 \\
h+1 & h
\end{pmatrix}} \quad &
{\begin{pmatrix}
h+1 & h \\
h+2 & h+1
\end{pmatrix}} \quad &
{\begin{pmatrix}
h+1 & h+2 \\
h & h+1
\end{pmatrix}}
\end{alignat*}
In the center of these squares, we draw a \cross, \backwrench or \wrench in the first and second, third and fourth, and fifth and sixth cases respectively.
\begin{alignat*}{10}
{\begin{pmatrix}
h & & h+1 \\
& \cross & \\
h+1 & & h
\end{pmatrix}} \quad &
{\begin{pmatrix}
h+1 & & h \\
& \cross & \\
h & & h+1
\end{pmatrix}} \quad &
{\begin{pmatrix}
h & & h+1 \\
& \backwrench & \\
h+1 & & h+2
\end{pmatrix}} \\
{\begin{pmatrix}
h+2 & & h+1 \\
& \backwrench & \\
h+1 & & h
\end{pmatrix}} \quad &
{\begin{pmatrix}
h+1 & & h \\
& \wrench & \\
h+2 & & h+1
\end{pmatrix}} \quad &
{\begin{pmatrix}
h+1 & & h+2 \\
& \wrench & \\
h & & h+1
\end{pmatrix}}
\end{alignat*}
We then connect the four points protruding from these symbols by horizontal and vertical edges. (We often have to bend the edges slightly to make this work. Kinks introduced in this way are not meant to be vertices, all the vertices come from the center of a $\cross$ or from the two vertices at the center of a $\wrench$ or $\backwrench$.)
\subsection{Labelling the Edges} \label{LabelEdges}
We now describe how to assign the members $(i,j,?)$ of $\EE$ to the edges of $\GG$. The middle edge of a wrench will not receive a label (these are the $E_u$ from our second statement of the Main Theorem). The horizontal and vertical edges are the edges that will be labeled with members of $\EE$. Such an edge lies between two faces $(n_1, i_1, j_1)$ and $(n_2, i_2, j_2)$ with $|i_1-i_2|+|j_1-j_2|=1$. Let the edge separating them receive the label $(i,j, ?)$. WLOG, $(i_1-i_2)+(j_1-j_2)=1$. (Otherwise, switch the names of $(i_1, j_1)$ and $(i_2,j_2)$.) There are four cases:
\begin{enumerate}
\item If $i_1>i_2$ and $n_1>n_2$ then $(i,j,?)=(i_1+n_2,j_1,a)=(i_2+n_1,j_2,a)$.
\item If $i_1>i_2$ and $n_1j_2$ and $n_1>n_2$ then $(i,j,?)=(i_1,j_1+n_2,b)=(i_2,j_2+n_1,b)$.
\item If $j_1>j_2$ and $n_1k$$
and $S_0=S_2=\cdots=S_{k-1}=1$. Then the $S_n$ are all positive integers.
\end{GR}
In this section, fix $k$, $a$ and $b$ and let $S_n$ be the sequence of the theorem. Define a map $\pi \maps \LL \mapsto \ZZ$ by
$$\pi \maps (n,i,j) \mapsto \frac{k}{2} (n+i+j) -a i- b j.$$
Set
$$\II=\pi^{-1}( \{0,1,2,\ldots,k-1 \} )$$
and
$$\UU=\pi^{-1} (\{k, k+1, k+2, \ldots \})$$
and define $f \maps \II \cup \UU \mapsto \ZZ$ by
$$f(n,i,j)=S_{\pi(n,i,j)}.$$
Propp observed (in slightly different terminology) that this choice of $f(n,i,j)$, $\II$ , $\UU$ obeys our recurrence where we set all the variables equal to 1. (We will often speak of ``setting a variable $z$ to 1.'' where $z$ is some member of the ring $R$. What we mean fromally is that we are now working working in $R/(z-1)$. If say that we set several variables $z_1$, \dots $z_i$ to 1, then we work in $R/(z_1-1, \ldots, z_i-1)$.) In this section we will find the $h$ associated to this choice of $\II$.
We will first need a notation. If $g(i,j)$ is any function of $i$ and $j$, define $\lfloortwo g(i,j) \rfloortwo$ to be the greatest integer $k$ such that $k \leq g(i,j)$ and $k=i+j \mod 2$; define $\lceiltwo g(i,j) \rceiltwo$ to be the least integer $k$ such that $k \geq g(i,j)$ and $k=i+j \mod 2$. We have
$$\lfloortwo g(i,j) \rfloortwo=2 \left\lfloor \frac{g(i,j) \pm (i+j)}{2} \right\rfloor \mp (i+j)$$
and
$$\lceiltwo g(i,j) \rceiltwo=2 \left\lceil \frac{g(i,j) \pm (i+j)}{2} \right\rceil \mp (i+j)$$
where we can take either choice of $\pm$ (and must take the opposite choice for $\mp$.)
$h(i,j)$ should be the unique integer $n$ such that $(n,i,j) \in \LL$ and $0 \leq \pi(n,i,j) < k$. We can see that such a unique integer exists because $\pi(n+2,i,j)=\pi(n,i,j)+k$. Let $\tilde{n}$ be such that $\pi(\tilde{n}, i,j)=0$, then $n=\lceiltwo \tilde{n} \rceiltwo$. Explicitly, we have
\begin{eqnarray*}
\tilde{n} &=& \frac{2}{k} \left( \left(a-\frac{k}{2} \right) i + \left(b-\frac{k}{2} \right) j \right) \\
&=& \left( \frac{2a}{k} i+\frac{2b}{k} j \right) - (i+j)
\end{eqnarray*}
Using the formula for $\lceiltwo \ \rceiltwo$ above, we get
$$ n=\lceiltwo \tilde{n} \rceiltwo = 2 \left\lceil \frac{a}{k} i + \frac{b}{k} j \right\rceil -(i+j). $$
\subsection{Somos 4 and 5}
Particularly interesting cases of the Gale-Robinson recurrence are $(k,a,b)=(4,2,1)$ and $(5,2,1)$, as these give Somos-sequences which have connections to theta functions. In these cases, we draw below the infinite graphs $\GG$ and the first several $G$. We have saved space by recording only the value of $h(i,j)$ for a $(h(i,j),i,j)$ triple and not labeling the edges.
\includegraphics{diagram10.eps}
\section{Proof I: Urban Renewal} \label{Urban}
In this section, we will prove the correctness of the crosses-and-wrenches algorithm. Our basic strategy is to hold the point $(n,i,j)$ where we are evaluating $f(n_0,i_0,j_0)$ fixed, while varying $h$. Our proof is by induction, with the base case $h(i,j)=\min(n_0 \pm (i-i_0), n_0 \pm (j-j_0))$. We use the infinite description of our graphs from section \ref{infext} so that we do not have to deal with open faces and other effects of the boundary.
\subsection{Some Easy Lemmas}
\begin{Lemma} \label{split}
Consider a \gwof $G$. Replace a vertex $G$ with two edges as below to form a new $G'$ and set the variables associated to those edges to 1.
\includegraphics{vertsplit.eps}
Then $M(G)=M(G')$.
\end{Lemma}
\begin{proof}
Any matching of the old graph can be transformed to a matching of the new graph uniquely by adding one of the two new edges. The additional edge in the matching contributes a factor of 1 in the product of the edge variables. The two faces adjacent to the new edges have one more used edge and one more unused edge than the corresponding faces of the previous matching, so they have the same exponent. The other faces are unaffected.
\end{proof}
%REDO variables
%
% V
% \ /
% \aaa/
% b c
% W b X c Y
% b c
% /ddd\
% / \
% Z
\begin{URT}
Suppose a \gwof $G$ contains the sub-\gwof
\includegraphics{preUR.eps}
with the indicated edge weights and face weights. (The face weights are in uppercase, the edge weights in lower case.) Create a new graph $G'$ by replacing this with
% \includegraphics{postUR.eps}
where
$$X'=(adWY+bcVZ)/X.$$
Then $m(G)=m(G')$. (That is, the matching polynomials are equal.)
\end{URT}
This theorem is almost that of \cite{Ciciu}. However, because he doesn't use face weights, his theorem involves slightly different replacements and yields a relation of the form $m(G)=(ac+bd) m(G')$.
\begin{proof}
We will create a correspondence between matchings of the two graphs. A matching of one graph may correspond either to one or two matchings of the other. The meaning of the diagrams below is that a matching of $G$ which contains the edge configuration of the left column corresponds to the matching(s) of $G'$ obtained by making the edge replacements in the right column.
\includegraphics{replace.eps}
In the first four cases, for any of the four outer faces, the number of used and unused edges each increase by 1 going from the left to the right column, so its exponent is unchanged. The edges that are used have the same weights. The center face has one edge adjacent to it and hence does not appear. Thus, the monomial is the same.
In case 5, the first transformation increases the exponents of $W$ and $Y$ by 1, adds the edges $a$ and $d$ and changes the contribution of the center face from $X$ to ${X'}^{-1}$. Similarly, the second transformation increases the exponents of $V$ and $Z$ by 1, adds the edges $b$ and $c$ and changes the contribution of the center face from $X$ to ${X'}^{-1}$. So this transformation is given by the variable substitution:
$$x=acvy{x'}^{-1}+bdwz{x'}^{-1}$$.
The sixth case is practically identical. This time, we want to group the matchings of $G$ that are of this case and correspond to the same matching of $G'$. Note that if one matching occurs, the other does. We are to change the contribution of the center face from $X^{-1}$ to $X'$ and either
\begin{enumerate}
\item delete edges $a$ and $d$ and reduce the exponents of $W$ and $Y$ by 1 or
\item delete edges $b$ and $c$ and reduce the exponents of $V$ and $Z$ by 1.
\end{enumerate}
This is accomplished by the substitution
$$(adWY+bcVZ)X^{-1}=X'.$$
This is exactly the substitution we make.
\end{proof}
\subsection{Proof of the Main Theorem}
Let $(n_0, i_0, j_0) \in \UU$ and let $h$ and $\tilde{h}$ be as in subsection \ref{infext}; let $\tilde{G}$ be the graph assosciated to $\tilde{h}$. Let $c(i,j)=\min(n_0 \pm (i-i_0), n_0 \pm (j-j_0))$, so $\tilde{h}(i,j)=\min(j(i,j), c(i,j))$. Our proof is by induction on $\sum_{i,j} c(i,j)-\tilde{h}(i,j)$.
If $\sum_{i,j} c(i,j)-\tilde{h}(i,j)=0$ then $\tilde{h}(i,j)=c(i,j)$ so $\tilde{G}$ is
\includegraphics{basecase.eps}
which has only the indicated matching (subject to the requirement that all but finitely many vertices are matched as required). The matching polynomial of this matching is $x(i_0,j_0)$. We also have in this case that $\tilde{h}(i_0,j_0)=c(i_0,j_0)=n_0$ so we have $f(n_0,i_0,j_0)=x(i_0,j_0)$.
If $\sum_{i,j} c(i,j)-\tilde{h}(i,j) > 0$ then, among the $(i,j)$ for which $\tilde{h}(i,j) < c(i,j)$ there is (at least) one with $\tilde{h}(i,j)$ minimal, let this be $(i,j)$. We claim that $\tilde{h}(i \pm 1,j)=\tilde{h}(i,j \pm 1)=\tilde{h}(i,j)+1$. We deal with the case of $\tilde{h}(i+1,j)$, the other four are similar. We have $\tilde{h}(i+1,j)=\tilde{h}(i,j) \pm 1$. If $\tilde{h}(i+1,j)=\tilde{h}(i,j)-1$, then $\tilde{h}(i+1,j) < \tilde{h}(i,j)$. This is only possible if $\tilde{h}(i+1,j)=c(i+1,j)$. But we have $c(i,j) > \tilde{h}(i,j)$ and, as $\tilde{h}(i,j)=c(i,j) \mod 2, we get
$$c(i,j) \geq \tilde{h}(i,j)+2=\tilde{h}(i+1,j)+1+2=c(i+1,j)+3.$$
As $|c(i,j)-c(i+1,j)=1$, this is impossible.
Thus, we have shown $\tilde{h}(i \pm 1,j)=\tilde{h}(i,j \pm 1)=\tilde{h}(i,j)+1$. So the face assosciated to $h(i,j)$ is a square. Apply the Urban Renewal Theorem to this square to create a new graph with the same matching polynomial. Then apply Lemma \ref{split} to this graph. The graph thus created will be the same as replacing any crosses whose vertex lies on the face $(i,j)$ by a wrench with one vertex on $(i,j)$ and \emph{vice versa}. Also, the edge weights adjacent to $(i,j)$ are interchanged with their diametric opposites and the weight $x(i,j)$ is replaced by a certain binomial.
The graph thus produced is precisely the graph produced by the function $h'$ where $h'(i,j)=h(i,j)+2$ and $h'=h$ everywhere else. By induction, the matching polynomial of this graph is $f(n_0,i_0,j_0)$ for the inital conditions $h'$. The $f$ for the initial conditions $h$ is given by replacing $x(i,j)$ by the same binomial as before. Thus, $f(n_0,i_0,j_0)$ is precisely given by the matching polynomial of the graph for $h'$ with $x(i,j)$ replaced by the said binomial, which by the Urban Renewal Theorem is precisely the matching polynomial of the graph for $h$.
\qedsymbol
\section{Proof II: Condensation} \label{Kuo}
\subsection{The Condensation Theorem}
The following is a strengthening of the result of \cite{Kuo}. We some notations. If $G$ is a \gwof and $S \subseteq V(G)$, let $\partial(S)$ elements of $S$ that border vertices of $G$ not in $S$. If $G$ is a bipartite \gwof, colored black and white, let $\delta(S)$ be the number of black vertices minus the number of white vertices. While $\delta(S)$ is only defined up to sign, we adopt the implicit assumption that, if $S_1$ and $S_2$ a both subsets of $V(G)$ that $\delta(S_!)$ and $\delta(S_2)$ are computed from the same coloring of $G$. Let $g(S)$ is the sub-\gwof of $G$ whose vertices are $S$, whose edges are the edges of $G$ that connect vertices of $S$ and whose faces are the faces of $G$ adjacent to such edges. We will only use the notation $g(S)$ in the case where the resulting \gwof is connected. Abuse notation for writing $m(S)$ to mean $m(g(S))$.
\begin{Kuo}
Let $G$ be a bipartite \gwof (recall that a \gwof is planar) and let the vertices of $G$ be partitioned into nine sets
$$V(G)=\C \sqcup \N \sqcup \NE \sqcup \E \sqcup \SE \sqcup \S \sqcup \SW \sqcup \W \sqcup \NW.$$
Denote by $X$ the set of sets $\{\C , \N , \NE , \E , \SE , \S , \SW , \W , \NW \}$
Assume that only vertices in the sets joined in the diagram below border each other. (Vertices may also border other vertices in the same set.)
Assume further that
$$\delta(\NE)=\delta(\SW)=1,\ \delta(\SE)=\delta(\NW)=-1,\ \delta(\C)=\delta(N)=\delta(E)=\delta(S)=\delta(W).$$
Finally, assume that $\partial(\NE)$ and $\partial(\SW)$ are entirely black and $\partial(\NW)$ and $\partial(\SE)$ are entirely white.
$$DIAGRAM$$
Then, if we set the face variables equal to 1 we have
\begin{multline*}
m(G) m(\C)=m(\N \cup \NE \cup \NW \cup \C) m(\S \cup \SE \cup \SW \cup C) m(\E) m(\W) + \\
m(\E \cup \NE \cup \SE \cup \C) m(\W \cup \NW \cup \SW \cup C) m(\N) m(\S).
\end{multline*}
where we assume that, for every set $\q$ of vertices appearing inside an $m$, $g(\q)$ is connected.
For $f$ a face and $\q \subseteq V(G)$, let $f(\q)$ denote the number of vertices of $f$ in $\q$. The theorem remains true if we do not set $x_f$ equal to 1 when any of the following hold
\begin{enumerate}
\item All the vertices of $f$ lie in the same $\q \in X$.
\item The vertices of $f$ lie in two $\q$'s, $\q_1$ and $\q_2$, $f(q_1)$ and $f(q_2)$ are odd and $f$ is closed.
\item The vertices of $f$ lie in three $\q$'s, $q_1$, $q_2$ and $q_3$ such that not all the $f(\q_i)$ are even, $f(\C)$ is even and $f$ is closed.
\end{enumerate}
(This is not an exhaustive list of cases, it is the smallest one that could be found to apply to all graphs that will appear in this paper.)
\end{Kuo}
\begin{proof}
Let $G$ always denote a graph obeying the above hypotheses. We define a northern join a set $\gamma$ of edges of $G$ which obey any of the following conditions:
\begin{enumerate}
\item A path with one endpoint in $\NE$, the other endpoint in $\NW$ and the intermediate vertices in $\C$.
\item A single edge with one endpoint in $\NE$ and the other in $\NW$.
\item A pair of edges, one joining $\NE$ to $\N$ and the other joining $\NW$ to $\N$.
\end{enumerate}
We define an eastern, southern or western join analogously.
\setcounter{Lemma}{0}
\begin{Lemma}
Let $M$ be a multiset of edges of $G$ such that every member of $\C$ lies on two edges of $M$ and every other vertex lies on a single edge of $M$. Then we can write $M$ uniquely as a disjoint union
$$M=\gamma_1 \sqcup \gamma_2 \sqcup \bigsqcup_{\q \in X} M_{\q}$$
where
\begin{enumerate}
\item Either $\gamma_1$ is a northern join and $\gamma_2$ is a southern join, or $\gamma_1$ is a eastern join and $\gamma_2$ is a western join.
\item $M_{\C}$ is a disjoint union of cycles, entirely contained in $\C$. (We count a doubled edge as a cycle of length 2.)
\item $M_{\q}$ is a disjoint union of paths entirely contained in $\q$ for $\q \in X$, $\q \neq X$.
\end{enumerate}
\end{Lemma}
\begin{proof}
Uniqueness is obvious; we prove existence.
Since every vertex is adjacent to either one or two elements of $M$, $M$ can be written uniquely as a disjoint union of cycles and paths. Moreover, the vertices of $\C$ are on cycles or are inner vertices of paths and the vertices of $V(G) \setminus \C$ are the ends of paths. For $\q \in X$, let $M_{\q}$ be the set of connected components of $M$ lying completely in $\q$. As $M_{\C}$ borders every vertex twice or not at all, it is a disjoint union of cycles. Similarly, the other $M_{\q}$ are disjoint unions of edges. Let $\Delta$ be the remaining edges.
Let $\q \in X$, $\q \neq \C$. We claim $\Delta \cap \q \subseteq \partial(\q)$. This is because if $v \in \q \setminus \partial(\q)$, then there is a single edge $vw$ of $M$ containing $v$. We have $w \in \q$ by the definition of $\partial(\q)$. Then $vw$ is also the only edge containing $w$ and thus $vw$ is a connected component of $M$ lying entirely in $\q$. So $v \in M_{\q}$ and $\q \not\in \Delta$.
We know $M_{\NE}$ borders equally many black as white vertices as it is a disjoint union of edges. Thus $\Delta \cap \NE$ has one more black vertex than white, as we assumed $\delta(\NE)=1$. However, we just showed $\Delta \cap \NE \subseteq \partial(\NE)$, and $\partial(\NE)$ is entirely black. So there is a unique vertex $v_{\NE}$ in $\Delta \cap \NE$. Similarly, there are unique vertices $v_{\NW}$, $v_{\SE}$ and $v_{\SW}$, with $v_{\NE}$ and $v_{\SW}$ black and $v_{\NW}$ and $v_{\SE}$ white. Also by the same logic, $\#(\Delta \cap \q)$ is even for $\q \in \{\C, \NE, \NW, \SE, \SW \}$.
Now, the $v_{\q}$ must be endpoints of paths. The \emph{a priori} possible paths are
\begin{enumerate}
\item A path from $v_{\NE}$ to $v_{\NW}$ through $\C$, and the three other rotations of this.
\item A path from $v_{\NE}$ to $v_{\SW}$ or from $v_{\NW}$ to $v_{\SE}$ through $C$.
\item A single edge from $v_{\NE}$ to $v_{\NW}$, and the three other rotations of this.
\item A single edge from $v_{\NE}$ to $N$, and the seven other rotations and reflections of this.
\end{enumerate}
As $\#(\Delta \cap \N)=\#(\Delta \cap \partial(N))$ is even, there must either be 0 or 2 paths of type (4) ending in $\N$, and similarly for $\E$, $\S$ and $\W$. This means we can \emph{not} have a path joining $v_{\NE}$ to $v_{\SW}$. If such a path existed, $v_{\NW}$ could not be joined to $N$ or $W$, as that would create one path ending in that set. Also, $v_{\NW}$ could not be joined to $v_{\SE}$, as the paths $v_{\NE} v_{\SW}$ and $v_{\NW} v_{\SE}$ would cross. Similarly, we may not have a path joining $v_{\NW}$ to $v_{\SE}$.
It is now easy to see that $\Delta$ must decompose either as the union of a northern and a southern join or as the union of an eastern and a western join.
\end{proof}
Note that, if a $\gamma_i$ ($i=1$ or $2$) passes through $\C$, it will contain an odd number of edges, as its endpoints are of opposite color.
We first establish the result with all the face variables set equal to $0$. Then each side of the equation is a sum of products of edge variables, and each product corresponds to an $M$ meeting the conditions of the lemma; we will abuse notation and call this product $M$ as well. We will show each $M$ occurs with the same coefficient on both sides. Let $k$ denote the number of cycles in $M_{\C}$ of length greater than 2. We claim that $m(G) m(\C)$ contains $M$ with coefficient $2^k$. If $\gamma_1$ is a northern join and $\gamma_2$ a southern join, we claim that $m(\N \cup \NE \cup \NW \cup \C) m(\S \cup \SE \cup \SW \cup C) m(\E) m(\W)$ contains $M$ with a coefficient of $2^k$ and $m(\E \cup \NE \cup \SE \cup \C) m(\W \cup \NW \cup \SW \cup C) m(\N) m(\S)$ does not contain $M$. If $\gamma_1$ is an eastern and $\gamma_2$ a western join we claim the reverse holds.
Consider first the task of determining how many times $M$ appears in $m(G) m(\C)$. This is the same as the number of ways to decompose $M$ as
$$M=M(G) \sqcup M(\C)$$
with $M(G)$ and $M(C)$ matchings of $G$ and $\C$ respectively. (Note that $M(\C)$ is \emph{not} the same as $M_{\C}$.) Clearly, the edges with endpoints outside $\C$ must lie in $M(G)$. This means all the edges of $M_{\q}$, $\q \neq \C$, the edges of $\gamma_i$ if $\gamma_i$ does not pass through $\C$ and the final edges of $\gamma_i$ if $\gamma_i$ does pass through $\C$. This forces the allocation of all the edges of $\gamma_i$ even in the case where $\gamma_i$ passes through $\C$. This is because when two edges of $M$ share a vertex, one edge must go in $M(G)$ and one in $M(\C)$. This forcing is consistent because $\gamma_i$ has an odd number of edges and the end edges must both lie in $M(G)$. Finally, we must allocate the edges of $M_{\C}$. All the cycles of $M_{\C}$ are of even length as $G$ is bipartite. In a cycle of length greater than 2, we may arbitrarily choose which half of its edges came from $M(G)$ and which from $M(C)$. This is $2^k$ choices.
Next, consider the coefficient of $M$ in $m(\N \cup \NE \cup \NW \cup \C) m(\S \cup \SE \cup \SW \cup C) m(\E) m(\W)$. We must similarly write
$$M=M(\N \cup \NE \cup \NW \cup \C) \sqcup M(\S \cup \SE \cup \SW \cup C) \sqcup M(\E) \sqcup M(\W).$$
We claim that if $\gamma_1$ is an eastern join and $\gamma_2$ a western, this coefficient is 0. There are three cases.
\setcounter{Case}{0}
\begin{Case}
$\gamma_1$ is a path joining $\NE$ to $\SE$ through $\C$.
\end{Case}
Then every edge of $\gamma_1$ must lie in $M(\N \cup \NE \cup \NW \cup \C)$ or in $M(\S \cup \SE \cup \SW \cup C) \sqcup M(\E)$ and which of these two it lies in must alternate. There are an odd number of edges in $\gamma_1$, so the final edges must lie in the same on of these two sets. But any edge with an endpoint in $\NE$ must lie in $M(\N \cup \NE \cup \NW \cup \C)$ and any edge with an endpoint in $\SE$ must lie in $M(\S \cup \SE \cup \SW \cup C) \sqcup M(\E)$. \cont.
\begin{Case}
$\gamma_1$ is a single edge with endpoints in $\NE$ and $\SE$. But none of the $M(\q)$'s can contain such an edge. \cont
\end{Case}
\begin{Case}
$\gamma_1$ is a union of two disjoint edges, one connecting $\NE$ to $\E$ and one connecting $\SE$ to $\E$.
\end{Case}
But neither of these edge types can lie in any of the four $M(\q)$'s. \cont
We now claim that if $\gamma_1$ is a northern join and $\gamma_2$ a southern join that $M$ has coefficient $2^k$. As before, the edges of $M_{\q}$, $\q \in X$, $\q \neq \C$ are uniquely allocated to one of $M(\N \cup \NE \cup \NW \cup \C)$, $M(\S \cup \SE \cup \SW \cup C)$, $M(\E)$ and $M(\W)$. If $\gamma_i$ does not pass through $\C$, its edges are also immediately forced. If $\gamma_i$ does pass through $\C$, its final edges are forced, thus forcing the others and again we have consistency as the two final edges are in the same set and $\gamma_i$ has an odd number of edges. Finally, each cycle of $M_{\C}$ can be allocated in two ways.
The case of $m(\E \cup \NE \cup \SE \cup \C) m(\W \cup \NW \cup \SW \cup C) m(\N) m(\S)$ is exactly analogous. We have now proven the theorem with the face variables set to 1 and continue to remove as much of this condition as possible.
We first note a general principle:
\begin{Lemma} \label{FaceExp}
Let $G$ be a \gwof and $G_1$, $G_2$, \dots $G_n$ be various sub-\gwofs. Let $M_i$ be a matching of $G_i$ for $1 \leq i \leq n$ and let $M$ be the multiset of edges of $G$ obtained by combining all the $M_i$. Let $f$ be a face of $G$ and let $\epsilon_i$ be the exponent of $f$ in $m(M_i)$ and let $\epsilon=\sum \epsilon_i.$ Let $G'_i$ be another set of sub-\gwofs, $M'_i$ another set of matchings and so forth. Then, if we establish the result
$$M=M' \quad \Longrightarrow \quad \epsilon=\epsilon'$$
for the case $M=M'=\emptyset$ it will follow for every $M$ and $M'$.
\end{Lemma}
\begin{proof}
Let $F$ and $F_i$ be the number of edges of $M$ and $M_i$ respectively adjacent to $f$. We have $F=\sum F_i$. Let $f_i$ denote the number of edges of $G_i$ adjacent to $f$. Let $c_i$ be 1 if $f$ is a closed face of $G_i$ and if $f$ is an open face of $G_i$. Define primed versions of all of these quantities analogously.
We have
$$\epsilon=\sum \epsilon_i =\sum \left( \left\lceil \frac{(f_i-F_i)-F_i}{2} \right\rceil -c_i \right) =
\sum \left( \left\lceil \frac{f}{2} \right\rceil -F_i -c_i \right)=
\sum \left\lceil \frac{f}{2} \right\rceil - \sum c_i - F.$$
The two sums do not depend on $M$ and $M'$ at all and, if $M=M'$ then $F=F'$. So if the theorem holds with $F=F'=0$, it holds whenever $F=F'$ and hence whenever $M=M'$.
\end{proof}
Let $f$ be a face. Fix a term $M$ as above and continue the notations $M(\q)$ from the above proof. For $\q \in X$, let $f(\q)$ denote the number of vertices of $f$ lying in $\q$ (this is the same notation as before). Let $f$ also denote the number of vertices of $f$. When we say $f$ is open or closed without further commentary we mean as a face of $G$.
We will show in several cases that the exponent of $x_f$ in the terms with the product of edge variables $M$ is the same from every contribution. By Lemma~\ref{FaceExp}, we will just need to check this in the case where no edge of $f$ is used in any of the matchings. (We do not need to verify that such a matching is actually possible.)
\setcounter{Case}{0}
\begin{Case} All the vertices of $f$ lie in $\q$ for $\q \in X$, $\q \neq \C$.
\end{Case}
$x_f$ will appear from the contribution of precisely one factor $m(\q')$ in each product, either always as an open or always as a closed face. So the exponent of $f$ is either always $\lceil (f-1)/2 \rceil$ or always $\lceil f/2 \rceil-1$. (Remember, we are assuming that no edge of $f$ is used in any of the matchings $M(\q)$.) \qedsymbol
\begin{Case} All the vertices of $f$ lie in $\C$.
\end{Case}
$x_f$ will have a contribution from two factors $m(\q_1)$ and $m(\q_2)$ in every case and will either always be a closed face with $f$ edges or always an open face with $f-1$ edges. The exponent of $x_f$ is hence the same in every case. \qedsymbol
\begin{Case} The vertices of $f$ lie in two sets, $\q_1$ and $\q_2 \in X$, neither of which is $\C$, we have $f(\q_1)=f(\q_2)=1 \mod 2$ and $f$ is closed.
\end{Case}
$\q_1$ and $\q_2$ can WLOG be taken to be either $\NE$ and $\NW$ or $\NE$ and $\N$.
Sometimes $x_f$ appears with exponent
$$\lceil (f(\q_1)-1)/2 \rceil + \lceil (f(\q_2)-1)/2 \rceil=(f(\q_1)-f(q_2))/2-1$$
and sometimes with exponent
$$\lceil f/2 \rceil -1 = f/2-1.$$
These are equal. \qedsymbol
\begin{Case} The vertices of $f$ lie in two sets, $\q$ and $\C$.
\end{Case}
If $f$ is closed $x_f$ always appears with exponent $\lceil (f(\C)-1)/2 \rceil + \lceil f/2 \rceil -1$. If $f$ is open $x_f$ always appears with exponent $\lceil (f(\C)-1)/2 \rceil + \lceil (f-1)/2 \rceil $. \qedsymbol
\begin{Case} The vertices of $f$ lie in three sets $\q_1$, $\q_2$ and $\q_3$, none of which are $\C$, with $f(\q_1)=f(\q_2)=1 \mod 2$ and $f(\q_3)=0 \mod 2$. Moreover, $f$ is closed.
\end{Case}
Sometimes $x_f$ appears with exponent
$$\lceil f/2 \rceil -1=f/2-1$$
and sometimes with exponent
$$\lceil (f(\q_1)-1)/2 \rceil +\lceil (f(\q_2)-1)/2 \rceil + \lceil (f(\q_3)-1)/2 \rceil=
(f(\q_1)-1)/2+(f(\q_2)-1)/2+f(\q_3)/2.$$
These are equal. \qedsymbol
\begin{Case} The vertices of $f$ lie in $\q_1$, $\q_2$ and $\C$ with $f(\q_1)=f(\q_2)=1 \mod 2$ and $f(\C)=0 \mod 2$. Moreover, $f$ is closed.
\end{Case}
Sometimes $x_f$ appears with exponent
$$\lceil f/2 \rceil -1 + \lceil (f(\C)-1)/2 \rceil =f/2-1+f(\C)/2$$
and sometimes with exponent
$$\lceil (f(\q_1)+f(\C)-1)/2 \rceil +\lceil (f(\q_2)+f(\C)-1)/2 \rceil=
(f(\q_1)+f(\C)-1)/2+(f(\q_2)+f(\C)-1)/2.$$
These are equal. \qedsymbol
Recalling that $G$ is bipartite and hence every closed face of $G$ has an even number of vertices, we see that are the these cases permitted by the theorem.
\end{proof}
\subsection{The Decomposition of $G$}
Let $G$ be a graph arising from the method of crosses and wrenches for some $h$. The purpose of this section is to describe a decomposition of the vertices of $G$ into nine disjoint sets. In the next section, we will show these sets obey the hypotheses of the previous section. For simplicity, we assume at first that $(n-2,i,j) \not\in \II$.
Let $G$ be the graph corresponding to $f(n,i,j)$. We have $F^c(G)=\Copen \cap \II$. We will assign every member $(n',i',j)$ of $\Copen$ and hence every member of $F^c(G)$ one or more of the nine labels $\tC$, $\tN$, $\tE$, $\tS$, $\tW$, $\tNE$, $\tNW$, $\tSE$, $\tSW$. The following table should be read as follows: if a face $f$ lies in all the indicated columns, then $f$ receives the indicated label.
$$\begin{matrix}
\Copen(n-1,i-1,j) & \Copen(n-1,i+1,j) & \Copen(n-1,i,j-1) & \Copen(n-1,i,j+1) & \Copen(n-2,i,j) & \mathrm{Label} \\
\in & \in & \in & \in & \in & \tC \\
& \in & & \in & & \tNE \\
\in & & & \in & & \tNW \\
& \in & \in & & & \tSE \\
\in & & \in & & & \tSW \\
& & & \in & & \tN \\
& & \in & & & \tS \\
& \in & & & & \tE \\
\in & & & & & \tW
\end{matrix}$$
The cases cover all situations except $(n',i',j)=(n-2,i,j)$, which we are currently assuming doesn't occur.
\textbf{The Rule for Allocating Vertices:} Define a vertex to lie in $\C$ if it is a vertex of a face in $\tC$. Define a vertex to lie in $\NE$ if it is a vertex of a face of $\tNE$ and not of a face of $\tC$; define $\NW$, $\SE$ and $\SW$ similarly. Define a vertex to lie in $\N$ if it is only adjacent to faces in $\tN$ and similarly for $\E$, $\W$ and $\S$. One can again check that these cases are exclusive. Note that $\tN \neq F(g(\N))$ and similarly for other $\q$, though they do live in roughly the same region of the graph.
We can restate this as follows. Let $f=(n',i',j')$.
\begin{eqnarray*}
f \in \tNE & \iff & n+i+j=n'+i'+j'+2,\ i'>i,\ j'>j \\
f \in \tNW & \iff & n-i+j=n'-i'+j'+2,\ i'*j \\
f \in \tSE & \iff & n+i-j=n'+i'-j'+2,\ i'>i,\ j'*