\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}