\documentclass[12pt]{article}
\usepackage{amsmath,amsfonts,amssymb,colordvi}

\textheight=22cm \topmargin=-1cm

%%%%%%%%%format of begin %%%%%%%%

\def\qed{\nopagebreak\hfill{\rule{4pt}{7pt}}}
\def\proof{\noindent {\it{Proof.} \hskip 2pt}}
\def\dis{\displaystyle}
\def\Remark{\noindent{\textbf Remark}}

\def\Bfe{\rule{1pt}{10pt}}%{\mathbf{\|}}
\def\leftb{\Blue{\textbf{\large{[}}}}
\def\rightb{\Blue{\textbf{\large{]}}}}

\def\A{{\mathbb A}}
\def\B{{\mathbb B}}
\def\C{{\mathbb C}}
\def\N{{\mathbb N}}
\def\L{{\mathbb L}}
%\def\X{{\mathbb X}}
\def\Y{{\mathbb Y}}
\def\Z{{\mathbb Z}}
\def\K{{\mathbb K}}
\def\P{{\mathfrak P}}
\def\i{\textit}
\def\mfs{{\mathfrak S}}
\def\Sym{\mathfrak{Sym}}
\def\s{\scriptstyle }
\def\d{\partial}
\def\Kh{\widehat K}
\def\bp{\widehat{\pi}}
\def\moins{\raise 1pt\hbox{{$\scriptstyle -$}}}
\def\plus{\raise 1pt\hbox{{$\scriptstyle +$}} }

\newtheorem{theo}{Theorem}[section]
\newtheorem{deff}[theo]{Definition}
\newtheorem{lemm}[theo]{Lemma}
\newtheorem{prop}[theo]{Proposition}
\newtheorem{cor}[theo]{Corollary}

