\documentclass[12pt]{article}
\newcommand{\sign}{{\rm sign}}
\newcommand{\bo}{{\bf 1}}
\newcommand{\Z}{{\bf Z}}
%\pagestyle{empty}
\begin{document}
\begin{center}
Math 192r, Problem Set \#19: Solutions 
\end{center}
\medskip

\begin{enumerate}

\item
{\it 
In problem \#3 of assignment \#17, multivariate polynomials
$$D(x_1,x_3,\dots,x_{2n+1};y_2,y_4,\dots,y_{2n})$$ 
were defined.
Find an infinite acyclic directed graph
with special vertices $\dots,v_{-1},v_0,v_1,\dots$
where all edges are assigned weight 1
and vertices are assigned weights
according to some scheme that you must devise,
so that for all integers $i \leq j$ 
the sum of the weights of the paths from $v_i$ to $v_j$ is
$D(x_{2i+1},x_{2i+3},\dots,x_{2j+1};y_{2i+2},y_{2i+4},\dots,y_{2j})$. 
Include a proof that your answer is correct.}

We can build a model of our directed graph in ${\bf Z}^2$.
Our vertices will be pairs $(i,j)$ with $i-j$ equal to 0, 1, 2, or 3,
and there will be a directed edge from vertex $(i,j)$ to vertex $(i',j')$
if and only if $(i'-i,j'-j)=$ $(1,0)$ or $(0,1)$.
The special vertices are $v_i=(i,i)$.
The weight of vertex $(i,j)$ is 
$x_{i+j}$ if $i-j=0$,
$y_{i+j}/x_{i+j-1}x_{i+j+1}$ if $i-j=1$,
$x_{i+j}/y_{i+j-1}y_{i+j+1}$ if $i-j=2$, and
$y_{i+j}$ if $i-j=3$.
Let $W_{i,j}$ be the sum of the weights of the paths from $v_i$ to $v_j$.
It is easy to check that $W_{i,i} = x_{2i}$ and $W_{i,i+1} = y_{2i+1}$
as required.
To prove that 
$W_{i,j} = D(x_{2i+1},\dots,x_{2j+1};y_{2i+2},\dots,y_{2j})$
for all values of $i$ and $j$,
it suffices to verify that the numbers $W_{i,j}$
satisfy the diamond recurrence.
That is, we must show that
$W_{i,j} W_{i+1,j-1} - W_{i+1,j} W_{i,j-1} = 1$.
By Lindstrom's lemma, this is equivalent to the assertion
that the signed sum of the weights of the 2-routings
from $\{v_i,v_{i+1}\}$ to $\{v_j,v_{j-1}\}$ is 1.
But we already know that there is a unique 2-routing of this kind,
connecting $v_i$ to $v_j$ and $v_{i+1}$ to $v_{j-1}$,
so it suffices to check that the weight of this 2-routing is 1.
To check this, note that
the product of the weights of $(i,i)$, $(i+1,i)$, $(i+1,i+1)$,
$(i+2,i)$, $(i+2,i+1)$, and $(i+2,i+2)$ is 
$(x_{2i})(y_{2i+1}/x_{2i}x_{2i+2})(x_{2i+2})
(x_{2i+2}/y_{2i+1}y_{2i+3})(y_{2i+3}/x_{2i+2}x_{2i+4})(x_{2i+4})=1$,
the product of the weights of
$(i+3,i)$, $(i+3,i+1)$, $(i+3,i+2)$, and $(i+3,i+3)$ is
$(y_{2i+3})(x_{2i+4}/y_{2i+3}y_{2i+5})
(y_{2i+5}/x_{2i+4}x_{2i+6})(x_{2i+6})=1$,
the product of the weights of
$(i+4,i+1)$, $(i+4,i+2)$, $(i+4,i+3)$, and $(i+4,i+4)$ is 1, etc.

\item
{\it Consider an infinite array with tilted upper boundary
like the one shown below:}
\[
\begin{array}{ccccccccccccccccc}
       &   &   &   &   &   &   &   &   &   &   &   &   &   &   &\vdots \\
       &   &   &   &   &   &   &   &   &   &   &   &   &   &x_5&    \\
       &   &   &   &   &   &   &   &   &   &   &x_4&   &w_5&   &y_5 \\
       &   &   &   &   &   &   &   &x_3&   &w_4&   &y_4&   & * &    \\
       &   &   &   &   &x_2&   &w_3&   &y_3&   & * &   & * &   & *  \\
       &   &x_1&   &w_2&   &y_2&   & * &   & * &   & * &   & * &    \\
       &w_1&   &y_1&   & * &   & * &   & * &   & * &   & * &   & *  \\
\vdots &   &   &   &   &   &   &   &   &   &   &   &   &   &   &\vdots 
\end{array}
\]
{\it Here the entries $w_i,x_i,y_i$ are formal indeterminates,
and the entries marked with asterisks are determined by the diamond rule
as in assignment \#17;
that is, whenever the array contains four entries arranged like}
$$\begin{array}{ccc}
  & a &    \\
b &   &  c \\
  & d &
