\documentclass[12pt]{article}
\newcommand{\sign}{{\rm sign}}
\newcommand{\Z}{{\bf Z}}
%\pagestyle{empty}
\begin{document}
\begin{center}
Math 192r, Problem Set \#19 \\
(due 12/6/01)
\end{center}
\medskip

\begin{enumerate}

\item
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.

\item
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}
\]
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}$$
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).

\end{enumerate}

\end{document}