\newcommand{\newsection}[1]{\section{#1} \setcounter{equation}{0}}

\renewcommand{\theequation}{\arabic{section}.\arabic{equation}}
\renewcommand{\thesection}{\arabic{section}.}
\renewcommand{\thetheo}{\arabic{section}.\arabic{theo}}
\renewcommand{\thefigure}{\arabic{section}.\arabic{figure}}
\makeatletter \@addtoreset{figure}{section} \makeatother
\makeatletter
\long\def\@makecaption#1#2{%
   \vskip 10\p@
   \setbox\@tempboxa\hbox{{#1}\ \ #2}%
   \ifdim \wd\@tempboxa >\hsize
       {#1}\ \ #2\par
   \else
       \hbox to\hsize{\hfil\box\@tempboxa\hfil}%
   \fi}
\makeatother

\parskip=8pt

\begin{document}

\begin{center}
{\Large \bf {Lattice graphs and Schubert polynomials} }
\end{center}
\centerline{Alain Lascoux, Hui Lin and Arthur L. B. Yang}

\vspace{0.3cm} \noindent{\bf Abstract.} We define new planar
combinatorial objects that we call lattice graphs. We generalize
divided differences into operators, still satisfying braid
relations, and operating on the space of lattice graphs. This
allows us to interpret Schubert polynomials as sums of lattice
graphs. By putting appropriate weights on lattice graphs, we
recover the usual Schubert polynomials in two sets of variables.

\noindent {\bf Keywords:} divided differences, Schubert
polynomials, lattice graphs


\section{Introduction}\label{introduction}

Schubert polynomials, defined in
\cite{Lascoux1,Lascoux2,Lascoux3}, were motivated by the geometry
of flag manifolds, following the work of Bernstein-Gelfand-Gelfand
\cite{Bernstein} and Demazure \cite{Demazure}. They have been
extensively studied by many authors \cite{Nantel1, Billey 1993,
CLL, Fomin 1991, Fomin 1993, Kohnert 1990, KohnertAC, Lenart, RS,
RSk, Winkel 1999}. More details can be found in \cite{cbmsnote,
Macdonald 1991}.

Let $v=[v_1,v_2,\dots,v_n]$ be a permutation in the symmetric
group $\mfs_n$ on $n$ elements $\{1,2,\ldots,n\}$. Let $s_i$
denote the simple transposition that interchanges $i,\,i+1$. It is
well known that $s_1,s_2,\dots,s_{n-1}$ generate $\mfs_n$, and
satisfy the braid relations
\begin{eqnarray}\label{braid}
s_i s_j & = & s_j s_i\quad for\ |i-j|>1,\\
s_is_{i+1}s_i & = & s_{i+1}s_is_{i+1}.
\end{eqnarray}
together with $s_i^2=1$.
For $v \in \mfs_n$, for $i=1,\ldots,n$, let
$c_i(v) = \#\{j:\ i<j \ and \ v_i
> v_j\}$. Then $c(v)=[c_1(v),c_2(v),\ldots,c_n(v)]$ is called the
\emph{code} of $v$, and $\ell(v)=\sum_{i=1}^n c_i(v)$ is the
\emph{length} of $v$, i.e., the number of inversions of $v$. A
decomposition $v = s_{r_1}s_{r_2}\cdots s_{r_p}$ is \emph{reduced}
iff $p = \ell(v)$. We rather use the \emph{reduced word}
$r_1r_2\cdots r_p$. Let $R(v)$ denote the set of all reduced words
of a permutation $v$. The maximal permutation $v_0$ of $\mfs_n$ is
$[n,n-1,\dots,1]$. One may check that
$$(s_{n-1}\cdots s_1)(s_{n-1}\cdots s_2)\cdots(s_{n-1}s_{n-2})(s_{n-1})$$ is a reduced decomposition of
$v_0$ (we add parentheses in order to distinguish canonical
factors). The following lemma is straightforward:

\begin{lemm}
Given a permutation $v\in \mfs_n$, let $c=[c_1,c_2,\dots,c_{n}]$
be its code, then the concatenation of right factors of the
factors of
$$(s_{n-1}\cdots s_1)(s_{n-1}\cdots s_2)\cdots(s_{n-1})(\ ) \, ,$$
of respective lengths $c_1, c_2, \dots, c_n$,  is a reduced
decomposition of $v$.
\end{lemm}

For example, $v = [3,1,6,2,5,4]$ has code $c(v) = [2,0,3,0,1,0]$,
and the above decomposition is $v = (s_2s_1)(\ )(s_5s_4s_3)(\
)(s_5)(\ )$.

Let $\Z[a_1,a_2,\dots,a_n]$ denote the ring of polynomials in $n$
commutative variables with coefficients in $\Z$. For any $1
\leqslant i \leqslant n-1$, the \emph{simple divided
difference} $\d_i$ is the operator:
$$\d_i f(a_1,a_2,\dots,a_n) = \frac{f(\dots,a_i,a_{i+1},\dots)
-f(\dots,a_{i+1},a_i,\dots)}{a_i-a_{i+1}}=\frac{f-f^{s_i}}{a_i-a_{i+1}}.$$
Divided differences satisfy the braid relations
\begin{eqnarray}
\d_i \d_j & = & \d_j \d_i\quad for\ |i-j|>1,\label{d-braid}\\
\d_i\d_{i+1}\d_i & = & \d_{i+1}\d_i\d_{i+1}.
\end{eqnarray}
together with $\d_i^2 = 0$. Thanks to these relations, one can
define $\d_v$ by taking any reduced word $r_1r_2 \cdots r_p$ and
putting $\d_v  = \d_{r_1}\d_{r_2}\cdots\d_{r_p}$. When
$r_1r_2\cdots r_p$ is not reduced,  then
$\d_{r_1}\d_{r_2}\cdots\d_{r_p}=0$. We do not follow the
conventions of Lascoux-Sch$\rm{\ddot{u}}$tzenberger and write
divided differences or permutations on the left of the operand.

Divided differences satisfy Leibnitz formulas, as easily seen from
the definition:
\begin{equation}\label{Leibnitz}
\d_i(fg) = (\d_if)g + f^{s_i}(\d_ig) = (\d_ig)f + g^{s_i}(\d_if),
\end{equation}
where $f$ and $g$ are polynomials. In particular, symmetric functions in $x_i,\
x_{i+1}$ are scalars for $\d_i$, i.e.
$$g=g^{s_i} \Longrightarrow \d_i(fg) = g(\d_if).$$

Schubert polynomials in two sets of commutative variables $\A$ and
$\B$ have been defined in \cite{Lascoux2}, starting from a top
element $X_{v_0}(\A,\B)$, and using the action of the symmetry
group $\mfs_n$ on $\A$ only.

\begin{deff}\label{DoubleDef}
$$\left\{ \begin{array}{ll}X_{v_0}(\A,\B)\ =&\prod_{1\leqslant i,j\leqslant n,\ i+j\leqslant n}(a_i-b_j) \\
                           X_{v}(\A,\B) \ =&\d_{v^{-1}v_0}X_{v_0}(\A,\B) \end{array}\right.$$
\end{deff}

The preceding definition implies the recursion

\begin{equation}\label{doublerecursion}
\d_i X_v(\A,\B)  = X_{vs_i}(\A,\B), \quad if\ v_i > v_{i+1}.
\end{equation}

We also need the definition of compatible sequences \cite{Billey
1993}:
\begin{deff} For any sequence $\mathbf{r}=(r_1\ldots r_p)$,
 a $p$-tuple
$\mathbf{cp}=(cp_1,\dots,cp_p)$ of
positive integers is $\mathbf{r}$-compatible if
\begin{eqnarray*}
& cp_1 \leqslant cp_2 \leqslant  \dots \leqslant cp_p,\\
& cp_j \leqslant r_j,\ and \ if\  r_j < r_{j+1},\, then\, cp_j < cp_{j+1}, \\
& \ for \ any\ j:1\leqslant j\leqslant p.
\end{eqnarray*}
\end{deff}

\section{Lattice Graphs}

\begin{deff}\label{latticedef}
A \emph{lattice graph} is a collection of length $1$ vertical
edges in the $\mathbb{N} \times \mathbb{N}$ lattice. The edge from
$(i,j)$ to $(i,j+1)$ is denoted $[i,j]$(we use the South-East
quadrant). Beware that, for us, $i=1,2,\ldots$ is the column index
and $j$ is the row index; the origin is $(1,1)$.
\end{deff}

\begin{figure}[h,t]
\setlength{\unitlength}{0.7pt}
\begin{center}
\raisebox{1cm}{
\begin{picture}(220,160)
\multiput(20,-30)(30,0){5}{\circle*{3}}
\multiput(20,0)(30,0){5}{\circle*{3}}
\multiput(20,30)(30,0){5}{\circle*{3}}
\multiput(20,60)(30,0){5}{\circle*{3}}
\multiput(20,90)(30,0){5}{\circle*{3}}
\multiput(20,120)(30,0){5}{\circle*{3}}
\multiput(20,150)(30,0){5}{\circle*{3}}

\put(20,90){\line(0,1){60}} \put(25,103){\tiny{[1,2]}}
\put(24.5,133){\tiny{[1,1]}} \put(50,0){\line(0,1){60}}
\put(55,13){\tiny{[2,5]}} \put(55,43){\tiny{[2,4]}}
\put(80,60){\line(0,1){30}}\put(85,73){\tiny{[3,3]}}
\put(110,0){\line(0,1){30}}\put(115,13){\tiny{[4,5]}}

\end{picture}
}
\end{center}
\caption{A lattice graph restricting $\mathbb{N} \times
\mathbb{N}$ to a domain where all edges appear.}\label{Figure-1}
\end{figure}

We shall also use three other equivalent representations of
lattice graphs.

The first one is a sequence of strictly decreasing words on $1, 2,
3, \ldots$ that we call \emph{column word}, by reading upwards the
columns from left to right, and replacing the edge $[i,j]$ by $j$.
Void columns must be written as $[\ ]$. Figure \ref{Figure-1}
gives $\leftb [2,1],[5,4],[3],[5],[\ ]\rightb $.
%If the underlying word obtained by erasing the brackets is a reduced
%decomposition of a permutation $v$, then D is called a lattice graph of $v$.

The second one is a word in commutative biletters $i^j$ (we say
\emph{biword}), replacing each edge $[i,j]$ by $(j-i+1)^i$. The
number $j-i+1$ is called \emph{label} of the edge $[i,j]$. Our
lattice graph, with edges $[1,1],[1,2],[2,4],[2,5],[3,3],[4,5]$
gives the biletters $1^1,2^1,3^2,4^2,1^3,2^4$. However, we shall
write biwords using the decreasing lexicographic order (ordering
first the labels, then the exponents) as a list of biletters.
Figure \ref{Figure-1} gives $[4^2,3^2,2^4,2^1,1^3,1^1]$.

The third one is a 0-1 matrix $A=(a_{ij})$, where $i,j \in
\mathbb{N}$. $a_{ji}=1$ if edge $[i,j]$ belongs to lattice graph
otherwise $a_{ji}=0$. Figure \ref{Figure-1} gives a lower
triangular 0-1 matrix
\begin{equation}\label{matrix-01}
\begin{pmatrix}
1 & 0 & 0 & 0 & 0\\
1 & 0 & 0 & 0 & 0\\
0 & 0 & 1 & 0 & 0\\
0 & 1 & 0 & 0 & 0\\
0 & 1 & 0 & 1 & 0\\
0 & 0 & 0 & 0 & 0
\end{pmatrix}
\end{equation}

We shall label diagonals downwards, the 1-diagonal being the main
diagonal.

Given $s$, for any $k$ we say that two edges $[s,k]$ and
$[s+1,k+1]$ are $s$-paired. Paired edges lie in the same diagonal.

We shall define new operators on lattice graphs, that we still
call \emph{simple transpositions} (denoted by $\sigma$) and
\emph{divided differences} (denoted by $\d$) as follows
(formulating them in terms of biwords):
\begin{deff}
Given a biword $w=[w_1,w_2,\ldots,w_m]$, where
$w_1,w_2,\ldots,w_m$ are biletters, then its image under the
simple transposition $\sigma_r$ is
$$\sigma_r(w)=[w_1^{\sigma_r},w_2^{\sigma_r},\ldots,w_m^{\sigma_r}],$$
where for $w_s = (j-i+1)^i$, $$ w_s^{\sigma_r} = \left\{
\begin{array}{ll}
(j-i+1)^{r+1}, & \mbox{ if $i=r$}\\[5pt]
(j-i+1)^r, & \mbox{ if $i=r+1$}\\[5pt]
(j-i+1)^i, & \mbox{ otherwise}
\end{array}
\right.
$$
\end{deff}
From the above definition, we see that $\sigma_r$ acts only on
exponents.

Equivalently, $\sigma_r$ acts on a column word $\leftb\ldots, y^r,
y^{r+1}, \ldots\rightb$, where $y^r = [a_1, \ldots, a_m]$ and
$y^{r+1} = [b_1, \ldots, b_n]$, as follows:
$$\sigma_r\leftb\ldots, y^r, y^{r+1}, \ldots\rightb = \leftb\ldots, [b_1-1,\ldots,b_n-1], [a_1+1,\ldots,a_m+1], \ldots\rightb.$$

\begin{deff}\label{DivDef}
Given a biword lexicographic ordered $w = [w_1, w_2, \ldots,
w_m]$, then the action of the divided difference $\d_r$ on it is
\begin{equation}\label{eq-div}
\d_r(w) = \sum_{i=1}^{m}\epsilon_r(w_i)\,W_i,
\end{equation}
 where
$$\epsilon_r(w_i)=\left\{
\begin{array}{ll}
1, & \mbox{ if the exponent of $w_i$ is $r$}\\[5pt]
-1, & \mbox{ if the exponent of $w_i$ is $r+1$}\\[5pt]
0,  &\mbox{otherwise},
\end{array}
\right.$$ and $W_i=[w_1, \ldots, w_{i-1}, w_{i+1}^{\sigma_r},
\ldots, w_m^{\sigma_r}]$.
\end{deff}

Paired edges will give twice the same lattice graph with different
signs, so that we do not need to write them in summation
\eqref{eq-div}.

Figure \ref{Figure-2} shows an example of the action of $\d_2$ in
terms of lattice graphs, column words and biwords:
\begin{figure}[h,t]
\setlength{\unitlength}{0.6pt}
$$
\begin{array}{cccccccc}
\begin{picture}(80,120)
%\multiput(0,19)(20,0){4}{\circle*{3}}
\multiput(0,9)(30,0){3}{\circle*{3}} \multiput(0,29)(30,0){3}{\circle*{3}}
\multiput(0,49)(30,0){3}{\circle*{3}} \multiput(0,69)(30,0){3}{\circle*{3}}
\multiput(0,89)(30,0){3}{\circle*{3}} \multiput(0,109)(30,0){2}{\circle*{3}}
\multiput(0,129)(30,0){1}{\circle*{3}}

%\put(4,107){\tiny{3}}\put(4,127){\tiny{2}}
\put(34,17){\tiny{[2,6]}}\put(34,37){\tiny{[2,5]}}\put(34,77){\tiny{[2,3]}}
\put(64,57){\tiny{[3,4]}}\put(64,77){\tiny{[3,3]}}
%\put(64,67){\tiny{5}}

%\put(0,99){\line(0,1){40}}
\put(30,9){\line(0,1){40}} \put(30,69){\line(0,1){20}}
\put(60,49){\line(0,1){40}}
%\put(60,59){\line(0,1){20}}

\end{picture}
&\raisebox{1.3cm}{$\stackrel{\d_2}{\rightarrow}$}&
\raisebox{1.3cm}{$-$}  &
\begin{picture}(80,120)
%\multiput(0,19)(20,0){4}{\circle*{3}}
\multiput(0,9)(30,0){3}{\circle*{3}} \multiput(0,29)(30,0){3}{\circle*{3}}
\multiput(0,49)(30,0){3}{\circle*{3}} \multiput(0,69)(30,0){3}{\circle*{3}}
\multiput(0,89)(30,0){3}{\circle*{3}} \multiput(0,109)(30,0){2}{\circle*{3}}
\multiput(0,129)(30,0){1}{\circle*{3}}

%\put(4,107){\tiny{3}}\put(4,127){\tiny{2}}
\put(34,17){\tiny{[2,6]}}\put(34,37){\tiny{[2,5]}}\put(34,77){\tiny{[2,3]}}
\put(64,57){\tiny{[3,4]}}
%\put(64,67){\tiny{5}}

%\put(0,99){\line(0,1){40}}
\put(30,9){\line(0,1){40}} \put(30,69){\line(0,1){20}}
\put(60,49){\line(0,1){20}}
%\put(60,59){\line(0,1){20}}

\end{picture}
& \raisebox{1.3cm}{$+$} &
\begin{picture}(80,120)
%\multiput(0,19)(20,0){4}{\circle*{3}}
\multiput(0,9)(30,0){3}{\circle*{3}} \multiput(0,29)(30,0){3}{\circle*{3}}
\multiput(0,49)(30,0){3}{\circle*{3}} \multiput(0,69)(30,0){3}{\circle*{3}}
\multiput(0,89)(30,0){3}{\circle*{3}} \multiput(0,109)(30,0){2}{\circle*{3}}
\multiput(0,129)(30,0){1}{\circle*{3}}

%\put(4,107){\tiny{3}}\put(4,127){\tiny{2}}
\put(34,17){\tiny{[2,6]}}\put(34,77){\tiny{[2,3]}}\put(34,97){\tiny{[2,2]}}
\put(64,57){\tiny{[3,4]}}
%\put(64,67){\tiny{5}}

%\put(0,99){\line(0,1){40}}
\put(30,9){\line(0,1){20}} \put(30,69){\line(0,1){40}}
\put(60,49){\line(0,1){20}}
%\put(60,59){\line(0,1){20}}

\end{picture}
& \raisebox{1.3cm}{$+$} &
\begin{picture}(80,120)
%\multiput(0,19)(20,0){4}{\circle*{3}}
\multiput(0,9)(30,0){3}{\circle*{3}} \multiput(0,29)(30,0){3}{\circle*{3}}
\multiput(0,49)(30,0){3}{\circle*{3}} \multiput(0,69)(30,0){3}{\circle*{3}}
\multiput(0,89)(30,0){3}{\circle*{3}} \multiput(0,109)(30,0){2}{\circle*{3}}
\multiput(0,129)(30,0){1}{\circle*{3}}

%\put(4,107){\tiny{3}}\put(4,127){\tiny{2}}
\put(34,77){\tiny{[2,3]}} \put(34,97){\tiny{[2,2]}}
\put(64,57){\tiny{[3,4]}}\put(64,17){\tiny{[3,6]}}
%\put(64,67){\tiny{5}}

%\put(0,99){\line(0,1){40}}
\put(30,69){\line(0,1){40}} \put(60,9){\line(0,1){20}}
\put(60,49){\line(0,1){20}}
%\put(60,59){\line(0,1){20}}

\end{picture}\\
$\leftb[\ ],[6,5,3],[4,3]\rightb$
&\raisebox{0.0cm}{$\stackrel{\d_2}{\rightarrow}$}& - & $\leftb[\
],[6,5,3],[4]\rightb$& $+$ & $\leftb[\ ],[6,3,2],[4]\rightb$ &
$+$ & $\leftb[\ ],[3,2],[6,4]\rightb$  \\[7pt]
$[$5^2$,$4^2$,$2^3$,$2^2$,$1^3$]$
&\raisebox{0.0cm}{$\stackrel{\d_2}{\rightarrow}$}& - &
$[$5^2$,$4^2$,$2^3$,$2^2$]$ & $+$ & $[$5^2$,$2^3$,$2^2$,$1^2$]$ &
$+$ & $[$4^3$,$2^3$,$2^2$,$1^2$]$
\end{array}
$$
\caption{Action of a divided difference}\label{Figure-2}
\end{figure}

Given a 0-1 matrix, choosing a submatrix made of 2 consecutive
columns and a finite number of adjacent diagonals, we read the
diagonals downwards and thus obtain a word in letters
$\{00,01,10,11\}$. For example the first two columns and first
five diagonals of the above matrix \eqref{matrix-01} give the word
$10\ 10\ 01\ 01\ 00$.

In this representation, we define a \emph{R-move} to be a
transformation of the type
$$00\ 11\ \cdots \ 11\ 10\ \rightarrow\ 01\ 11\ \cdots\ 11\ 00,$$
with only occurrences of $11$ in the middle block. This is clearly
an invertible operation.

Notice that one R-move involves three main elements $i, \theta$
and $m$, where R-move acts on the $i$-th column and $(i+1)$-th
column, and shifts one edge in the $(\theta+m)$-diagonal to the
$\theta$-diagonal. We shall denote such a R-move by
$R_{i,\theta,m}$. Explicitly, given a lattice graph $D$ and $i,
\theta, m \geqslant 1$, if the word obtained by restricting $D$ to
$i, i+1$ columns and $\theta, \theta+1, \dots, \theta+m$ diagonals
is of type $00\ 11\ \cdots \ 11\ 10$, then R-move moves the edge
$[i,i+\theta+m-1]$ to $[i+1,\theta+i]$, it can be rewritten as
$$R_{i,\theta,m}(D)=D\cup\{[i+1,\theta+i]\}\setminus\{[i,i+\theta+m-1]\};$$
otherwise, we set $R_{i,\theta,m}(D)=D$.


\section{Braid Relations}\label{DBraid}
We will give some properties of transpositions and divided differences on
lattice graphs in this section.
%Suppose D is a lattice graph, and the column words of its $i$-th, $i+1$-th and
%$i+2$-th respectively are $y^i=[a_1,\ldots,a_{k1}],
%y^{i+1}=[b_1,\ldots,b_{k2}], y^{i+2}=[c_1,\ldots,c_{k3}]$, then
\begin{prop}\label{trans-braid}
The operators $\sigma$ satisfy the braid relations~:
\begin{eqnarray}
&&\sigma_i^2 = 1, \label{trans1}\\[5pt]
&&\sigma_i\sigma_j = \sigma_j\sigma_i, \ if\ |i-j|\neq 1  \label{trans2}\\[5pt]
&&\sigma_i\sigma_{i+1}\sigma_i = \sigma_{i+1}\sigma_i\sigma_{i+1}
\label{trans3}
\end{eqnarray}
\end{prop}
\proof It is easy to check the first two relations. As for the
third relation, the two operators
$\sigma_i,\ \sigma_{i+1}$ act only on the columns
$i$, $i+1$ and $i+2$ of the lattice graph. We can take $i=1$ and
restrict to lattice graphs with columns 1, 2, 3. Let
$$y^1=[a_1,\ldots,a_k],\  y^2=[b_1,\ldots,b_m],\
y^3=[c_1,\ldots,c_n].$$ We now compare $\sigma_1\sigma_2\sigma_1$
and $\sigma_2\sigma_1\sigma_2$:
\begin{eqnarray*}
\lefteqn{\sigma_1\sigma_2\sigma_1[y^1,y^2,y^3]} \hspace{0.5cm} \\
  &=&\sigma_1\sigma_2\leftb[b_1-1,\ldots,b_m-1],[a_1+1,\ldots,a_k+1],[c_1,\ldots,c_n]\rightb\\
  &=&\sigma_1\leftb[b_1-1,\ldots,b_m-1],[c_1-1,\ldots,c_n-1],[a_1+2,\ldots,a_k+2]\rightb\\
  &=&\leftb[c_1-2,\ldots,c_n-2],[b_1,\ldots,b_m],[a_1+2,\ldots,a_k+2]\rightb
\end{eqnarray*}
In the same way,
$$\sigma_2\sigma_1\sigma_2[y^1,y^2,y^3]=\leftb[c_1-2,\ldots,c_n-2],[b_1,\ldots,b_m],[a_1+2,\ldots,a_k+2]\rightb.$$
 Therefore we have $\sigma_1\sigma_2\sigma_1 = \sigma_2\sigma_1\sigma_2.$
\qed
\begin{prop}\label{div-braid}
\begin{eqnarray}
&&\d_i^2=0, \label{div1}\\[5pt]
&&\d_i\d_j = \d_j\d_i, \quad if\ |i-j|\neq 1 \label{div2}\\[5pt]
&&\d_i\d_{i+1}\d_i = \d_{i+1}\d_i\d_{i+1} \label{div3}
\end{eqnarray}
\end{prop}
\proof We can take $i=1$ as in Proposition \ref{trans-braid} and a
biword with three columns lexicographic ordered is $[w_1,
w_2,\ldots, w_m]$. We now check the first relation:
\begin{eqnarray*}
\lefteqn{\d_1^2([w_1, w_2, \ldots, w_m])
=\d_1\left(\sum_{h=1}^{m}\epsilon_1(w_h)[w_1,\ldots, w_{h-1}, w_{h+1}^{\sigma_1}, \ldots, w_m^{\sigma_1}]\right)} \\[5pt]
&=&
\sum_{h=1}^{m}\epsilon_1(w_h)\sum_{j>h}\epsilon_1(w_j^{\sigma_1})[w_1,\ldots,
w_{h-1}, w_{h+1}^{\sigma_1}, \ldots,w_{j-1}^{\sigma_1}, w_{j+1}^{\sigma_1^2},\ldots, w_m^{\sigma_1^2}]+\\[5pt]
&
&\sum_{h=1}^{m}\epsilon_1(w_h)\sum_{j<h}\epsilon_1(w_j)[w_1,\ldots,
w_{j-1}, w_{j+1}^{\sigma_1}, \ldots, w_{h-1}^{\sigma_1}, w_{h+1}^{\sigma_1^2},\ldots, w_m^{\sigma_1^2}]\\[5pt]
&=& 0.
\end{eqnarray*}

The second relation is immediate.

Let us now compute the image of the biword under $\d_1\d_2\d_1$:
\begin{eqnarray*}
\lefteqn{\d_1\d_2\d_1([w_1,\ldots,w_m]) = \d_1\d_2 \left(
\sum_{h=1}^{m}\epsilon_1(w_h)[w_1,\ldots,w_{h-1},w_{h+1}^{\sigma_1},\ldots
,w_{m}^{\sigma_1}] \right)} \\[5pt]
&=&\d_1 \left(
\sum_{h=1}^{m}\sum_{j<h}\epsilon_1(w_h)\epsilon_2(w_j)[w_1,\ldots,
w_{j-1},w_{j+1}^{\sigma_2},\ldots, w_{h-1}^{\sigma_2},
w_{h+1}^{\sigma_1\sigma_2},\ldots,
w_{m}^{\sigma_1\sigma_2}]\right)\\[5pt]
&+&\d_1 \left(
\sum_{h=1}^{m}\sum_{j>h}\epsilon_1(w_h)\epsilon_2(w_j^{\sigma_1})[w_1,\ldots,
w_{h-1}, w_{h+1}^{\sigma_1},\ldots, w_{j-1}^{\sigma_1},
w_{j+1}^{\sigma_1\sigma_2}, \ldots,
w_{m}^{\sigma_1\sigma_2}]\right).
\end{eqnarray*}
Using \eqref{trans1}, the sum decomposes into six summands:
\begin{eqnarray*}
M_1=
\lefteqn{\sum_{h=1}^m\sum_{j<h}\sum_{j<k<h}\epsilon_1(w_h)\epsilon_2(w_j)\epsilon_1(w_k^{\sigma_2})}
\hspace{1cm}\\[5pt]
&&\hspace{-2cm}[w_1, \ldots,w_{j-1}, w_{j+1}^{\sigma_2},\ldots,
w_{k-1}^{\sigma_2}, w_{k+1}^{\sigma_2\sigma_1},\ldots,
w_{h-1}^{\sigma_2\sigma_1},
w_{h+1}^{\sigma_1\sigma_2\sigma_1},\ldots,
w_m^{\sigma_1\sigma_2\sigma_1}], \end{eqnarray*}
\begin{eqnarray*}
M_2  =
\lefteqn{\sum_{h=1}^m\sum_{j<h}\sum_{j<h<k}\epsilon_1(w_h)\epsilon_2(w_j)\epsilon_1(w_k^{\sigma_1\sigma_2})}
\hspace{1cm}\\[5pt]
&&\hspace{-2cm}[w_1,\ldots,w_{j-1},w_{j+1}^{\sigma_2},\ldots,
w_{h-1}^{\sigma_2}, w_{h+1}^{\sigma_1\sigma_2},\ldots,
w_{k-1}^{\sigma_1\sigma_2},w_{k+1}^{\sigma_1\sigma_2\sigma_1},\ldots,
w_{m}^{\sigma_1\sigma_2\sigma_1}],\end{eqnarray*}
\begin{eqnarray*}
M_3  =
\lefteqn{\sum_{h=1}^m\sum_{j<h}\sum_{k<j<h}\epsilon_1(w_h)\epsilon_2(w_j)\epsilon_1(w_k)}
\hspace{1cm} \\[5pt]
&&\hspace{-2cm}[w_1, \ldots, w_{k-1}, w_{k+1}^{\sigma_1}, \ldots,
w_{j-1}^{\sigma_1}, w_{j+1}^{\sigma_2\sigma_1}, \ldots,
w_{h-1}^{\sigma_2\sigma_1}, w_{h+1}^{\sigma_1\sigma_2\sigma_1},
\ldots, w_{m}^{\sigma_1\sigma_2\sigma_1}],\end{eqnarray*}
\begin{eqnarray*}
M_4  =
\lefteqn{\sum_{h=1}^m\sum_{j>h}\sum_{k>j}\epsilon_1(w_h)\epsilon_2(w_j^{\sigma_1})\epsilon_1(w_k^{\sigma_1\sigma_2})}
\hspace{1cm} \\[5pt]
&&\hspace{-2cm}[w_1, \ldots, w_{h-1}, w_{h+1}^{\sigma_1}, \ldots,
w_{j-1}^{\sigma_1}, w_{j+1}^{\sigma_1\sigma_2}, \ldots,
w_{k-1}^{\sigma_1\sigma_2}, w_{k+1}^{\sigma_1\sigma_2\sigma_1},
\ldots, w_m^{\sigma_1\sigma_2\sigma_1}], \end{eqnarray*}
\begin{eqnarray*}
M_5 =
\lefteqn{\sum_{h=1}^m\sum_{j>h}\sum_{h<k<j}\epsilon_1(w_h)\epsilon_2(w_j^{\sigma_1})\epsilon_1(w_k^{\sigma_1})}
\hspace{1cm} \\[5pt]
&&\hspace{-2cm}[w_1, \ldots, w_{h-1}, w_{h+1}^{\sigma_1}, \ldots,
w_{k-1}^{\sigma_1}, w_{k+1}, \ldots, w_{j-1},
w_{j+1}^{\sigma_1\sigma_2\sigma_1}, \ldots,
w_{m}^{\sigma_1\sigma_2\sigma_1}],
\end{eqnarray*}
\begin{eqnarray*}
M_6 =
\lefteqn{\sum_{h=1}^m\sum_{j>h}\sum_{k<h}\epsilon_1(w_h)\epsilon_2(w_j^{\sigma_1})\epsilon_1(w_k)}
\hspace{1cm} \\[5pt]
&&\hspace{-2cm}[w_1, \ldots, w_{k-1}, w_{k+1}^{\sigma_1}, \ldots,
w_{h-1}^{\sigma_1}, w_{h+1}, \ldots, w_{j-1},
w_{j+1}^{\sigma_1\sigma_2\sigma_1}, \ldots,
w_{m}^{\sigma_1\sigma_2\sigma_1}].
\end{eqnarray*}
The image under $\d_2\d_1\d_2$  gives also a sum of six summands:
\begin{eqnarray*}
N_1=
\lefteqn{\sum_{h=1}^m\sum_{j>h}\sum_{k>j}\epsilon_2(w_h)\epsilon_1(w_j^{\sigma_2})\epsilon_2(w_k^{\sigma_2\sigma_1})}
\hspace{1cm}\\[5pt]
&&\hspace{-2cm}[w_1, \ldots,w_{h-1}, w_{h+1}^{\sigma_2},\ldots,
w_{j-1}^{\sigma_2}, w_{j+1}^{\sigma_2\sigma_1},\ldots,
w_{k-1}^{\sigma_2\sigma_1},
w_{k+1}^{\sigma_2\sigma_1\sigma_2},\ldots,
w_m^{\sigma_2\sigma_1\sigma_2}],
\end{eqnarray*}
\begin{eqnarray*}
N_2  =
\lefteqn{\sum_{h=1}^m\sum_{j<h}\sum_{k<j}\epsilon_2(w_h)\epsilon_1(w_j)\epsilon_2(w_k)}
\hspace{1cm}\\[5pt]
&&\hspace{-2cm}[w_1,\ldots,w_{k-1}, w_{k+1}^{\sigma_2},\ldots,
w_{j-1}^{\sigma_2}, w_{j+1}^{\sigma_1\sigma_2},\ldots,
w_{h-1}^{\sigma_1\sigma_2},
w_{h+1}^{\sigma_2\sigma_1\sigma_2},\ldots,
w_{m}^{\sigma_2\sigma_1\sigma_2}],
\end{eqnarray*}
\begin{eqnarray*}
 N_3  =
\lefteqn{\sum_{h=1}^m\sum_{j<h}\sum_{k>h}\epsilon_2(w_h)\epsilon_1(w_j)\epsilon_2(w_k^{\sigma_2\sigma_1})}
\hspace{1cm} \\[5pt]
&&\hspace{-2cm}[w_1, \ldots, w_{j-1}, w_{j+1}^{\sigma_1}, \ldots,
w_{h-1}^{\sigma_1}, w_{h+1}^{\sigma_2\sigma_1}, \ldots,
w_{k-1}^{\sigma_2\sigma_1}, w_{k+1}^{\sigma_2\sigma_1\sigma_2},
\ldots, w_{m}^{\sigma_2\sigma_1\sigma_2}],
\end{eqnarray*}
\begin{eqnarray*}
N_4  =
\lefteqn{\sum_{h=1}^m\sum_{j<h}\sum_{j<k<h}\epsilon_2(w_h)\epsilon_1(w_j)\epsilon_2(w_k^{\sigma_1})}
\hspace{1cm} \\[5pt]
&&\hspace{-2cm}[w_1, \ldots, w_{j-1}, w_{j+1}^{\sigma_1}, \ldots,
w_{k-1}^{\sigma_1}, w_{k+1}^{\sigma_1\sigma_2}, \ldots,
w_{h-1}^{\sigma_2\sigma_1}, w_{h+1}^{\sigma_2\sigma_1\sigma_2},
\ldots, w_{m}^{\sigma_2\sigma_1\sigma_2}],
\end{eqnarray*}
\begin{eqnarray*}
N_5 =
\lefteqn{\sum_{h=1}^m\sum_{j>h}\sum_{h<k<j}\epsilon_2(w_h)\epsilon_1(w_j^{\sigma_2})\epsilon_2(w_k^{\sigma_2})}
\hspace{1cm} \\[5pt]
&&\hspace{-2cm}[w_1, \ldots, w_{h-1}, w_{h+1}^{\sigma_2}, \ldots,
w_{k-1}^{\sigma_2}, w_{k+1}, \ldots, w_{j-1},
w_{j+1}^{\sigma_2\sigma_1\sigma_2}, \ldots,
w_{m}^{\sigma_2\sigma_1\sigma_2}],
\end{eqnarray*}
\begin{eqnarray*}
N_6 =
\lefteqn{\sum_{h=1}^m\sum_{j>h}\sum_{k<h}\epsilon_2(w_h)\epsilon_1(w_j^{\sigma_2})\epsilon_2(w_k)}
\hspace{1cm} \\[5pt]
&&\hspace{-2cm}[w_1, \ldots, w_{k-1}, w_{k+1}^{\sigma_2}, \ldots,
w_{h-1}^{\sigma_2}, w_{h+1}, \ldots, w_{j-1},
w_{j+1}^{\sigma_2\sigma_1\sigma_2}, \ldots,
w_{m}^{\sigma_2\sigma_1\sigma_2}].
\end{eqnarray*}

Thanks to \eqref{trans2} and
\begin{eqnarray*}
&&\epsilon_1(w^{\sigma_1\sigma_2})=\epsilon_2(w), \quad \epsilon_2(w^{\sigma_2\sigma_1})=\epsilon_1(w),\\
&&\epsilon_1(w^{\sigma_1}) = -\epsilon_1(w), \quad
\epsilon_2(w^{\sigma_2}) = -\epsilon_2(w),
\end{eqnarray*}
we get $M_k = N_k,\ for\ 1 \leqslant k \leqslant 4$ and
$M_5+M_6=0,\ N_5+N_6=0.$ Therefore $\d_1\d_2\d_1 = \d_2\d_1\d_2$.
\qed

Similar computations give the following relations of the same
type:
\begin{eqnarray}
&&\d_i\sigma_i + \sigma_i\d_i = 0, \label{div-trans}\\[5pt]
&&\d_i\sigma_{i+1}\sigma_i= \sigma_{i+1}\sigma_{i}\d_{i+1},\quad \d_{i+1}\sigma_i\sigma_{i+1}=\sigma_i\sigma_{i+1}\d_i \label{div2-1}\\[5pt]
&&\d_i\sigma_{i+1}\d_i = \d_{i+1}\d_i\sigma_{i+1}+\sigma_{i+1}\d_i\d_{i+1},\label{div2-2}\\
&&\d_{i+1}\sigma_i\d_{i+1} = \d_i\d_{i+1}\sigma_i +
\sigma_i\d_{i+1}\d_i. \label{div2-3}
\end{eqnarray}

These relations, together with Proposition \ref{trans-braid} and
\ref{div-braid}, allow to define a ``twisted action" of the
symmetric group, lifting the action on polynomials used by
Lascoux-Leclerc-Thibon \cite{LLT}.
\begin{prop}
Let $q\in \mathbb{C}$, for any $i$, define $T_i:\ \sigma_i+q\d_i$.
Then
\begin{eqnarray}
&&T_i^2  =  1\label{T-braid1},\\[5pt]
&&T_iT_j =  T_jT_i,  \quad if\ |i-j|\neq 1 \label{T-braid2}\\[5pt]
&&T_iT_{i+1}T_i = T_{i+1}T_iT_i\label{T-braid3}.
\end{eqnarray}
\end{prop}
\proof \eqref{T-braid1} is an immediate result of \eqref{trans1},
\eqref{div1} and \eqref{div-trans}.

\eqref{T-braid2} is evident owing to \eqref{trans2}, \eqref{div2}
and $\sigma_i\d_j = \d_j\sigma_i$.

\eqref{T-braid3} comes from \eqref{trans3}, \eqref{div3},
\eqref{div2-1}, \eqref{div2-2}, and \eqref{div2-3}.

\section{Schubert Polynomials and Lattice Graphs}\label{Schu}

In this section, we define Schubert polynomials in terms of
lattice graphs. Our definition is different from the combinatorial
description of Schubert polynomials in terms of tableaux
(\cite{Lascoux4}, \cite{RS}), of reduced decompositions
(\cite{Billey 1993}), of rc-graphs (\cite{Nantel1}), though
connected to the preceding descriptions.

Let $\mathcal{L}$  be the {$\mathbb{Z}$}-module with basis the
lattice graphs. Schubert polynomials $\L_v$, $v\in\mfs_n$, will
now be defined as elements of the space $\mathcal{L}$ as follows:

The top element $\L_{v_0}$ is the lattice graph corresponding to
the column word $\leftb[n-1, \ldots,2,1],\cdots, [n-1],[\
]\rightb$, and for any $v\in\mfs_n$,
\begin{equation}\label{Shcubert-def}
\L_v = \d_{v^{-1}v_0} \L_{v_0}.
\end{equation}

Given a lattice graph, whose edges $[i,j]$ are such that $i \leqslant j$, we
say that it is \emph{reduced} if the underlying word obtained by erasing the
brackets in the column word is reduced. Denote by $L^v$ the set of all the
lattice graphs which give a reduced decomposition of $v$.


\begin{lemm}\label{keepperm}
Given any permutation $v$, any reduced lattice graph
$\mathcal{D}\in L^v$, and $i,\theta,m\geqslant 1$, then
$R_{i,\theta,m}(\mathcal{D})\in L^{v}$.
\end{lemm}
\proof If $R_{i,\theta,m}(\mathcal{D})=\mathcal{D}$, the lemma
holds.

Otherwise,
$R_{i,\theta,m}(\mathcal{D})=\mathcal{D}\cup\{[i+1,\theta+i]\}\setminus\{[i,i+\theta+m-1]\}.$
Let $\eta=i+\theta+m$. Restricting $\mathcal{D}$ to $i,i+1$ two
columns and the diagonals between $\theta$-diagonal and
$(\theta+m)$-diagonal, the column word is
$$\leftb[\eta-1,\eta-2,\dots,\eta-m],[\eta-1,\eta-2,\dots,\eta-m+1]\rightb.$$

The corresponding column word for $R_{i,\theta,m}(\mathcal{D})$ is
$$\leftb[\eta-2,\eta-3,\dots,\eta-m],[\eta-1,\eta-2,\dots,\eta-m+1,\eta-m]\rightb.$$
It is straightforward, thanks to the braid relations
\eqref{braid}, that the underlying permutations are the same. \qed

Lemma \ref{keepperm} shows that R-moves , or their inverses,
preserve the underlying permutation.

\begin{theo}\label{main-1}For each permutation $v\in \mfs_n$, we have
\begin{equation}
\L_v= \sum_{\mathcal{D}\in L^v}\mathcal{D}.
\end{equation}
\end{theo}

\proof We use  decreasing induction on the
length of permutations. When $v=v_0$,
 $L^{v_0}$ contains only the
reduced lattice graph $D_0 = \hat{L}(v_0)=\L_{v_0}$ and the statement
is evident.


If $v \neq v_0,$ let $\pi=vs_r$ and $\ell(\pi)=\ell(v)+1$. We know
that $\L_{v} = \d_r\L_{\pi}$, and by induction , that Theorem
\ref{main-1} holds for $\L_{\pi}$.

Given any reduced lattice graph $D$ in $L^\pi$, we denote the
biword corresponding to the unpaired edges of $r$-th column and
$(r+1)$-th column by $[w_1, w_2, \ldots, w_n]$ (ignoring the other
edges). Let $D_i$ be the lattice graph which is obtained from $D$
by replacing $[w_1, w_2, \ldots, w_n]$ with $[w_1, \ldots,
w_{i-1}, w_{i+1}^{\sigma_r}, \ldots, w_n^{\sigma_r}]$.
\eqref{eq-div} can be rewritten in terms of lattice graphs as
\begin{equation}
\d_r D=\sum_{i=1}^{n} \epsilon_r(w_i)D_i.
\end{equation}

We shall also need the underlying set $\{\d_r D\}=\{D_i\}$.

We decompose $L^{\pi}$ into two sets $L_0^{\pi}$ and $L_1^{\pi}$
as follows:
\begin{equation}\label{eq-decomp}
L_0^{\pi}=\{D\in L^{\pi}: [r,r]\not \in D\},\quad L_1^{\pi} =
L^{\pi}-L_0^{\pi}.
\end{equation}

Given $D \in L_1^{\pi}$, let $f(r,D)$ be the minimal integer such
that $[r,f(r,D)]\in D$ and $[r,f(r,D)+1] \not\in D$. Let $t^D$ be
the maximal index such that all the labels of $w_{t^D}, \ldots,
w_n$ are smaller than,
 or equal to, $f(r,D)-r+1$.

\begin{lemm} With $L_1^{\pi},\,t^D$ and $D_i$ defined as above, we have
\begin{equation}
L^{v}= \bigcup_{D\in L_1^{\pi}}\bigcup_{i=t^D}^n D_i.
\end{equation}
\end{lemm}

\proof For $i: t^{D}\leqslant i\leqslant n$, it's clear that
$\epsilon_r(w_i)=1$, and that there exist $\alpha, \beta_1,
\ldots, \beta_s$ satisfying
$$
[w_i, w_{i+1}, \ldots, w_n] = \leftb[\alpha, \alpha-1, \ldots, r],
[\beta_s, \beta_{s-1}, \ldots, \beta_1]\rightb.
$$

The subword $[w_{i+1}^{\sigma_r}, w_{i+2}^{\sigma_r}, \ldots,
w_n^{\sigma_r}]$ must appear in $D_i$, and in terms of the
definition \ref{DivDef},
$$
[w_{i+1}^{\sigma_r}, w_{i+2}^{\sigma_r}, \ldots, w_n^{\sigma_r}] =
\leftb[\beta_s-1,\beta_{s-1}-1,\ldots, \beta_1-1], [\alpha,
\alpha-1, \ldots, r+1]\rightb.
$$

The braid relations \eqref{braid} entail
$$ [w_i, w_{i+1}, \ldots, w_n]\ s_r =
  [w_{i+1}^{\sigma_r}, w_{i+2}^{\sigma_r}, \ldots, w_n^{\sigma_r}] \ . $$
Therefore, $D_i\in L^v$.

On the other hand, for every lattice graph $D'\in L^v$, let
$h(r,D')$ be the minimal number such that neither $[r,h(r,D')]$
nor $[r+1,h(r,D')+1]$ belongs to $D'$. Among those edges with
labels less than $h(r,D')-r+1$, all the unpaired edges constitute
a set $\mathcal{E}$ which lie in column $r+1$. Otherwise it would
contradict the fact that $\ell({v\,s_r})=\ell({v})+1$. Given $D'$,
we define $D$ by replacing all the edges in $\mathcal{E}$ by their
images under $\sigma_r$, and adding a new edge $[r,h(r,D')]$.
Suppose that the biword corresponding to the unpaired edges of
$r$-th column and $r+1$-column in $D$ is $[w_1, w_2, \ldots,
w_n]$, and that the biletter corresponding to the edge
$[r,h(r,D')]$ is $w_{i'}$, then $D'=D_{i'}$. \qed

\begin{lemm}\label{vanish-la} Given $\pi,\,r$ and the
decomposition \eqref{eq-decomp} of $L^{\pi}$, let $D_i$ and $t^D$
be defined as above, then we have
\begin{eqnarray}
\sum_{D\in L_1^{\pi}}\sum_{i=1}^{t^D-1} \epsilon_r(w_i) D_i &=& 0,\label{1-invo}\\[5pt]
\d_r\sum_{D \in L_0^{\pi}}D &=& 0.\label{0-invo}
\end{eqnarray}
\end{lemm}
\proof We shall show that if a lattice graph appears in
\eqref{1-invo} or \eqref{0-invo}, then it appears  twice, with
different signs. Then we describe an involution which allows us to
eliminate these pairs.

Here we shall use 0-1 matrices instead of lattice graphs.
%Restricting a lattice graph to two adjacent columns, we read the
%successive diagonals downwards, and thus obtain a word in the
Denote by $\digamma$ the flip operation on a word in the alphabet
$\{00,01,10,11\}$ which exchanges 01 and 10, and fixes 00 and 11.
We define now a transformation $\Theta$ on words. Given any word
$w=xz_1z_2\cdots z_k y$, its image under $\Theta$ is
\begin{equation}
\Theta(w)=y^{\digamma}z_1^{\digamma}z_2^{\digamma}\cdots
z_k^{\digamma}x^{\digamma}.
\end{equation}
It is clear that $\Theta$ is an involution on words in the
alphabet $\{00,01,10,11\}$.

We shall consider only words of the type
\begin{equation}\label{type1}
\begin{array}{ccccccccccccc}
01 & 11 & \cdots & 11 & 01 & 11 & \cdots & 11 & 01 & 11 & \cdots &
11 & 00,
\end{array}
\end{equation}
where only $11$ and $01$ appears in the middle block, and their
images under $\Theta$
\begin{equation}\label{type2}
\begin{array}{ccccccccccccc}
00 & 11 & \cdots & 11 & 10 & 11 & \cdots & 11 & 10 & 11 & \cdots &
11 & 10
\end{array}.
\end{equation}

We apply the above involution to prove \eqref{1-invo}. Given $D\in
L_1^{\pi}$, we restrict $D$ to $r$ and $r+1$ columns. For $i, 1
\leqslant i\leqslant t^D-1$:

If $w_i$ corresponds to the edge $[r,\eta]$, its diagonal number
is $\eta-r+1$ and  word is $10$. By definition of $t^D$, we can
find upwards the first diagonal whose word is $00$. Let $\xi$ be
its label. Reading the successive columns from the $\xi$-diagonal
to the $(\eta-r+1)$-diagonal, we get a word $u$ which is of type
\eqref{type2}, because $01$ can't appear(otherwise $D$ is not
reduced). Then we apply $\Theta$ to $u$, and obtain a new lattice
graph $D'$. In fact, the action of $\Theta$ in that case is a
sequence of R-moves which changes $[r,\eta]$ to $[r+1,r+\xi]$, and
it doesn't change the edge $[r,r]$, so $D' \in L_1^{\pi}$. The
action of $\d_r$ on the edge $[r,\eta]$ of $D$ and on the edge
$[r+1,r+\xi]$ of $D'$ give the same lattice graph, but with
different signs.


Otherwise, $w_i$ corresponds to the edge $[r+1,\eta']$ which lies
in the $(\eta'-r)-$diagonal and the diagonal word is $01$. We can
find downwards the first diagonal whose word is $00$. Let $\xi'$
be its label. Reading the successive columns from the
$\xi'$-diagonal to the $(\eta'-r)$-diagonal, we get a word $u'$ of
type \eqref{type1}. By applying $\Theta$ in a similar manner, we
can find a pair of lattice graphs plus the corresponding edges,
and eliminate the two lattice graphs which appear in
\eqref{1-invo}.

Relation \eqref{0-invo} is also proven by using $\Theta$, which
allows us to eliminate lattice graphs by pairs. \qed

The following lemma is an immediate consequence of the above two:
\begin{lemm}
Given two permutations $\pi$ and $v$ such that $\pi=vs_r$ and
$\ell(\pi)=\ell(v)+1$, then
$$\d_r L^\pi = L^v.$$
\end{lemm}

Thus we finish the proof of Theorem \ref{main-1}.


We weight each edge $[i,j]$ in the lattice by $a_i-b_{j-i+1}$.
Take the weight of $D$ as the product of the weight of all edges
$[i,j]\in D$, denoted by $\omega(D)$. Then the action of divided
difference on lattice graphs is compatible with the action of
divided difference on monomials. The following theorem is
immediate:
\begin{theo}\label{mainthem} With the weight function $\omega$, for any permutation $v$ we have
\begin{equation}\label{main}
X_{v}(\A,\B) = \sum_{D\in L^v}\omega(D).
\end{equation}
\end{theo}

There is an obvious bijection between column words of lattice
graphs $L^v$ and $RC$-words of permutation $v$. From this
bijection one can deduce that:
\begin{theo}\label{doublerd}
\begin{equation}
X_{v}(\A,\B) = \sum_{\mathbf{r}\in R(v)}\sum_{\mathbf{cp}\in
C(\mathbf{r})}\prod_{j=1}^{p}(a_{cp_j}-b_{r_j-cp_j+1}).
\end{equation}
\end{theo}
The case of this theorem on the Schubert polynomials over one set
of variables has been studied by Bergeron-Billey \cite{Nantel1}
and Fomin-Stanley \cite{Fomin 1991}.

For the other combinatorial construction of Schubert polynomial,
we refer the reader to Lascoux-Sch$\rm{\ddot{u}}$tzenberger
\cite{Lascoux5}, Fomin-Kirillov \cite{Fomin 1993}, Kohnert
\cite{Kohnert 1990, KohnertAC}, Lenart \cite{Lenart}.

\section{Acknowledgements}
 This work was done under the auspices of the Key Laboratory of Pure Mathematics and Combinatorics of
 the Ministry of Education of China, and the 973 Project on Mathematical Mechanization of the Ministry
 of Science and Technology of China. We thank Professor Axel Kohnert in particular for providing some references.
 Special thanks are given to Professor William Y. C. Chen for his giving us a chance to study
 symmetric functions and Schubert polynomials.

\begin{thebibliography}{30}

   \bibitem{Nantel1} N. Bergeron and S. Billey, RC-graphs and Schubert polynomials, \i{Experimental
   Math.} \textbf{2} (1993), 257-269.

   \bibitem{Bernstein} I. N. Bernstein, I. M. Gelfand, and S. I. Gelfand, Schubert celles and cohomology
   of the spaces G/P, \i{Russian Math. Surveys} \textbf{28} (1973), 1-26.

   \bibitem{Billey 1993} S. Billey, W. Jockusch and R. Stanley, Some combinatorial properties of Schubert polynomials,
   \i{J. Alg. Comb.} \textbf{2} (1993), 345-374.

   \bibitem{CLL} W. Y. C. Chen, B. Li, and J. D. Louck, The flagged double Schur
   function, \textit{J. Alg. Combin.}, \textbf{15} (2002), 7-26.

   \bibitem{Demazure} M. Demazure, D$\acute{e}$singularisation des vari$\acute{e}$t$\acute{e}$s de Schubert
   g$\acute{e}$n$\acute{e}$ralis$\acute{e}$es, \i{Ann. Sci. $\acute{E}$cole Norm. Sup. (4)} \textbf{7} (1974), 53-58.

   \bibitem{Fomin 1991} S. Fomin and R. Stanley, Schubert polynomials and the NilCoxeter algebra, \i{Adv. Math.}
   \textbf{103} (1994), 196-207.

   \bibitem{Fomin 1993} S. Fomin and A. N. Kirillov, Yang-Baxter equation, symmetric functions, and Schubert
   polynomials, \i{Discrete Math.} \textbf{153} (1996), 123-143.

   \bibitem{Kohnert 1990} A. Kohnert, Weintrauben, Polynome, Tableaux, \i{Bayreuth. Math. Schrift.} \textbf{38} (1991), 1-97.

   \bibitem{KohnertAC} A. Kohnert, Multiplication of a Schubert polynomial by a Schur
   polynomial, \i{Ann. Comb.} \textbf{1} (1997), 367-375.

   \bibitem{Lascoux2} A. Lascoux, Classes de Chern des vari$\acute{e}$t$\acute{e}$s de drapeaux, \i{Comptes Rendus} \textbf{295} (1982), 393-398.

   \bibitem{cbmsnote} A.~Lascoux, Symmetric Functions and Combinatorial Operators on Polynomials, CBMS Regional Conference Series in Mathematics, 99,
    AMS, 2003.


   \bibitem{Lascoux1} A. Lascoux and M. P. Sch$\rm{\ddot{u}}$tzenberger, Polyn$\hat{o}$mes de Schubert, \i{C.R. Acad. Sci.
   Paris} \textbf{294} (1982), 447-450.

   \bibitem{Lascoux3} A. Lascoux and M. P. Sch$\rm{\ddot{u}}$tzenberger, Structure de Hopf de l'anneau de cohomologie
   et de l'anneau de Grothendieck d'une vari��t�� de drapeaux. \i{C.R. Acad. Sci.
   Paris} \textbf{295} (1982), 629-633.

   \bibitem{Lascoux4} A. Lascoux and M. P. Sch$\rm{\ddot{u}}$tzenberger,
   Tableaux and noncommutative Schubert polynomials, \i{Funct. Anal. Appl.} \textbf{23} (1989), 63-64.

   \bibitem{Lascoux5} A. Lascoux and M. P. Sch$\rm{\ddot{u}}$tzenberger,
   Fonctorialite des polynomes de Schubert, \i{Contermporary Mathematics}
   Volume \textbf{88}, (1989), 585-598.

   \bibitem{LLT} A. Lascoux, B. Leclerc and J.-Y. Thibon, Twisted action of the symmetric group on the cohomology of a flag manifold. Parameter spaces (Warsaw, 1994),
   111-124, Banach Center Publ., 36, Polish Acad. Sci., Warsaw, 1996.

   \bibitem{Lenart} C. Lenart, A unified approach to combinatorial formulas for Schubert polynomials,
   \i{J. Alg. Comb.}, to appear.

   \bibitem{Macdonald 1991} I. G. Macdonald, Notes on Schubert Polynomials, \i{Publications du LACIM 6},
   Universit$\acute{e}$ du Qu$\acute{e}$bec, $\grave{a}$ Montr$\acute{e}$al(1991).

   \bibitem{RS} V. Reiner and M. Shimozono, Plactification, \i{J. Alg.
   Combin.} \textbf{4} (1995), 331-351.

   \bibitem{RSk} V. Reiner and M. Shimozono, Key polynomials and a
   flagged Littlewood-Richardson rule, \i{J. Combin. Theory Ser.
   A} \textbf{70} (1995), 107-143.


   \bibitem{Winkel 1999} R. Winkel, Diagram rules for the generation of Schubert
   polynomials, \i{J. Combin. Theory Ser.
   A} \textbf{86} (1999), 14-48.

\end{thebibliography}

\end{document}