\end{array}$$
{\it we must have $ad-bc=1$.
Some experimentation will probably convince you that
each entry in the table is
a Laurent polynomial in the variables $w_i,x_i,y_i$,
and that moreover each coefficient in this polynomial
equals $+1$.
Show how for each such Laurent polynomial,
the Laurent monomials that participate
correspond to the perfect matchings of some graph
(just as was the case in assignment \#17).
Give a concrete description of the graphs
and the correspondence between matchings and monomials
(including either a proof or convincingly large examples).}

Consider first what we get when we specialize
all the variables to equal 1:
\[
\begin{array}{ccccccccccccccccc}
       &   &   &   &   &   &   &   &   &   &   &   &   &   &   &\vdots \\
       &   &   &   &   &   &   &   &   &   &   &   &   &   & 1 &    \\
       &   &   &   &   &   &   &   &   &   &   &\bo&   & 1 &   & 1  \\
       &   &   &   &   &   &   &   & 1 &   & 1 &   & 1 &   & 2 &    \\
       &   &   &   &   &\bo&   & 1 &   & 1 &   & 2 &   & 3 &   & 7  \\
       &   & 1 &   & 1 &   & 1 &   & 2 &   & 3 &   & 7 &   &11 &    \\
       & 1 &   & 1 &   & 2 &   & 3 &   & 7 &   &11 &   &26 &   &41  \\
\vdots &   &   &   &   &   &   &   &   &   &   &   &   &   &   &\vdots 
\end{array}
\]
I claim that each of these entries counts the number of lattice paths
joining two points on the upper boundary of 1's,
where a lattice path may pass only through vertices 
that are marked with 1's, 2's, 3's, and 7's
(call these the ``single-digit locations'').
Specifically, given a location in the table,
trace a diagonal going northwest until you hit the boundary,
and call that location $i$;
likewise, trace a diagonal going northeast until you hit the boundary,
and call that location $j$.
Then I claim that the entry in question
is equal to the number (call it $N(i,j)$)
of paths from location $i$ to location $j$
consisting of northeast and southeast steps,
by way of single-digit locations.

For example, I claim that the 3 in the last row of the above excerpt
counts the lattice paths between the two boldface 1's
on the boundary.
To see why this is true,
take four entries that form a diamond,
and let the associated locations on the boundary
be $i,i',j',j$
(from left to right).
To get a proof by induction that 
the entries count lattice paths,
we need to verify that
$N(i,j)N(i',j')-N(i,j')N(i',j)=1$.
But (by Lindstrom's lemma) this is a consequent of the fact
that there is a unique 2-routing
that joins $\{i,i'\}$ with $\{j,j'\}$,
and that it connects $i$ with $j$ and $i'$ with $j'$.
(That's because the single-digit locations in any column
are precisely the top two locations in that column.)

We have now shown that the entries in the table count lattice paths.
But a lattice path is just a special case of a routing
(namely, a 1-routing),
so by using the routings-into-matchings trick
we can get a bijection between lattice paths in that graph
and perfect matchings of a certain graph.
For instance, consider the directed graph
\begin{verbatim}
                                     o 
                                   /
                         o       o 
                       /   \   /
             o       o       o 
           /   \   /   \   /
 o       o       o       o 
   \   /   \   /   \   /
     o       o       o 
       \   /   \   /
         o       o 
\end{verbatim}
The 11 lattice paths
joining the leftmost and rightmost vertices
in this directed graph
correspond to the 11 perfect matchings of the graph
\begin{verbatim}
                                    o
                                   /
                        o-o     o-o
                       /   \   /
            o-o     o-o     o-o
           /   \   /   \   /
  o     o-o     o-o     o-o
   \   /   \   /   \   /
    o-o     o-o     o-o
       \   /   \   /
        o-o     o-o
\end{verbatim}
which in turn correspond to the 11 perfect matchings of the graph
\begin{verbatim}
                        o-o
                       /   \
            o-o     o-o     o
           /   \   /   \   /
        o-o     o-o     o-o
       /   \   /   \   /
      o     o-o     o-o
       \   /   \   /
        o-o     o-o
\end{verbatim}

Now we may bring the variables $w_i,x_i,y_i$ back into the story.
If indeed the rational functions 
that are generated by the two-dimensional recurrence
are Laurent polynomials,
and if indeed each monomial contributing to these polynomials
has coefficient $+1$,
then we can say that the number of monomials
must go like 1, 1, 1, 2, 3, 7, 11, 26, 41, \dots,
and they should correspond to matchings of the above graph.

To see how the correspondence goes,
label the hexagonal cells as shown in the diagram
on the next page:

\pagebreak

\begin{verbatim}
                        o-o
                       /   \
            o-o     o-o x_3 o
           /   \   /   \   /
        o-o x_2 o-o w_3 o-o y_3
       /   \   /   \   /
      o w_2 o-o y_2 o-o   
       \   /   \   /
    y_1 o-o     o-o   
\end{verbatim}
(Note that we've added two extra ``ghost-cells'' at the ends.)
Given a matching $\mu$ of the graph (and its associated monomial)
and a cell $c$ in the graph (and its associated variable),
the exponent of the variable in the monomial
is equal to 2 minus the number of edges in $\mu$ adjacent to $c$,
unless $c$ is a ghost-cell,
in which case the exponent of the variable in the monomial
is equal to 1 minus the number of edges in $\mu$ adjacent to $c$.
For instance, the matching
\begin{verbatim}
                        o-o   
                             
            o-o     o-o x_3 o
                           /
        o o x_2 o o w_3 o o y_3
       /   \   /   \   /
      o w_2 o o y_2 o o   
                    
    y_1 o-o     o-o   
\end{verbatim}
corresponds to the monomial
$$y_1^{1-0} w_2^{2-3} x_2^{2-3} y_2^{2-3} w_3^{2-3} x_3^{2-2} y_3^{1-1}
= \frac{y_1}{w_2 x_2 y_2 w_3}.$$
\end{enumerate}

\end{document}
