\begin{document}

\newcommand{{\,|\,}}{{\,|\,}}		
\renewcommand{\mathfrak}{\mathfrak}		
\renewcommand{\mathbb}{\mathbb}		
\newcommand{\displaystyle}{\displaystyle}		
\newcommand{\underline}{\underline}		
\newcommand{\sigma}{\sigma}		
\newcommand{\lambda}{\lambda}		
\newcommand{\tau}{\tau}			
\newcommand{\otimes}{\otimes}		
\newcommand{\twoheadrightarrow}{\twoheadrightarrow}
\newcommand{\cup}{\cup}		
\newcommand{\cap}{\cap}		
\newcommand{\hookrightarrow}{\hookrightarrow}

\newcommand{G_{d,n}}{G_{d,n}}		
\newcommand{I(d,n)}{I(d,n)}		
\newcommand{S^v_w}{S^v_w}		
\newcommand{S^v_wm}{S^v_w(m)}		
\newcommand{S^v}{S^v}			
\newcommand{{\underline{i}}}{{\underline{i}}}	
\newcommand{{\mathfrak N}}{{\mathfrak N}}		

\newcommand{\smvw}{\begin{mbox}
		{\rm SM}\end{mbox}^v_w}	
\newcommand{\smvw(m)}{\smvw(m)}		

\newcommand{\mathfrak S}{\mathfrak S}		
\renewcommand{\frak B}{\mathfrak B}		
\newcommand{\vdeg}[1]{\mbox{{\rm $v$-degree}}(#1)}

\newcommand{\vdeg}{\vdeg}		
\newcommand{\degree}[1]{\mbox{{\rm degree}}(#1)}

\newcommand{\prod}{\prod}		
\newcommand{T^v}{T^v}			
\newcommand{U^v}{U^v}			
\newcommand{U^vm}{U^v(m)}		
\newcommand{T^vwm}{T^v_w(m)}		
\newcommand{\smvtopv}{\begin{mbox}
		{\rm SM}\end{mbox}^{v,v}} 
\newcommand{\smvtopvm}{\begin{mbox}
		{\rm SM}\end{mbox}^{v,v}(m)} 
\newcommand{\smvtopvw}{\begin{mbox}
		{\rm SM}\end{mbox}^{v,v}_w} 
\newcommand{\smvtopvwm}{\begin{mbox}
		{\rm SM}\end{mbox}^{v,v}_w(m)} 
\newcommand{\smvvm}{\begin{mbox}
		{\rm SM}\end{mbox}^{v}_v(m)} 
\newcommand{\tilde{\pi}}{\tilde{\pi}}	
\newcommand{\tilde{\phi}}{\tilde{\phi}}	
\newcommand{\mathfrak R }{\mathfrak R }		
\renewcommand{\frak T}{\mathfrak T}		
\newcommand{{\frak T}^w_j}{{\frak T}^w_j}		

\newcommand{\mathfrak Sj}{\mathfrak S_j}		
\newcommand{\mathfrak Sw}{{\mathfrak S}_w}		
\newcommand{\mathfrak Swj}{{\mathfrak S}_w^j}		
\newcommand{\mathfrak Swk}{{\mathfrak S}_w^k}		
\newcommand{\mathfrak Swone}{{\mathfrak S}_w^1}		
\newcommand{\mathfrak Swtwo}{{\mathfrak S}_w^2}		
\newcommand{\mathfrak P}{\mathfrak P}			
\newcommand{\mathfrak C}{\mathfrak C}			

\newcommand{\mathfrak B}{\mathfrak B}		
\newcommand{\mathfrak C}{\mathfrak C}		
\newcommand{\mathfrak Cnot}{\mathfrak C_0}		
\newcommand{\mathfrak Cone}{\mathfrak C_1}		

\newcommand{\mathfrak Ba}{\mathfrak A}		
\newcommand{\mathfrak Bd}{\mathfrak D}		
\newcommand{\mathfrak Be}{\mathfrak E}		

\newcommand{\card}[1]{|#1|}		

\newcommand{\init}[1]{\mbox{{\rm in}}(#1)}
\newcommand{>_1}{>_1}		
\newcommand{>_2}{>_2}		
\newcommand{>_3}{>_3}		
\newcommand{>_4}{>_4}		

\newcommand{U^vw}{{\mathfrak U}^v_w}	
\newcommand{N^v_w}{N^v_w}		
\newcommand{R^v_w}{R^v_w}		
\newcommand{\Lambda}{\Lambda}		
\newcommand{\beta^{\mbox{\begin{rm}start\end{rm}}}}{\beta^{\mbox{\begin{rm}start\end{rm}}}}

\newcommand{\beta^{\mbox{\begin{rm}start\end{rm}}}j}{\beta^{\mbox{\begin{rm}start\end{rm}}}_j}
\newcommand{\beta^{\mbox{\begin{rm}finish\end{rm}}}}{\beta^{\mbox{\begin{rm}finish\end{rm}}}}

\newcommand{\beta^{\mbox{\begin{rm}finish\end{rm}}}j}{\beta^{\mbox{\begin{rm}finish\end{rm}}}_j}

\addtolength{\itemsep}{-100mm}

\title{Hilbert functions of points on\\
	 Schubert varieties in the Grassmannian}
\author{V.~Kodiyalam  and K.N.~Raghavan \\
Institute of Mathematical Sciences \\
C.I.T.~Campus, Taramani\\
Chennai 600 113 INDIA \\
E-mail: vijay@imsc.ernet.in and knr@imsc.ernet.in
}

\maketitle

\newtheorem{theorem}{Theorem}[section]
\newcommand{\begin{theorem}}{\begin{theorem}}
\newcommand{\end{theorem}}{\end{theorem}}

\newtheorem{proposition}[theorem]{Proposition}

\newcommand{\begin{proposition}}{\begin{proposition}}
\newcommand{\begin{proposition}op}{\begin{proposition}}
\newcommand{\end{proposition}}{\end{proposition}}
\newcommand{\end{proposition}op}{\end{proposition}}

\newtheorem{definition}[theorem]{Definition}

\newcommand{\begin{definition}\begin{rm}}{\begin{definition}\begin{rm}}
\newcommand{\end{rm}\end{definition}}{\end{rm}\end{definition}}

\newtheorem{example}[theorem]{Example}

\newcommand{\begin{example}\begin{rm}}{\begin{example}\begin{rm}}
\newcommand{\ $\Box$\end{rm}\end{example}}{\ $\Box$\end{rm}\end{example}}

\newtheorem{remark}[theorem]{Remark}
\newcommand{\begin{remark}\begin{rm}}{\begin{remark}\begin{rm}}
\newcommand{\end{rm}\end{remark}}{\end{rm}\end{remark}}

\newtheorem{corollary}[theorem]{Corollary}
\newcommand{\begin{corollary}}{\begin{corollary}}
\newcommand{\end{corollary}}{\end{corollary}}

\newtheorem{exercise}[theorem]{Exercise}

\newcommand{\begin{exercise}\begin{rm}}{\begin{exercise}\begin{rm}}
\newcommand{\end{rm}\end{exercise}}{\end{rm}\end{exercise}}

\newtheorem{lemma}[theorem]{Lemma}

\newcommand{\begin{lemma}}{\begin{lemma}}
\newcommand{\begin{lemma}ma}{\begin{lemma}}
\newcommand{\end{lemma}}{\end{lemma}}
\newcommand{\end{lemma}}{\end{lemma}}

\newenvironment{proof}[1][]{{\sc Proof #1}:\ }{\ $\Box$}
\newcommand{\begin{proof}}{\begin{proof}}
\newcommand{\begin{proposition}oof}{\begin{proof}}
\newcommand{\end{proof}}{\end{proof}}
\newcommand{\end{proposition}oof}{\end{proof}}

\newenvironment{prooftwo}[1][]{{\sc Proof #1}:\ }{}
\newcommand{\begin{proof}two}{\begin{prooftwo}}
\newcommand{\begin{proposition}ooftwo}{\begin{prooftwo}}
\newcommand{\end{proof}two}{\end{prooftwo}}
\newcommand{\end{proposition}ooftwo}{\end{prooftwo}}

\newenvironment{solution}{{\sc Solution}:\ }{\ $\Box$}
\newcommand{\begin{solution}}{\begin{solution}}
\newcommand{\end{solution}}{\end{solution}}

\section{Introduction}\label{sintro}
This paper arose out of our reading of the recent paper \cite{kl}
of Kreiman and Lakshmibai.   They consider the following problem.
Let $X$ be a Schubert variety in the Grassmannian $G_{d,n}$ of $d$-planes
in $n$-dimensional linear space.    Given a point $x$ on $X$,  what is
the Hilbert function of the tangent cone to $X$ at $x$?

In case the point $x$ is the ``identity coset'',  Kreiman and
Lakshmibai deduce, from well known results of Hodge~\cite[Chapter XIV]{hodge} and
Musili~\cite{smt} about homogeneous co-ordinate rings of Schubert varieties in
the Grassmannian,   an expression
for the Hilbert function in terms
of the combinatorics of the Weyl group.
From this they recover the interpretation of the multiplicity,
due to Herzog and Trung \cite{ht}, as the cardinality of a certain set of
non-intersecting lattice paths.   One can interpret their main result as saying
that the natural set of generic determinantal minors that generate the ideal of
the tangent cone form a Gr\"obner basis in the ``anti-diagonal'' term order.

As to the case when $x$ is
some other point,  they conjecture expressions for
the Hilbert function and the multiplicity.

In the present paper,  we clarify the approach of Kreiman and Lakshmibai,
thereby handling, in their spirit,  all points.   We extend their
expressions
and combinatorial interpretation to all points.
Here again there is an interpretation of the main result in terms of Gr\"obner basis.

Even in the case when $x$ is the identity coset,  we have something to say
that is not already in \cite{kl}.     Namely we give explicitly a bijection between
the combinatorially defined sets $SM_w(m)$ and $S_w(m)$ of that paper.
The bulk of this paper,  namely \S4, is devoted to establishing 
this bijection.   While we are convinced that this bijection is natural and
moreover that it is, in some sense,  the only natural bijection,
we are unable to make this precise.   It would be good to have this
nailed down.

The expressions for the Hilbert function and
the multiplicity are given respectively in Theorem~\ref{tmain}  and
Corollary~\ref{cmain} of \S\ref{stheorem} below.
The combinatorial interpretation of
the multiplicity and the interpretation of the main result in terms of Gr\"obner basis
are given in \S\ref{sinterpretation}.
The proof of Theorem~\ref{tmain}
occupies \S\ref{ssmt} and \S\ref{sproof}.   In \S\ref{ssmt}
the proof of the Theorem~\ref{tmain} is reduced to the solution of a combinatorial problem,
and in \S\ref{sproof}
a solution of the combinatorial problem is presented.
It is only in \S\ref{sproof} that this paper differs significantly from
\cite{kl}.

Krattenthaler~\cite{k} has proved the multiplicity conjecture of \cite{kl} but there is
little in common between his approach and ours.    It is possible that the methods
of the recent paper of Knutson and Miller~\cite{km} are relevant to our situation but
we have not investigated further along this direction except to notice that the results
of \cite{kl}
can be deduced from those of \cite{km}.

The ideal of the tangent cone at the identity coset (as a sub-variety of
the tangent space of the Grassmannian) is a determinantal ideal,  the ideal 
``co-generated'' by a minor.    Abhyankar \cite{abh} and Herzog-Trung \cite{ht}
give formulas for the multiplicity and Hilbert function of the quotient
ring by such a determinantal ideal.   Lakshmibai-Weyman \cite{lw} obtain,
using standard monomial theory (for the Grassmannian, this theory boils down
to the results of Hodge
and Musili mentioned above),
a recursive formula for the
multiplicity at any point (not just at the identity coset).   From this
recursive formula Rosenthal-Zelevinsky \cite{rz}
obtain a closed-form determinantal
formula for the multiplicity at any point.  Krattenthaler \cite{kr1} gives
an interpretation of the Rosenthal-Zelevinsky formula as counting certain
non-intersecting lattice paths,  and then,    using the technique of
dual paths,  deduces a simpler determinantal formula.    
Krattenthaler's papers \cite{kr1} and \cite{k} provide
the bridge
between what we do here and the Rosenthal-Zelevinsky formula.

\section{The Theorem}\label{stheorem}
The purpose of this section is to state Theorem~\ref{tmain} and
Corollary~\ref{cmain} below which provide respectively combinatorial
expressions for  the Hilbert
function and the multiplicity at a point on a Schubert variety in
a Grassmannian.
We start by recalling some well known facts about Schubert varieties in
Grassmannians.     This also serves to fix notation.

Once for all fix positive integers $n$ and $d$ with $d\leq n$.
Let $G_{d,n}$ denote the {\em Grassmannian},  which as a set consists of
$d$-dimensional linear subspaces of a fixed $n$-dimensional vector space.
Let us think of the $n$-dimensional vector space as the space of column matrices of
size $n\times 1$.   The general linear group $GL_n$ of $n\times n$ invertible
matrices acts on this by
left multiplication.   The induced action on $d$-dimensional subspaces
is transitive and so $G_{d,n}$ is the quotient of $GL_n$ by the stabilizer
of any given point.   We identify $G_{d,n}$
as the homogeneous
space $GL_n/P_d$,  where $P_d$ is the stabilizer of the point of $G_{d,n}$
that is the span of the first $d$ standard basis vectors $e_1,\ldots,e_d$;
here $e_j$ is the $n\times 1$ column matrix whose entries are all zero
except the one on row $j$ which is $1$.

Let $B$ be the ``Borel subgroup'' of $GL_n$ consisting of
invertible upper triangular matrices,
and $T$ the ``torus'' of $GL_n$ consisting of invertible diagonal matrices.
The points of $G_{d,n}$ that are fixed
by $T$ are precisely those $d$-planes that are spanned by $d$ of the standard
basis vectors. 

Let $I(d,n)$ denote the set of subsets of cardinality $d$ of $\{1,\ldots,n\}$.
We write an element $v$ of $I(d,n)$ as $(v_1,\ldots,v_d)$ where $1\leq v_1<\ldots
<v_d\leq n$.
Given an element $v=(v_1,\ldots,v_d)$ of $I(d,n)$,

we denote by $e^v$ the $T$-fixed point of $G_{d,n}$ that is the span of $e_{v_1},\ldots,
e_{v_d}$.
These points lie in different $B$-orbits and the union of the $B$-orbits
of these points is all of $G_{d,n}$.

   A {\em Schubert variety} in $G_{d,n}$
is by definition the closure of such a $B$-orbit (with the
reduced scheme structure).    It is a union of 
the $B$-orbit (of which it is the closure) with smaller dimensional
$B$-orbits.   Schubert varieties are thus indexed by $T$-fixed points
and so by $I(d,n)$.    Given $w\inI(d,n)$,  we denote by $X_w$ the closure of
the $B$-orbit of the $T$-fixed point $e^w$.

We are interested in the local rings of various points on a Schubert
variety $X_w$.    It is enough to focus attention on the $T$-fixed points
contained in $X_w$,  for $X_w$ is the union of $B$-orbits of such points.
The point $e^v$ belongs to $X_w$ if and only
if $v\leq w$,  where, 

  for elements $v= (v_1<\ldots<v_d)$ and $w=(w_1<\ldots<w_d)$
of $I(d,n)$,   we say $v\leq w$ if $v_1\leq w_1$,

$\ldots$,
 $v_d\leq w_d$. 

For the rest of this section,  fix elements $v,w$ of $I(d,n)$ with
$v\leq w$.  

Let $c$ be among the entries $v_1,\ldots,v_d$ of $v$, and
$r$ be among the complement $\{1,\ldots,n\}\setminus\{v_1,\ldots,v_d\}$.
Denote by $\mathfrak R ^v$ the set of ordered pairs $(r,c)$ of such 
$r$ and $c$,  and by ${\mathfrak N}^v$ the subset of $\mathfrak R ^v$ consisting
of those $(r,c)$ with $r>c$.  

We will be considering ``multisets'' of $\mathfrak R ^v$ and ${\mathfrak N}^v$.
By a {\em multiset} we mean a subset in which repetitions are
allowed and kept account of.   Multisets can be thought of as
monomials in the variables consisting of elements of the set.
We also use the term  {\em monomial} to refer to a multiset.
The {\em degree} of a monomial is just the cardinality,
counting repetitions, of the multiset.

Given $\beta_1=(r_1,c_1)$, $\beta_2=(r_2,c_2)$ elements in ${\mathfrak N}^v$,
we say $\beta_1>\beta_2$ if $r_1>r_2$ and $c_1<c_2$.   A sequence
$\beta_1>\ldots>\beta_t$ of elements of ${\mathfrak N}^v$ is called a
{\em $v$-chain}.
Given a $v$-chain $\beta_1=(r_1,c_1)>\ldots>\beta_t=(r_t,c_t)$, we denote
by $s_{\beta_1}\cdots s_{\beta_t}v$ the element 
$(\{v_1,\ldots,v_d\}\setminus\{c_1,\ldots,c_t\})\cup\{r_1,\ldots,r_t\}$
of $I(d,n)$.  In case the $v$-chain is empty,  this element is just $v$.
We say that $w$ {\em dominates} the $v$-chain
$\beta_1>\ldots>\beta_t$  if $w\geq 
s_{\beta_1}\cdots s_{\beta_t}v$.

Let $\mathfrak S$ be a monomial in $\mathfrak R ^v$.  By a {\em $v$-chain in $\mathfrak S$}
we mean a sequence $\beta_1>\ldots>\beta_t$ of elements of
$\mathfrak S\cap{\mathfrak N}^v$.  We say that {\em $w$ dominates $\mathfrak S$} if $w$
dominates every $v$-chain in $\mathfrak S$.

Let $S^v_w$ denote the set of $w$-dominated monomials in $\mathfrak R ^v$,
and $S^v_w(m)$ the set of such monomials of degree $m$.

We can now state our theorem:
\begin{theorem} \label{tmain} {\bf (Conjecture of Kreiman and Lakshmibai)}
Let $v,w$ be elements of $I(d,n)$ with $v\leq w$.   Let $X_w$ be the
Schubert variety corresponding to $w$,  $e^v$ the $T$-fixed point
corresponding to $v$, and $R$ the co-ordinate ring of the tangent cone
to $X_w$ at the point $e^v$ (that is,  the associated graded ring
${\begin{rm}gr\end{rm}}_{\mathfrak{M}}(O_{X_w, e^v})$ of the local ring
$O_{X_w,e^v}$ of $X_w$ at the point $e^v$ with respect to its maximal
ideal $\mathfrak{M}$).     Then the vector space dimension of the 
$m^{\begin{rm}th\end{rm}}$ graded piece $R(m)$ of $R$ equals the 
cardinality of $S^v_wm$,  where $S^v_wm$ is as defined above.
\end{theorem}
The proof of the theorem occupies sections \ref{ssmt} and \ref{sproof} .   
For now let us note the following easy consequence.

\begin{corollary}\label{cmain}
With notation as in Theorem~\ref{tmain} above,
the multiplicity of $R$ equals the number of square-free
$w$-dominated monomials in $\mathfrak R ^v$ of maximum cardinality.

\end{corollary}
\begin{proposition}oof
Consider the set $\left\{A_1,\ldots,A_k\right\}$ of all
members of $S^v_w$ that have no repetitions and that are maximal
with respect to inclusion among those having no repetitions. 

For a subset
${\underline{i}}:= \left\{i_1<\ldots<i_j\right\}$ of cardinality $j$ of
$\left\{1,\ldots,k\right\}$,  let $a_{{\underline{i}}}$ denote the cardinality of
$A_{i_1}\cap\cdots\cap A_{i_j}$.   Then, since $S^v_wm$ is the set of
all monomials of degree $m$ with elements from any one of the $A_j$ as
variables,  we have
\[
	\begin{mbox}{\rm Cardinality of $S^v_wm$}\end{mbox}
=
\sum\limits_{j=1}^k (-1)^{j-1}\sum\limits_{{\underline{i}}}
\binom{a_{{\underline{i}}}-1+m}{a_{{\underline{i}}}-1}
				\]
where the inner summation is over all subsets ${\underline{i}}$ of cardinality $j$
of $\left\{1,\ldots,k\right\}$.   It follows immediately that the
multiplicity equals the number of ${\underline{i}}$ with $a_{{\underline{i}}}$ as large as
possible,  which  in other words is the number of $A_1,\ldots,A_k$ with
maximum cardinality.\end{proposition}oof

\section{Reduction of the proof to combinatorics}\label{ssmt}
In this section we will see how some well known results of
Hodge~\cite[Chapter XIV]{hodge}
and Musili~\cite{smt} about homogeneous co-ordinate rings of Schubert
varieties in the Grassmannian allow us
to reduce the proof of Theorem~\ref{tmain} to the solution of 
a combinatorial problem.    This reduction is already there
in Lakshmibai-Weyman~\cite{lw} (see their Theorem~3.4) and in a
more general set-up,  but it would hurt readability if we merely
quoted their result and cut this section out.

Fix elements $v,w$ of $I(d,n)$ with $v\leq w$, so that $e^v$ belongs to 
the Schubert variety $X_w$.   Let $G_{d,n}\hookrightarrow\mathbb{P}(\wedge^d V)$
be the Pl\"ucker embedding,  where we think of $G_{d,n}$ as $d$-dimensional
subspaces of the $n$-dimensional vector space $V$.    For $\theta$
in $I(d,n)$,  let $p_\theta$ denote the Pl\"ucker co-ordinate 
corresponding to $\theta$.    Let $\mathbb{A}^v$
be the affine patch of $\mathbb{P}(\wedge^d V)$ given by $p_v\neq0$,
 and set

$Y^v_w := X_w \cap \mathbb{A}^v$.
The point $e^v$ is the origin of the affine space $\mathbb{A}^v$.

The functions $f_u := p_u/p_v$,  $u\inI(d,n)$, provide a
set of co-ordinate functions on $\mathbb{A}^v$.  The co-ordinate ring
$k[Y^v_w]$ of $Y^v_w$ is a quotient of the polynomial ring 
$k[f_u{\,|\,} u\inI(d,n)]$,    $k$ being the underlying field. 
In order to describe a basis for $k[Y^v_w]$ as a $k$-vector space,   we now make some
definitions.

We consider multisets of $I(d,n)$, or, in other words, monomials with elements
of $I(d,n)$ as variables.
Such a monomial is called {\em standard}  if after
suitable rearrangement it has the form $\left\{\theta_1,\ldots,\theta_t\right\}$
with $\theta_1\geq\ldots\geq \theta_t$.   A standard monomial 
$\theta_1\geq\ldots\geq\theta_t$  is {\em $w$-dominated} if 
$w\geq\theta_1$;  it is {\em $v$-compatible}  if each of $\theta_1,
\ldots,\theta_t$ is comparable with $v$ and none of them equals $v$.
We denote the set of all $w$-dominated $v$-compatible standard monomials
by $\smvw$.   
\begin{proposition}op\label{psmt} 
As $\theta_1\geq\ldots\geq\theta_t$ varies over $\smvw$, that is, over
all $w$-dominated $v$-compatible standard monomials,  the elements
$f_{\theta_1}\cdots f_{\theta_t}$ form a $k$-vector space basis of $k[Y_w^v]$.
\end{proposition}op
\begin{proposition}oof

We know from \cite[\S4]{smt} that the elements $p_{\tau_1}\cdots p_{\tau_s}$,
as $\tau_1\geq\ldots\geq\tau_s$  varies over all $w$-dominated standard
monomials,   form a basis for the homogeneous co-ordinate ring of $X_w$
as embedded in $\mathbb{P}(\wedge^d V)$.
(In \cite{smt}, $G_{d,n}$ is identified as a right coset space rather than as a
left coset space as we have done here,  but there should be no problem in
translating the statements from there to our set up.)

Consider now any linear dependence relation among the $f_{\theta_1}
\cdots f_{\theta_t}$ with $\theta_1\geq \ldots\geq \theta_t$ in $\smvw$.
Multiplying this by a suitably high power of $p_v$ yields a linear
dependence relation among the $w$-dominated standard monomials
$p_{\tau_1}\cdots p_{\tau_s}$ (so called by an abuse of terminology),
and so the original dependence relation
must have only been the trivial one.

To prove that $f_{\theta_1}\cdots f_{\theta_t}$ generate $k[Y^v_w]$ as a vector
space (as $\theta_1\geq\ldots\geq\theta_t$ varies over $\smvw$), we use the
following fact:   if $\mu_1,\ldots,\mu_r$ be any monomial in $I(d,n)$, and
$p_{\tau_1}\cdots p_{\tau_s}$ a standard monomial that occurs with non-zero
coefficient in the expression for $p_{\mu_1}\cdots p_{\mu_r}$ (as an element
of the homogeneous co-ordinate ring of $X_w$) as a linear combination of
$w$-dominated standard monomials,  then $r=s$ and $\tau_1\cup\cdots\cup\tau_s$
equals $\mu_1\cup\cdots\cup\mu_r$ as multisets of $\{1, 2,\ldots,n\}$.   This fact
follows from the nature of the quadratic relations (page 152 of \cite{smt}) which
provide the key to showing that the $w$-dominated standard monomials span
the homogeneous co-ordinate ring of $X_w$.
Let $\sigma_1,\ldots,\sigma_r$ be any monomial in
$I(d,n)$.     Consider the  expression for
$p_{\sigma_1}\cdots
p_{\sigma_r}\cdot p_v^h$,  where $h$ is an integer such that $h>r(d-1)$, as a linear
combination of $w$-dominated standard monomials.
We claim that $p_v$ occurs in every standard monomial in this expression.
To prove the claim,  suppose that $p_{\tau_1}\cdots p_{\tau_{r+h}}$ is such a
standard monomial,  and that none of $\tau_1,\ldots,\tau_{r+h}$ equals $v$.  For
each $\tau_j$ there is at least one entry of $v$ that does not occur in $\tau_j$.
The number of occurrences of entries of $v$ in ${\tau_1}\cup\cdots\cup {\tau_{r+h}}$
is thus at most $(r+h)(d-1)$.   But these entries occur at least $hd$ times in
${\sigma_1}\cup\cdots\cup {\sigma_r}\cup v\cup\cdots\cup v$
(where $v$ is repeated $h$ times),  a contradiction to the fact above,
and the claim is proved.

Dividing by $p_v^{r+h}$ the expression for $p_{\sigma_1}\cdots p_{\sigma_r}\cdot
p^h_v$ as a linear combination of $w$-dominated standard monomials provides
an expression for $f_{\sigma_1}\cdots f_{\sigma_r}$ as a linear combination of
$f_{\theta_1}\cdots f_{\theta_t}$,   as $\theta_1\geq\ldots\geq\theta_t$ varies over
$\smvw$.\end{proposition}oof

For $\theta\inI(d,n)$,  define the {\em $v$-degree} of $\theta$
to be the cardinality of the set $\theta\setminus v$ (as a subset  of $\{1,2,\ldots,n\}$).
 Set $Z^v:=G_{d,n}\cap\mathbb{A}^v$.  The co-ordinate ring $k[Z^v]$ of
$Z^v$ is a polynomial ring in the indeterminates $f_\theta$ with
$\theta$ varying over the elements of $I(d,n)$ with $v$-degree $1$.
Such $\theta$ are in bijective correspondence with the elements
$\beta$ of $\mathfrak R ^v$: if $\beta=(r,c)$,
then $\theta$ is obtained from
$v$ by replacing $c$ with $r$.   We set $X_\beta:=f_\theta$
and arrange them in a matrix as shown in Figure~1 
 for the case $d=4$, $n=10$, and $v=(2,5,7,9)$.

\[\begin{array}{c}
\left( \begin{array}{cccc}
	X_{12} & X_{15} & X_{17} &X_{19}\\
	1 & 0 & 0 & 0\\
	X_{32} & X_{35} & X_{37} &X_{39}\\
	X_{42} & X_{45} & X_{47} &X_{49}\\
	0 & 1 & 0 & 0\\
	X_{62} & X_{65} & X_{67} &X_{69}\\
	0 & 0 & 1 & 0\\
	X_{82} & X_{85} & X_{87} &X_{89}\\
	0 & 0 & 0 & 1\\
	X_{10,2} & X_{10,5} & X_{10,7} &X_{10,9}\\
\end{array} \right)\\
\mbox{}\\
\mbox{
Figure 1: The matrix of $X_\beta$, $\beta$ an element of $\mathfrak R ^v$,}\\

\mbox{for the case $d=4$, $n=10$, and $v=(2,5,7,9).$}
\end{array}\]

The expression for a general $f_\theta$ in terms
of the indeterminates $X_\beta$ is obtained by taking the determinant
of the sub-matrix of such a matrix as in Figure~1 obtained by choosing
the rows given by the entries of $\theta$. 
Thus it is a graded polynomial of degree the $v$-degree of 
$\theta$. Since $X_w$ is the 
intersection of $G_{d,n}$ with the planes $p_\tau$, $\tau\not\leq w$ (again see
\cite[Theorem~4.1]{smt}),
the co-ordinate ring $k[Y^v_w]$ is a quotient of the polynomial ring
$k[Z^v]$ by the homogeneous ideal $(f_\tau{\,|\,}\tau\not\leq w)$.
We are interested in the tangent cone to $Y^v_w$ at the origin (the
point of $Z^v$ corresponding to $e^v$),  and since $k[Y^v_w]$
is graded,  this tangent cone is isomorphic to $k[Y^v_w]$ itself.

The proposition above tells us that the graded piece of degree $m$
of $k[Y^v_w]$ is generated as a $k$-vector space by elements of
$SM^v_w$ of degree $m$,  where the degree of a standard monomial
$f_{\theta_1}\cdots f_{\theta_t}$ is defined to be the sum of
the $v$-degrees of $\theta_1,\ldots,\theta_t$.
To prove Theorem~\ref{tmain} it therefore suffices
to show that the set $SM^v_w(m)$ of $v$-compatible $w$-dominated
standard monomials of degree $m$ is in bijection with $S^v_w(m)$.

\section{The Proof}\label{sproof}
In this section we show that $\smvw(m)$ and $S^v_w(m)$ are naturally
bijective.    As we saw in the previous section,   this serves to
complete the proof of Theorem~\ref{tmain}.

We fix once for all an element $v=(v_1,\ldots,v_d)$ of $I(d,n)$.

We will describe two maps called $\pi$ and $\phi$.
The map $\pi$ associates
to any non-empty monomial $\mathfrak S$ of elements in ${\mathfrak N}^v$ a pair
$(w,\mathfrak S')$   consisting of an element $w$ of $I(d,n)$ and a ``smaller''
monomial $\mathfrak S'$ in ${\mathfrak N}^v$.   This map enjoys the following good
properties:
\begin{proposition}op\label{ppi}
\begin{enumerate}
\item
$w\gneq v$
\item
$\vdeg{w}+\degree{\mathfrak S'}=\degree{\mathfrak S}$
\item
$w$ dominates $\mathfrak S'$
\item
$w$ is the least element of $I(d,n)$ that dominates $\mathfrak S$.
\end{enumerate}
\end{proposition}op
The map $\phi$, on the other hand,   associates a non-empty monomial in
${\mathfrak N}^v$  to any pair $(w,\frak T)$ consisting of an element $w$ of $I(d,n)$ with
$w\gneq v$  and a $w$-dominated monomial $\frak T$,  possibly empty, in ${\mathfrak N}^v$.
\begin{proposition}op\label{ppiphi}
The maps $\pi$ and $\phi$ are inverses of each other.
\end{proposition}op

Before turning to the descriptions of $\pi$ and $\phi$ and the
proofs of the propositions above,
let us see how these mutually inverse maps help us establish the desired
bijection between $\smvw(m)$ and $S^v_w(m)$.
Let $S^v$ denote the set of monomials in $\mathfrak R ^v$ and $T^v$ the set of monomials
in ${\mathfrak N}^v$.

Let $\smvtopv$ denote the set of $v$-compatible standard monomials that are anti-dominated
by $v$:   a standard monomial $\theta_1\geq \ldots\geq \theta_t$ is
{\em anti-dominated} by $v$ if $\theta_t\geq v$   (we can also write
$\theta_t>v$ since $\theta_t\neq v$ by $v$-compatibility).

Define the {\em domination map} from $T^v$ to $I(d,n)$ by
sending a monomial in ${\mathfrak N}^v$ to the least element that dominates it.
Define the {\em domination map} from $SM^{v,v}$
to $I(d,n)$ by sending $\theta_1\geq\ldots\geq\theta_t$ to
$\theta_1$. 
Both these maps take, by definition, the value $v$ on the empty monomial.

Using $\pi$, we now define a  map $\tilde{\pi}$  from $T^v$ to $\smvtopv$
that commutes with domination and preserves degree.    Proceed by
induction on the degree of an element $\mathfrak S$ of $T^v$.   
The image of the empty monomial under $\tilde{\pi}$ is taken to be the
empty monomial.

Let $\mathfrak S$ be non-empty,   and suppose that $\pi(\mathfrak S) =(w,\mathfrak S')$.    By (1) and
(2) of Proposition~\ref{ppi},   the degree of $\mathfrak S'$ is strictly less
than that of $\mathfrak S$,  and so by induction $\tilde{\pi}(\mathfrak S')$  is defined.
Suppose that $\tilde{\pi}(\mathfrak S')=w'\geq\ldots$.    By induction we also know
that the degree of $\mathfrak S'$ is the same as that of $w'\geq\ldots$ and that
$w'$ is the least element of $I(d,n)$ that dominates $\mathfrak S'$.   By (3) of
Proposition~\ref{ppi},     we have $w\geq w'$,  and we set
$\tilde{\pi} (\mathfrak S):=w\geq\tilde{\pi}(\mathfrak S')$.   It follows from (4) of the same
proposition that $\mathfrak S$ has the same image under domination as
$\tilde{\pi} (\mathfrak S)$,  namely $w$.   It follows from (2) of the proposition
that the degrees of $\mathfrak S$ and $\tilde{\pi}(\mathfrak S)$ are the same, and the
induction is complete.

Using $\phi$, we  now define a map $\tilde{\phi}$ from $\smvtopv$ to $T^v$
that commutes with domination.    Proceed by induction on the length 
$t$ of a standard monomial  $\theta_1\geq\ldots\geq\theta_t$ in $\smvtopv$.
The image of the empty monomial under $\tilde{\phi}$ is taken to be the empty
monomial.   Letting $t\geq1$, we know by induction what $\tilde{\phi}(\theta_2\geq
\ldots\geq\theta_t)$ is,  and let us denote it by $\frak T$.   We also know
that $\theta_2$ is the least element that dominates $\frak T$, so that
$\theta_1$ dominates $\frak T$.    We set $\tilde{\phi}(\theta_1\geq\ldots\geq
\theta_t):=\phi(\theta_1,\frak T)$.    
By Proposition~\ref{ppiphi},  we know $\pi\phi(\theta_1,\frak T)=(\theta_1,\frak T)$,
so that the image under the domination map of $\tilde{\pi}\phi(\theta_1,\frak T)$ is
$\theta_1$.      Since $\tilde{\pi}$ commutes with domination,  it follows that $\theta_1$
is the least element to dominate $\phi(\theta_1,\frak T)$, and the induction is complete.

Easy arguments using induction,   which we omit,   show that $\tilde{\pi}$
and $\tilde{\phi}$ are mutually inverse maps.    Since $\tilde{\pi}$ preserves
degree,   it follows as a consequence that $\tilde{\phi}$ too preserves degree.

The maps $\tilde{\pi}$ and $\tilde{\phi}$   establish a bijection between
$\smvtopv$ and $T^v$.   In fact, since domination and degree are
respected,   we get a bijection $\smvtopvw(m)\congT^vwm$, where
$\smvtopvwm$ is the set of $w$-dominated elements of $\smvtopv$
that have degree $m$,   and similarly $T^vwm$ is the set of $w$-dominated
elements of $T^v$ that have degree $m$.

Now let $U^v$ denote the set of monomials in $\mathfrak R ^v\setminus{\mathfrak N}^v$
(that is,  in pairs $(r,c)$ of $\mathfrak R ^v$ with $r<c$), and $SM^v_v$ 
the set of $v$-compatible and $v$-dominated standard monomials.  
As explained below,  the ``mirror image'' of the bijection
$SM^{v,v}\cong T^v$   gives a bijection $SM^v_v(m)\cong U^v(m)$,
where $SM^v_v(m)$ and $U^v(m)$ denote respectively the sets of elements
of degree $m$ of $SM^v_v$ and $U^v$.

Putting these bijections together, we get the desired
bijection:
\begin{eqnarray*}
\smvw(m) &=& 
	\bigcup\limits_{j=0}^m SM^{v,v}_w(j) \times
	SM^v_v(m-j)\\
&\cong&\bigcup\limits_{j=0}^m T^v_w(j) \times
				U^v(m-j)
				= S^v_w(m).
\end{eqnarray*}
Here the first equality is obtained by splitting a $v$-compatible
standard monomial $\theta_1\geq\ldots\geq\theta_t$ into two parts
$\theta_1\geq\ldots\geq\theta_p$ and $\theta_{p+1}\geq\ldots\geq\theta_t$,
where $p$ is the largest integer,  $1\leq p\leq t$,  with $\theta_p\geq v$
(we can also write $\theta_p>v$ since $\theta_p\neq v$ by
$v$-compatibility).    The last equality is obtained by writing a
monomial of degree $m$ in $\mathfrak R ^v$ as a product of two monomials, one
in ${\mathfrak N}^v$ and the other in $\mathfrak R ^v\setminus{\mathfrak N}^v$,
the sum of  their degrees being $m$.

Let us now briefly explain how to take the ``mirror image''.
For an integer $x$, $1\leq x\leq n$, define the dual $x^*$ by
$x^*:=n-x+1$.   For $v=(v_1,\ldots,v_d)$ in $I(d,n)$,  define
the dual $v^*$ by $v^*:=(v_d^*,\ldots,v^*_1)$.   This dual map
on $I(d,n)$ is an order reversing involution.  It induces a 
bijection $SM^v_v\cong SM^{v^*,v^*}$ by associating to
$\theta_1\geq\ldots\geq\theta_t$ the element $\theta_t^*
\geq\ldots\geq\theta^*_1$.   The sum of the $v$-degrees of 
$\theta_1,\ldots,\theta_t$ equals the sum of the $v^*$-degrees of
$\theta_t^*,\ldots,\theta_1^*$,  so that we get a bijection
$SM^v_v(m)\cong SM^{v^*,v^*}(m)$.

For an element $(r,c)$ in ${\mathfrak N}^{v^*}$,  define
the dual to be the element $(r^*,c^*)$
$\mathfrak R ^v\setminus{\mathfrak N}^v$.
This induces a degree preserving bijection $T^{v^*}\cong U^v$.
Putting this together with the bijection of the previous paragraph and the
one given by $\tilde{\pi}$ and $\tilde{\phi}$ (for $v^*$ in place of $v$),
we have
\[
	SM^v_v(m)\cong SM^{v^*,v^*}(m)\cong T^{v^*}(m)\cong U^v(m)
								\]
The proof of Theorem~\ref{tmain} is thus reduced to the descriptions
of the maps $\pi$ and $\phi$ and the proofs of Propositions
\ref{ppi}  and \ref{ppiphi}.

\subsection{Preparation}\label{sspreparation}
The statements in the sequel and their proofs may appear
to be more involved than they really are.  We have found it convenient
to think of them in terms of pictures as illustrated in
Example~\ref{epi} below and in \S\ref{sinterpretation}.
In fact, they are just a translation into the language of
words of pictorial suggestions that are more or less obvious.

Recall from \S\ref{ssmt} the definition of $v$-degree of an element $\theta$ of
$I(d,n)$:    it is the cardinality of the set $\theta\setminus v$ (or,
equivalently,  that of $v\setminus\theta$).   If $\beta_1>\ldots>\beta_t$ is a $v$-chain,
we call  $\beta_1$ the {\em head} of the $v$-chain, $\beta_t$ its {\em tail}, and $t$ its
{\em length}.
Let $\mathfrak S$ be a subset of ${\mathfrak N}^v$.    We say that an element $\beta$ of $\mathfrak S$
is {\em $t$-deep} in $\mathfrak S$ (where $t$ is a positive integer) if it is the tail of $v$-chain
in $\mathfrak S$ of length $t$.     The {\em depth} of $\beta$ in $\mathfrak S$ is $t$ if $\beta$ is
$t$-deep but not $(t+1)$-deep.   Two distinct elements $\alpha$ and $\beta$
of ${\mathfrak N}^v$ are said to be {\em comparable} if either $\alpha>\beta$ or $\beta>\alpha$.
Suppose, for example, that $\alpha=(r,c)$ and $\beta=(r,C)$.  In this case the two
are not comparable unless of course $c=C$.

The following proposition can be interpreted as specifying the map $\phi$
in the special case when $\frak T$ is empty.   It will be used in the description
of $\pi$.    Let us call {\em distinguished} the subsets (in the usual sense, not multisets) $\mathfrak S$
of ${\mathfrak N}^v$ satisfying the following conditions:
\begin{enumerate}
\item[(A)]
For $(r,c)\neq (r',c')$ in $\mathfrak S$,  we have $r\neq r'$ and $c\neq c'$
(in other words,  no two distinct elements of $\mathfrak S$ share a row or column
index).
\item[(B)]
If $\mathfrak S=\{(r_1,c_1),\ldots,(r_p,c_p)\}$ with $r_1<r_2<\ldots<r_p$,
then for $j$, $1\leq j\leq p-1$,  we have either $c_j>c_{j+1}$ or
$r_j<c_{j+1}$.
\end{enumerate}
Condition (B) can be restated as follows:
\begin{enumerate}
\item[(B*)]
For $(r,c), (R,C)$ in $\mathfrak S$ with $r<R$,  either $C<c$ or $r<C$.
\end{enumerate}
\begin{proposition}op\label{psw}
There exists a bijection between elements $w$ of $I(d,n)$ satisfying
$w\geq v$ on the one hand and subsets $\mathfrak S$ of ${\mathfrak N}^v$ satisfying
conditions (A) and (B) above on the other.  If $\mathfrak S_w$ be the subset
of ${\mathfrak N}^v$ corresponding to $w$ under this bijection, then

the $v$-degree of $w$ equals the cardinality of $\mathfrak S_w$.

\end{proposition}op
\begin{proposition}oof
Given $w\geq v$, consider the sets
$\{w_1,\ldots,w_d\}\setminus\{v_1,\ldots,v_d\}$
and
$\{v_1,\ldots,v_d\}\setminus\{w_1,\ldots,w_d\}$.
Both these have the same cardinality $p=\vdeg{w}$.   The first set provides us with
the row indices of elements of $\mathfrak S_w$,  the second with the column indices.
If we arrange the row indices in an increasing order,  say we have
$r_1<\cdots<r_p$,    then there is a unique way to arrange the
column indices such that condition (B*) above is satisfied: proceed by
induction,  and if $c_1,\ldots,c_j$ have been chosen,  choose $c_{j+1}$ to be
the maximum among the remaining column indices that are less than $r_{j+1}$.
This defines the map $w\mapsto\mathfrak S_w$.    It is clear that the cardinality
of $\mathfrak S_w$ equals $\vdeg{w}$.

For the map in the other direction,   given $\mathfrak S$,  to obtain $w$,  start with
$v=(v_1,\ldots,v_d)$,  delete those entries that occur as column indices in
$\mathfrak S$,  add those that occur as row indices in $\mathfrak S$,  and finally
arrange the entries in increasing order.  It is readily seen that the
two maps are inverses of each other.\end{proposition}oof

\begin{remark}\begin{rm}\label{rsw}
\begin{enumerate}
\item
Subsets of distinguished monomials are themselves distinguished.
\item
If $\mathfrak S$ is a subset of ${\mathfrak N}^v$ satisfying condition (A),  then
we can still define a corresponding element $w$ of $I(d,n)$ as in
the proof of the proposition.
If $\mathfrak S\subseteq\tilde{\mathfrak S}$ are subsets of ${\mathfrak N}^v$ satisfying condition
(A),   $w$ and $\tilde{w}$ the corresponding elements of $I(d,n)$,  then
$w\leq \tilde{w}$.
\end{enumerate}
\end{rm}\end{remark}

\begin{lemma}ma\label{ldom}
Let $\beta_1=(r_1,c_1)>\ldots>\beta_t=(r_t,c_t)$ be a $v$-chain,
$w$ and element of $I(d,n)$ with $w\geq v$, and $\mathfrak Sw$ the
distinguished subset of ${\mathfrak N}^v$ associated to $w$.  Then
$w$ dominates $\beta_1>\ldots>\beta_t$ if and only if there
exists a $v$-chain $\alpha_1=(R_1,C_1)>\ldots>\alpha_t=(R_t,C_t)$
in $\mathfrak Sw$ such that $C_j\leq c_j$ and $r_j\leq R_j$
for $1\leq j\leq t$.
\end{lemma}
\begin{proposition}ooftwo
Just for the purpose of this proof,  we introduce the
following notation:   for a subset $A$ of positive integers
and $l$ a positive integer,  denote by $A^l$ the subset
$\{a\in A{\,|\,} a\leq l\}$.   Note that for elements $u,y$ of
$I(d,n)$,  we have $u\leq y$ if and only if $\card{u^l}
\geq \card{y^l}$ for every $l$,  where $\card{\cdot}$
denotes cardinality.

Suppose first that there exists a $v$-chain $\alpha_1>\ldots>\alpha_t$
of elements of $\mathfrak Sw$ as in the statement.   Set
$y:=s_{\alpha_1}\cdots s_{\alpha_t}v$ and
$u:=s_{\beta_1}\cdots s_{\beta_t}v$.   Clearly $w\geq y$
(see Remark~\ref{rsw}~(2)).   To show that $w$ dominates
$\beta_1>\ldots>\beta_t$ it therefore suffices to show $y\geq u$.

Let $l$ be any integer.    We have
\begin{eqnarray*}
u^l&=&\left(v^l\setminus\left\{c_1,\ldots,c_t\right\}^l\right)
		\cup\left\{r_1,\ldots,r_t\right\}^l
		\quad\quad \mbox{\begin{rm} and \end{rm}}
		\quad\quad \\
y^l&=&\left(v^l\setminus\left\{C_1,\ldots,C_t\right\}^l\right)
		\cup\left\{R_1,\ldots,R_t\right\}^l
						\end{eqnarray*}
From the hypothesis it immediately follows that
\[
	\left|\left\{c_1\ldots,c_t\right\}^l\right|\leq
	\left|\left\{C_1\ldots,C_t\right\}^l\right|
		\quad\quad \mbox{\begin{rm} and \end{rm}}
		\quad\quad
	\left|\left\{r_1\ldots,r_t\right\}^l\right|\geq
	\left|\left\{R_1\ldots,R_t\right\}^l\right|
						\]
Thus $\card{u^l}\geq\card{y^l}$  and we are done
(implicitly used here are the facts that $\{c_1,\ldots,c_t\}$,
$\{C_1,\ldots,C_t\}$ are subsets of $v$ and $\{r_1,\ldots,r_t\}$,
$\{R_1\ldots,R_t\}$ are disjoint from $v$).

To prove the converse,  we proceed by induction on $t$.
Let us isolate the case $t=1$ as a separate statement:
\begin{lemma}ma\label{lsubldom}
Let $\beta=(r,c)$ be an element of ${\mathfrak N}^v$ and $w$ an element
of $I(d,n)$ such that $w\geq s_\beta v$.   Then there exists
an element $(R,C)$ in the distinguished monomial $\mathfrak Sw$
associated to $w$ such that $C\leq c$ and $r\leq R$.
\end{lemma}
\begin{proposition}oof
Consider the set of elements $(A,B)$ of $\mathfrak Sw$ such that
$B\leq c<A$.   We claim that this set is non-empty.  To see
this,   consider $w^c$ and $u^c$,  where $u:=s_\beta v$.
Clearly $u^c=v^c\setminus\{c\}$.   If the set were empty,
we would have $\card{w^c}=\card{v^c}$, and so $\card{w^c}
\gneq\card{u^c}$,  a contradiction to the hypothesis that
$w\geq u$.

Since $\mathfrak Sw$ is distinguished,  the set of such elements
$(A,B)$ form a $v$-chain.     Let $(R,C)$ be the head of this
$v$-chain.     We claim that $r\leq R$.    To see this,
consider $w^R$ and $u^R$.     Since $\mathfrak Sw$ is distinguished,
we have $\card{w^R}=\card{v^R}$.   If $R<r$,  then
$u^R=v^R\setminus\{c\}$,   and so $\card{w^R}\gneq\card{v^R}$,
a contradiction to the hypothesis that $w\geq u$.\end{proposition}oof

Now suppose that $w$ dominates $\beta_1>\ldots>\beta_t$.
Then $w\geq s_{\beta_1}\cdots s_{\beta_t}v\geq s_{\beta_1}v$
(see Remark~\ref{rsw}).    By the lemma above,   there exists
$(R,C)$ in $\mathfrak Sw$ with $C\leq c_1$ and $r_1\leq R$.  Since
$\mathfrak Sw$ is distinguished,  the set of such $(R,C)$ forms a
$v$-chain.    Let $\alpha_1=(R_1,C_1)$ be the head of this
$v$-chain.

Let $\tilde{w}$ be the element of $I(d,n)$ associated to the
distinguished subset $\mathfrak Sw\setminus\{(R_1,C_1)\}$ of ${\mathfrak N}^v$.
We will show below that $\tilde{w}$ dominates $\beta_2>\ldots>\beta_t$.
Assuming this for the moment,  we obtain by induction on $t$
(the case $t=1$ being the lemma above) a $v$-chain $\alpha_2=
(R_2,C_2)>\ldots>\alpha_t=(R_t,C_t)$ with $C_j\leq c_j$ and $r_j\leq
R_j$.  Since $\mathfrak Sw$ is distinguished,   it follows easily from
our choice of $\alpha_1$ that $\alpha_1>\alpha_2$, and we are done.

To prove that $\tilde{w}\geq s_{\beta_2}\cdots s_{\beta_t}v$, we
set $y:=s_{\beta_2}\cdots s_{\beta_t}v$ and verify that, for
every integer $l$, $\card{\tilde{w}^l}\leq\card{y^l}$:
\begin{itemize}
\item
	For $l<c_2$, we have $y^l=v^l$.  Since $\tilde{w}\geq v$,
	it follows that $\card{\tilde{w}^l}\leq\card{y^l}$.
\item
	For $c_2\leq l<r_1$,  we have $y^l=u^l\cup\{c_1\}$,
	so that $\card{y^l}=\card{u^l}+1$,  and $\tilde{w}^l
	=w^l\cup\{C_1\}$.  Since $w\geq u$, it follows that
	$\card{\tilde{w}^l}=\card{w^l}+1\leq\card{u^l}+1=\card{y^l}$.
\item
	For $l\geq r_2$,  we have $\card{y^l}=\card{v^l}$. Since
		$\tilde{w}\geq v$,  it follows that $\card{
			\tilde{w}^l}\leq\card{y^l}$.~$\Box$
			\end{itemize}\end{prooftwo}

\begin{corollary}\label{cldom}
Let $w$ be an element of $I(d,n)$ and $\mathfrak Sw$ the corresponding
distinguished subset of ${\mathfrak N}^v$.  For a positive integer $j$,
let $\mathfrak S_w^j$ denote the subset of $\mathfrak Sw$ of those elements
that are $j$-deep,  and $w^j$ the corresponding element of
$I(d,n)$.  Let $\beta_1=(r_1,c_1)>\ldots>\beta_t=(r_t,c_t)$ be
a $v$-chain.
\begin{enumerate}
\item
	If $w^k$ dominates $\beta_1>\ldots>\beta_t$,  then $w^{k+1}$
	dominates $\beta_2>\ldots>\beta_t$, $w^{k+2}$ dominates
	$\beta_3>\ldots>\beta_t$, and so on.
\item
                If, for integers $l>k$,  there exists $(R,C)$ in $\mathfrak Sw^l$ such
                that $C\leq c_1$ and $r_1\leq R$,  and $w^{k+1}$ does not dominate
                $\beta_1>\dots>\beta_t$,  then $w^{k+2}$ does not dominate
               $\beta_2>\dots>\beta_t$,   $w^{k+3}$ does not dominate
                $\beta_3>\dots>\beta_t$,   and so on until, finally,
                $w^{l+1}$ does not dominate
                $\beta_{l-k+1}>\dots>\beta_t$.

\end{enumerate}
\end{corollary}
\begin{proposition}oof
(1)~~Choose a $v$-chain $\alpha_1>\ldots>\alpha_t$ in $\mathfrak S_w^k$
as in the lemma.  Note that $\{\alpha_2,\ldots,\alpha_t\}
\subseteq\mathfrak S_w^{k+1}$,  $\{\alpha_3,\ldots,\alpha_t\}\subseteq
\mathfrak S_w^{k+2}$, and so on.   Now use the ``if'' part of the
lemma.

(2)~~The proof is based on the following claim:  given an element
$\beta$ of ${\mathfrak N}^v$ and an integer $j$,  there exists at most one
element of $\alpha$ of $\mathfrak S_{w,j}$ such that $\alpha>\beta$.  To prove
the claim,   note that, on the one hand,  since $\mathfrak Sw$ is distinguished,
the set of its elements $\alpha$ such that $\alpha>\beta$ form a $v$-chain,
but, on the other hand,   no two elements of $\mathfrak S_{w,j}$ are comparable.

It is enough to do the case when $l=k+1$.  So let $l=k+1$.
Suppose that $w^{k+2}$ dominates $\beta_2>\ldots>\beta_t$.
By the lemma above,  there exists a $v$-chain $(R_2,C_2)>\ldots
>(R_t,C_t)$ in $\mathfrak S_w^{k+2}$ such that $C_j\leq c_j$ and $r_j\leq R_j$
for $2\leq j\leq t$.     Choose $(R_1,C_1)$ in $\mathfrak S_{w,k+1}$ such that
$(R_1,C_1)>(R_2,C_2)$.  If $(R,C)$ belongs to $\mathfrak S_w^{k+2}$,  then
replacing it with an element $(R',C')$ of $\mathfrak S_{w,k+1}$ such that
$(R',C')>(R,C)$,  we may assume that $(R,C)$ belongs to $\mathfrak S_{w,k+1}$.

Now we have $(R_1,C_1)>\beta_2$ and $(R,C)>\beta_2$.  It follows from
the claim above that $(R_1,C_1)=(R,C)$.  Thus $C_1\leq c_1$ and
$r_1\leq R_1$, and, by the ``if'' part of the lemma above,  it follows
that $w^{k+1}$ dominates $\beta_1>\ldots>\beta_t$.\end{proposition}oof

\subsection{The description of $\pi$}\label{sspi}
In what follows,
when we speak of a ``subset'' $\mathfrak S_1$ of a
multiset $\mathfrak S$,  it should be understood that we have in mind a subset of the
set underlying $\mathfrak S$ and that $\mathfrak S_1$ is the collection
with multiplicities of those elements of $\mathfrak S$ that belong to the
underlying subset.    A similar comment
applies to ``partition'' of a multiset.

We now specify the map $\pi$.
Let $\mathfrak S$ be a non-empty monomial in the elements of ${\mathfrak N}^v$.
We partition $\mathfrak S$
in two stages.  First we partition $\mathfrak S$ into subsets
$\mathfrak S_1,\ldots,\mathfrak S_k$,   where $k$ is the largest length of
a $v$-chain in $\mathfrak S$:   $\beta\in\mathfrak S$ belongs to $\mathfrak S_j$
if it is $j$-deep but not $(j+1)$-deep.

Clearly $\mathfrak S_1,\ldots,\mathfrak S_k$ form a partition of $\mathfrak S$,
and no two distinct elements belonging to the same
$\mathfrak S_j$ are comparable.

Now we partition each $\mathfrak S_j$ into subsets called
{\em blocks} as follows.   We arrange the elements of $\mathfrak S_j$
in non-decreasing order of their row numbers (all arrangements are from left
to right; and elements occur with their respective multiplicities).

Among those with
the  same row number,  the arrangement is by non-decreasing
order of column numbers.   By the incomparability of any two
distinct elements of $\mathfrak S_j$,    the column numbers are
also now arranged in non-decreasing order.   If $(r,c),(R,C)$
are consecutive members in this arrangement,   we demand that
the two belong to the same or different blocks accordingly as
$r>C$ or $r<C$ ($r\neq C$, for $C$ belongs and $r$ does not to
$\{v_1, \ldots, v_d\}$).    More formally,  two consecutive
members $(r,c),(R,C)$ in the arrangement are said to be {\em related}
if $r>C$.    The blocks are the equivalence classes
of the smallest equivalence relation containing the above relations.

Let us now concentrate on a single block $\frak B$ of some $\mathfrak S_j$.
Let \begin{eqnarray}\label{eblock}
	(r_1,c_1), \ldots, (r_p,c_p)	\end{eqnarray}
be the elements of $\frak B$ written in non-decreasing order of
both row and column numbers (in all such arrangements
the elements occur with their
respective multiplicities).    We set $w(\frak B):= (r_p,c_1)$,
$\frak B'$ to be the monomial
\begin{eqnarray} \label{eblockprime}
		\left\{(r_1,c_2), (r_2,c_3), \ldots,
		(r_{p-2},c_{p-1}), (r_{p-1}, c_p)\right\} \\

\label{emonprime}
\mathfrak S_j':=\bigcup\limits_{\mathfrak B} \mathfrak B'   \quad\quad
\mbox{\begin{rm} and \end{rm}}\quad\quad
\mathfrak S':=
 \bigcup\limits_{j=1}^k \mathfrak S_j'

			\end{eqnarray}
where the index $\frak B$ runs over all
blocks of $\mathfrak S_j$. 

It follows from Corollary~\ref{cltwoone} below that
\[      \left\{w(\mathfrak B){\,|\,}\mbox{\begin{rm} $\mathfrak B$ is a block of $\mathfrak S$ \end{rm}}
                                                                                                                \right\}\]
satisfies conditions (A) and (B) of subsection~\ref{sspreparation}.  Let $w$
be the corresponding element of $I(d,n)$ (see Proposition~\ref{psw}),  and
set
\[	\pi(\mathfrak S) := (w,\mathfrak S').		\]

\renewcommand{\arabic{figure}}{\arabic{figure}}
Let us illustrate the definition of the map $\pi$ by means of
an example.
\begin{example}\begin{rm}\label{epi}
Let $d=13$, $n\geq 25$,  and
$$v=(1,2,4,5,7,8,9,14,15,16,17,18,19).$$
A monomial $\mathfrak S$ and its decomposition into blocks is represented
in Figure 2.

\begin{figure}
\caption{A monomial $\mathfrak S$ and its decomposition into blocks}
\label{fexmon}
\end{figure}

The lattice points of the grid correspond to elements of ${\mathfrak N}^v$.
The solid dots indicate the elements that
occur with non-zero multiplicity.   The integers by the dots are
the multiplicities of the corresponding elements.   The solid lines
indicate the decomposition of $\mathfrak S$ into blocks.   There are two
blocks each in $\mathfrak S_1$, $\mathfrak S_2$, and $\mathfrak S_3$.  For example, the
blocks in $\mathfrak S_3$ are $\{(10,8),(11,8)\}$ and $\{(21,18)^2, (22,18)\}$
(the exponent $2$ indicates the multiplicity);   $\mathfrak S_4$ consists
of just one block, namely, $\{(10,9)^3\}$.

Let $\pi(\mathfrak S)=(w,\mathfrak S')$.  Since $\mathfrak S$ has  $7$ blocks,
$\mathfrak S_w$ has $7$ elements:
\[
	\mathfrak S_w=\left\{(10,9), (11,8), (12,4), (13,1),
 (22,18), (23,16), (25,14)\right\}		\]
The monomial $\mathfrak S'$ is represented in
Figure~3.\ $\Box$\end{rm}\end{example}

\begin{figure}
\caption{The monomial $\mathfrak S^\prime$ where $\mathfrak S$ is the monomial of Figure~2}
\label{fexmonprime}
\end{figure}

We now note some properties of the above construction that will be
used in the proofs of Propositions \ref{ppi} and \ref{ppiphi}.
\begin{lemma}\label{lone}
If $\mathfrak B_1,\ldots, \mathfrak B_l$ are the blocks in order
 from left to right of  some $\mathfrak S_j$,   and
$w(\mathfrak B_1)=(R_1,C_1)$,
$w(\mathfrak B_2)=(R_2,C_2)$,
$\ldots$,
$w(\mathfrak B_l)=(R_l,C_l)$,
then \[ C_1<R_1<C_2<R_2<\ldots<R_{l-1}<C_l<R_l	\]
\end{lemma}
\begin{proposition}oof
From the definition of $w(\mathfrak B)$,  it is clear that
$C_1<R_1$,  $C_2<R_2$, etc.   Note that $C_2$ is the least
column index in $\mathfrak B_2$ and $R_1$ is the greatest row
index in $\mathfrak B_1$.   From the way we divided $\mathfrak S_j$
into blocks,  it is clear that $R_1<C_2$.  Similarly
$R_2<C_3$, etc.\end{proposition}oof
\begin{lemma}ma\label{lssprime}

No two
distinct elements of $\mathfrak S_j\cup\mathfrak S_j'$ are comparable.
More precisely,   if $(a,b)$ and $(c,d)$ are elements of ${\mathfrak N}^v$
with $(a,b)>(c,d)$,   then they cannot both belong to
$\mathfrak S_j\cup\mathfrak S_j'$.
\end{lemma}
\begin{proposition}oof
We can put the elements in (\ref{eblock}) and (\ref{eblockprime})
together in non-decreasing order of both row and column numbers:
\begin{eqnarray*}
(r_1,c_1), (r_1,c_2), (r_2,c_2), (r_2,c_3), (r_3,c_3),\ldots,\\
(r_{p-2},c_{p-2}), (r_{p-2},c_{p-1}), (r_{p-1},c_{p-1}),
	(r_{p-1},c_p),(r_p,c_p) 		\end{eqnarray*}
This means that distinct  elements belonging to $\mathfrak B\cup\mathfrak B'$,
where $\mathfrak B$ is a block of $\mathfrak S_j$,  are not comparable.
Let $\mathfrak B$ and $\mathfrak C$ are distinct blocks of $\mathfrak S_j$
with $w(\mathfrak B)=(R,C)$ and $w(\mathfrak C)=(S,T)$.  Using
Lemma~\ref{lone}, we may assume without loss of generality that
$C<R<S<T$.    If $(a,b)$ belongs to $\mathfrak B\cup\mathfrak B'$ and
$(c,d)$ to $\mathfrak C\cup\mathfrak C'$,  then
\[	C\leq b< a\leq R<S\leq d<c\leq T	\]
so that $(a,b)$ and $(c,d)$ are not comparable.
Note that this shows also that $\mathfrak B\cup\mathfrak B'$
and $\mathfrak C\cup\mathfrak C'$ are disjoint.\end{proposition}oof
\begin{corollary}\label{clssprime}
For $(r,c)\in\mathfrak S'$,  there exists a unique block $\mathfrak B$ of
$\mathfrak S$ with $(r,c)\in\mathfrak B'$.
\end{corollary}
\begin{proposition}oof
The existence is immediate from the definition of $\mathfrak S'$.
For the uniqueness,   let $\mathfrak B$ and $\mathfrak C$ be two distinct
blocks of $\mathfrak S$ with $(r,c)$ belonging to both $\mathfrak B'$ and
$\mathfrak C'$.    For the reason noted at the end of the proof of
the previous lemma,   $\mathfrak B$ and $\mathfrak C$ cannot belong to
the same $\mathfrak S_j$.     So suppose, without loss of generality,
that $\mathfrak B\subseteq\mathfrak S_i$, $\mathfrak C\subseteq\mathfrak S_j$, and $i<j$.
Now there exists an element of the form $(r,a)$ in $\mathfrak C$ with
$a\leq c$ (this follows from the definition of $\mathfrak C'$),  and
an $(R,C)$ in $\mathfrak S_i$ with $(R,C)>(r,a)$ (such an
element can be found at the appropriate place on a $v$-chain of
length $j$ with $(r,a)$ as tail).    But then $(R,C)>(r,c)$
and both $(R,C)$ and $(r,c)$ belong to $\mathfrak S_i\cup\mathfrak S_i'$,
a contradiction to the previous lemma.\end{proposition}oof
\begin{lemma}\label{ltwo}
Given positive integers $i<j$ and a block $\mathfrak B$ of $\mathfrak S_j$,
there exists a unique block $\mathfrak C$ of $\mathfrak S_i$ such that
$w(\mathfrak C)>w(\mathfrak B)$.

\end{lemma}
\begin{proposition}oof
Let $\mathfrak C$ and $\mathfrak Cone$ be distinct blocks of $\mathfrak S_i$
with $w(\mathfrak C)=(A,B)$, $w(\mathfrak Cone)=(A_1,B_1)$, and
$(A,B)>(r,c)$.     By Lemma~\ref{lone},
\[\mbox{\begin{rm}
either
 $B<c<r<A<B_1<A_1$ or
 $B_1<A_1<B<c<r<A$.\end{rm}}\]
In either case, we have $(A_1,B_1)\not>(r,c)$.  This proves uniqueness.

For the existence,  write $w(\mathfrak B)=(r,c)$, and
let the elements of $\mathfrak B$ in non-decreasing
order of row and column entries be
\[  (r_1,c),\ldots,(r,c_p)	\]
Let $(R,C)$ and $(R',C')$  be elements of $\mathfrak S_i$ such that
$(R,C) > (r_1,c)$ and $(R',C')>(r,c_p)$.
If $(R',C')$ either equals $(R,C)$ or appears to the left of it
in the arrangement of the elements of $\mathfrak S_i$ in non-decreasing
order of row and column entries,  then let $\mathfrak C$ be the
block of $\mathfrak S_i$ containing $(R',C')$.    Writing $w(\mathfrak C)
=(A,B)$,  we have $r<R'\leq A$ and $B\leq C'\leq C<c$,
and we are done.

So let us assume
that $(R',C')$ appears to the right of $(R,C)$  in the arrangement
of elements of $\mathfrak S_i$:
\[	\ldots,(R,C),\ldots,(s,t),\ldots,(R',C'),\ldots	\]
where $(s,t)$ denotes an arbitrary element between $(R,C)$ and $(R',C')$ that is not equal to
$(R',C')$.    We claim that $s>b$ for an element
$(a,b)$ that occurs in the above arrangement
strictly to the right of $(s,t)$.
Once the claim is proved,  it will follow that
all the elements $(R,C),\ldots,(R',C')$
belong to the same block of $\mathfrak S_i$.    Let $\mathfrak C$ be this
block and set $w(\mathfrak C)=(A,B)$.    We then have
$B\leq C<c$ and $r<R'\leq A$.

To prove the claim,  we may assume that $s<c_p$, for otherwise $C'<c_p\leq s$
and we can take $(a,b)$ to be $(R',C')$.   Let $y$ be the least
among the column indices of elements of $\mathfrak B$ subject to
$s<y$,  and let $(x,y)$ be the left most element with column
index $y$ in the arrangement of $\mathfrak B$.   It is not possible
that $(r_1,c)=(x,y)$,  for that would imply $y<x=r_1<R\leq s$,
but $s<y$ by our choice of $y$.

Now let $(x',y')$ be the element
in $\mathfrak B$ immediately to the left of $(x,y)$.
By our choice of $(x,y)$ we have $y'\leq s$.  Since $(x',y')$ and
$(x,y)$ belong to the same block $\mathfrak B$,  we have $y<x'$.

Let $(a,b)$ be an element in $\mathfrak S_i$ such that $(a,b)>(x',y')$.
We then have $s<y<x'<a$, so that $(a,b)$ appears to the right of
$(s,t)$.  Further,  we have $b<y'\leq s$, and the claim is proved.\end{proposition}oof
\begin{corollary}\label{cltwoone}
If $\mathfrak B$ and $\mathfrak B_1$ are blocks of $\mathfrak S$ with $w(\mathfrak B)=(r,c)$
and $w(\mathfrak B_1)=(r_1,c_1)$,  then exactly one of the following holds:
\begin{eqnarray*}
        c<r<c_1<r_1,&\quad\quad\quad\quad& c_1<r_1<c<r,\\
  c<c_1<r_1<r,&\quad\quad\mbox{\begin{rm}or\end{rm}}
  \quad\quad& c_1<c<r<r_1.
  \end{eqnarray*}
  \end{corollary}
  \begin{proposition}oof
  Let $j$ and $j_1$ be the integers such that $\mathfrak B\subseteq\mathfrak S_j$
  and $\mathfrak B_1\subseteq\mathfrak S_{j_1}$.   If $j=j_1$,  then it follows from
  Lemma~\ref{lone} that one of the first two possibilities holds.

  Now suppose that $j_1<j$.   Then,  by Lemma~\ref{ltwo},   there exists
  a block $\mathfrak C$ of $\mathfrak S_{j_1}$ such that $w(\mathfrak C)>w(\mathfrak B)$.
  Writing $w(\mathfrak C)=(A,B)$,  we have $B<c<r<A$.   If $\mathfrak B_1=\mathfrak C$,
  then the fourth possibility holds.   If $\mathfrak B_1\neq \mathfrak C$,  then, again
  by Lemma~\ref{lone},  either $B<A<c_1<r_1$ or $c_1<r_1<B<A$,  so
  that respectively either the first or the second possibility holds.

  If $j_1<j$,   then we see similarly that one of the first three possibilities
  holds.\end{proposition}oof

\begin{corollary}\label{cltwo}
\begin{enumerate}
\item
Let $(r,c)>(r_1,c_1)$ be elements of $\mathfrak S$, and $\mathfrak B$,
$\mathfrak B_1$ be blocks of $\mathfrak S$ such that $(r,c)\in\mathfrak B$,
and $(r_1,c_1)\in\mathfrak B_1$.  Then $w(\mathfrak B)>w(\mathfrak B_1)$.
\item
Let $(r,c)>(r_1,c_1)$ be elements of $\mathfrak S'$, and $\mathfrak B$,
$\mathfrak B_1$ be blocks of $\mathfrak S$ such that $(r,c)\in\mathfrak B'$,
and $(r_1,c_1)\in\mathfrak B_1'$.  Then $w(\mathfrak B)>w(\mathfrak B_1)$.
\end{enumerate}
\end{corollary}
\begin{proposition}oof  We prove both statements simultaneously.
Let $j$ and $j_1$ be  such that $\mathfrak B\subseteq\mathfrak S_j$
and $\mathfrak B_1\subseteq\mathfrak S_{j_1}$.  We claim that $j<j_1$.
This is clear in case (1).    In case (2),
$j\neq j_1$ by
Lemma~\ref{lssprime}.   If $j>j_1$,
then choosing an element of the form $(r,a)$ with
$a\leq c$ in $\mathfrak B$  and an element $(R,C)$ in $\mathfrak S_{j_1}$ with $(R,C)>(r,a)$, we have
$(R,C)>(r_1,c_1)$,  but this contradicts Lemma~\ref{lssprime}.
The claim is thus proved.

Write $w(\mathfrak B)=(R,C)$ and 
$w(\mathfrak B_1)=(R_1,C_1)$.   By Lemma~\ref{ltwo},  there exists
a unique block $\mathfrak C$ of $\mathfrak S_j$ with
$w(\mathfrak C)>w(\mathfrak B_1)=(R_1,C_1)$.  We will show that
$\mathfrak B=\mathfrak C$.
Write $w(\mathfrak C)=(S,T)$ and suppose that $\mathfrak B\neq\mathfrak C$.
Then, by Lemma~\ref{lone},  either  $S<T<C<R$ or $C<R<S<T$.
In the first case we have
\[
	S<C_1\leq c_1<r_1\leq  R_1<T<C\leq c<r\leq R	\]
	which is inconsistent with our hypothesis that
		$c<c_1<r_1<r$.    A similar contradiction occurs
			in the second case.\end{proposition}oof  
\begin{corollary}\label{cltwothree}
Let $\beta$ be an element of $\mathfrak S$,  $\mathfrak B$ the block of 
$\mathfrak S$ containing $\beta$,  and $\mathfrak B_1$ a block of $\mathfrak S$
with $w(\mathfrak B_1)>w(\mathfrak B)$.  Then there exists $\beta_1$
in $\mathfrak B_1$ with $\beta_1>\beta$.
\end{corollary}
\begin{proposition}oof
Let $j$ and $j_1$ be the integers such that $\mathfrak B\subseteq
\mathfrak S_j$ and $\mathfrak B_1\subseteq\mathfrak S_{j_1}$.  By Lemma~\ref{lone},
$j\neq j_1$.  Suppose $j<j_1$.  By Lemma~\ref{ltwo},  there exists
a block $\mathfrak C$ in $\mathfrak S_j$ with $w(\mathfrak C)>w(\mathfrak B_1)$,
but then $w(\mathfrak C)>w(\mathfrak B)$,  which contradicts Lemma~\ref{lone}.
Thus $j>j_1$.

Now there exists $\beta_1$ in $\mathfrak S_{j_1}$ such that $\beta_1>\beta$.
Let $\mathfrak C$ be the block of $\mathfrak S_{j_1}$ containing $\beta_1$.
By Corollary~\ref{cltwo}~(1),  $w(\mathfrak C)>w(\mathfrak B)$,
and by the uniqueness part of Lemma~\ref{ltwo}, 
$\mathfrak C=\mathfrak B_1$.\end{proposition}oof
\begin{corollary}\label{cltwofour}
Let $\mathfrak B$ be block of $\mathfrak S$ and $\beta$ an element of
$\mathfrak B$.  Then the depth of $\beta$ in $\mathfrak S$ equals the
depth of $w(\mathfrak B)$ in $\left\{w(\mathfrak B){\,|\,}\mbox{
\begin{rm}$\mathfrak B$ is a block of $\mathfrak S$\end{rm}}\right\}$.
\end{corollary}
\begin{proposition}oof
That the depth of $w(\mathfrak B)$ is not less than the depth of
$\beta$ follows from Corollary~\ref{cltwo}~(1).    That the
depth of $\beta$ is not less than that of $w(\mathfrak B)$
follows from Corollary~\ref{cltwothree}.\end{proposition}oof

\subsection{Proof of Proposition~\ref{ppi}} \label{sspiproof}
It is clear from the definition of $\mathfrak S'$ that $\degree{\mathfrak S'}$ is less
than $\degree{\mathfrak S}$ by exactly the number of blocks in $\mathfrak S$.
By Proposition~\ref{psw},  this number equals $\vdeg{w}$,   and so
statement (2) is proved.   Moreover,   this number is positive since
$\mathfrak S$ is non-empty,  and so statement (1) holds.

	To prove (3), let a $v$-chain $\beta_1>\ldots>\beta_t$
	in $\mathfrak S'$ be given.   Let $\mathfrak B_1,\ldots,\mathfrak B_t$
	be blocks of $\mathfrak S$ such that $\beta_i$ belongs to $\mathfrak B_i'$.
	(In fact,  these blocks are uniquely determined as
	shown in Lemma~\ref{clssprime},  but here we need only
	that they exist, and this is immediate from the definition
	of $\mathfrak S'$.)    It follows from Corollary~\ref{cltwo}~(2) that
	$w(\mathfrak B_1)>\ldots>w(\mathfrak B_t)$,  and then from 
	Lemma~\ref{ldom} that (3) holds.

	We now turn to the proof of (4).   That $w$ dominates
	$\mathfrak S$ follows in much the same way as statement (3):
                it uses Corollary~\ref{cltwo}~(1) in place of Corollary~\ref{cltwo}~(2).

               To prove that it is
	the minimal one that does so,  it suffices to show
	the following:  given an integer $j$, $1\leq j\leq d$,  there
	exists a $v$-chain $\alpha_1>\ldots>\alpha_t$ in $\mathfrak S$
	such that $y:=s_{\alpha_1}\cdots s_{\alpha_t}v$ satisfies
	$y_j=w_j$,  where $y_j$ and $w_j$ denote as usual the
	$j^{\mbox{\begin{rm}th\end{rm}}}$ entries of $y$ and
	$w$ as elements of $I(d,n)$.

	Fix $j$, $1\leq j\leq d$.  We will first get hold of
	a $v$-chain $\beta_1>\ldots>\beta_t$ in
        \(\mathfrak S_w:=\left\{w(\mathfrak B){\,|\,}
        \mbox{\begin{rm} $\mathfrak B$ is a block
	of $\mathfrak S$ \end{rm}}\right\}\)
	such that $u=s_{\beta_1}\cdots s_{\beta_t}v$ satisfies
	$u_j=w_j$.   Set $D:=w_j$.  Consider the subset of
	$\mathfrak S_w$ consisting of those elements $(r,c)$ for which
	$c<D\leq r$.

                Since $\mathfrak S_w$ is distinguished
                (see Corollary~\ref{cltwoone}),
                it follows that
	these elements form a $v$-chain,  say $\beta_1=(r_1,c_1)>
	\ldots>\beta_t=(r_t,c_t)$.    We have
                \begin{eqnarray}
                        c_1<\ldots<c_t<D\leq r_t<\ldots<r_1    \label{epiproofone} \end{eqnarray}
                        and $r_t=D$ if and only if $D$ is not an entry of $v$.

	Set $u:=s_{\beta_1}\cdots
	s_{\beta_t}v$.   We claim that $u_j=D=w_j$.  First note
	that $D$ occurs as an entry of  $u$:  if $D$ belongs to
	$\{v_1,\ldots,v_d\}$, then $D$ is not a column index
	in $\mathfrak S_w$  much less of any $\beta_1,\ldots,\beta_t$;
	if $D$ is a row index in $\mathfrak S_w$,  then $r_t=D$.

	Every element $\delta=(r,c)$
	of $\mathfrak S_w$ other than $\beta_1,\ldots,\beta_t$
	satisfies either $c<r<D$ or $D<c<r$,  so that $s_\delta u$
	will continue to have $D$ in the same place as $u$.  Since
	we can go from $u$ to $w$ by a sequence of multiplications by such $s_\delta$,
	the claim follows.

                Now let $\mathfrak B_1,\ldots,\mathfrak B_t$ be the blocks of $\mathfrak S$ such
                that $w(\mathfrak B_j)=\beta_j$.  To get a $v$-chain $\alpha_1>\ldots>
                \alpha_t$ in $\mathfrak S$ with the desired property,   we start by getting an
                appropriate $\alpha_t$ in $\mathfrak B_t$.  Let $a$ be the least row index
                of an element of $\mathfrak B_t$ subject to $D\leq a$.   Choose $(a,b)$
                in $\mathfrak B_t$ with $b$ being least possible.  We claim that $b<D$.

                If $(a,b)$ is the first element in
	the arrangement of elements of $\mathfrak B_t$ in non-decreasing order
	of row and column indices,  then $b=c_t$ and so $b<D$.
	If not,  then we may assume that the element $(a',b')$
	immediately to the left of $(a,b)$ is  distinct from
	$(a,b)$, and so by choice of $(a,b)$ we have $a'<D$.
	But  also $b<a'$ because both $(a',b')$ and
	$(a,b)$ are in $\mathfrak B_t$, and the claim follows.
                Set $\alpha_t=(a,b)$.

                        Now, by Corollary~\ref{cltwothree}, there exists $\alpha_{t-1}$
                        in $\mathfrak B_{t-1}$ such that $\alpha_{t-1}>\alpha_t$,
                $\alpha_{t-2}$ in $\mathfrak B_{t-2}$ such that $\alpha_{t-2}>\alpha_{t-1}$,
                and so on.  Writing $\alpha_j=(a_j,b_j)$,   we have
               \begin{eqnarray}
                       b_1<\ldots<b_t<D\leq a_t<\ldots<a_1    \label{epiprooftwo} \end{eqnarray}
               and $a_t=D$ if and only if $D$ is not an entry of $v$.

               Set $y:=s_{\alpha_1}\cdots s_{\alpha_t}v$.     We show $y_j=w_j$
               by showing that $y_j=D=u_j$.     Note first that $D$ occurs as an entry in
               $y$ for similar reasons that $D$ occurs as an entry of $u$.  Now it follows
               from equations (\ref{epiproofone}) and (\ref{epiprooftwo}) that the number
               of entries in $u$ that are less than $D$ equals the corresponding number
               for $y$ (both equal the corresponding number in $v$ reduced by $t$),
               and so $D$ occurs in the same place in $y$ as it does in $u$.

\subsection{The description of $\phi$}\label{ssphi}
We now specify the map $\phi$. Let
$(w,\frak T)$ be a pair consisting of an element $w$ of $I(d,n)$ with
$w\gneq v$  and a $w$-dominated monomial $\frak T$,  possibly empty, in ${\mathfrak N}^v$.

Let $\mathfrak S_w$ be the monomial in ${\mathfrak N}^v$ associated to $w$ as in Proposition~\ref{psw},
and $k$ be the maximum length of a $v$-chain in $\mathfrak S_w$.
For a positive integer $j$, $1\leq j\leq k$,  let $\mathfrak Swj$
be the subset of elements of $\mathfrak Sw$ that are $j$-deep.
 Letting $w^j$ be the element associated by Proposition~\ref{psw} to $\mathfrak S_w^j$,
we have $w=w^1\geq\ldots w^k\geq v$ (see Remark~\ref{rsw}).

Clearly
$\mathfrak Sw=\mathfrak Swone\supseteq\mathfrak Swtwo\supseteq\ldots\supseteq\mathfrak Swk$.

For a positive integer $j$, $1\leq j\leq k$,  let ${\frak T}^w_j$ be the subset of $\frak T$
of elements $\beta$ such that $\beta$ is the head of a $v$-chain in $\frak T$ dominated
by $w^j$ but not $w^{j+1}$  (we set $w^{k+1}=v$),  and every $v$-chain in $\frak T$
with head $\beta$ is dominated by $w^j$.   The ${\frak T}^w_j$ form a partition of
$\frak T$ (some of the ${\frak T}^w_j$ could be empty).    Two distinct elements belonging
to the same ${\frak T}^w_j$ are not comparable:  if $\beta>\beta'$  and $\beta'$ belongs
to ${\frak T}^w_j$,   choose a $v$-chain $\beta'>\ldots$ in $\frak T$ that is not dominated by
$w^{j+1}$, so that, by Corollary~\ref{cldom}~(1), the $v$-chain $\beta>\beta'>\ldots$ is not dominated
by $w^j$.

We now further partition each ${\frak T}^w_j$ into subsets called {\em pieces} as follows.
Let $\mathfrak S_{w,j}$ denote the set of elements of $\mathfrak Sw$ that are $j$-deep but not
$(j+1)$-deep.    Clearly no two distinct elements of $\mathfrak S_{w,j}$ are comparable.
\begin{lemma}ma\label{pphi}
For an element $(r,c)$ of ${\frak T}^w_j$,   there exists a unique element $(R,C)$ of
$\mathfrak S_{w,j}$ such that $C\leq c$ and $r\leq R$.
\end{lemma}
\begin{proposition}oof
Let $(r,c)=(r_1,c_1)>\ldots>(r_k,c_k)$ be a $v$-chain in $\frak T$
that is dominated by $w^j$ but not $w^{j+1}$.    By Lemma~\ref{ldom},  there
exists a $v$-chain $(R_1,C_1)>\ldots>(R_k,C_k)$ of elements of $\mathfrak Swj$
with $C_i\leq c_i$ and $r_i\leq R_i$.     Note that $(R_1,C_1)$ does not belong to
$\mathfrak S_w^{j+1}$, for the former $v$-chain is not dominated by $w^{j+1}$ (we are
using Lemma~\ref{ldom} again here).   This proves
existence.

For uniqueness,  let $(R,C)$ and $(R',C')$ be distinct elements of
$\mathfrak S_{w,j}$.   Since $\mathfrak S_{w,j}$ is distinguished and no two of
its distinct elements are comparable,   it follows that either
$C<R<C'<R'$ or $C'<R'<C<R$.    But then if $C\leq c<r\leq R$ and
$C'\leq c<r\leq R'$,    there is an obvious contradiction.\end{proposition}oof

The pieces of ${\frak T}^w_j$ are indexed by $\mathfrak S_{w,j}$.    Let  $\beta=(R,C)$ in $\mathfrak S_{w,j}$.
The corresponding piece $\mathfrak P_\beta$ of ${\frak T}^w_j$ consists,
by definition, of all those $(r,c)$ in ${\frak T}^w_j$
with $r\leq R$ and $C\leq c$.   Of course, some of these pieces could be empty.

Let us arrange the elements of $\mathfrak P_\beta$ in non-decreasing order of the row entries;
among those with equal row entries the arrangement is by non-decreasing order of
column entries.     Since no two distinct elements of ${\frak T}^w_j$ are comparable,
the column entries are also now in non-decreasing order.   Suppose the arrangement is
\begin{eqnarray}\label{epiece}
(r_1,c_1), (r_2,c_2),\ldots, (r_p,c_p)		\end{eqnarray}
Note that $C\leq c_1$,  and $r_p\leq R$.     Let $\mathfrak P_\beta^*$ denote the monomial
\begin{eqnarray}\label{epiecestar}
	\left\{(r_1,C), (r_2,c_1),\ldots, (r_p,c_{p-1}), (R,c_p)\right\}.
					\end{eqnarray}
 Set
\[
(\frak T^w_j)^*:=\bigcup\limits_{\mathfrak S_{w,j}}\mathfrak P_\beta^*
\quad\quad\mbox{ {\rm and} } \quad\quad
\phi(w,\frak T):=\bigcup\limits_j 
(\frak T^w_j)^*. 		\]
This finishes the description of $\phi$.

The following lemma
will be used in the proof of Proposition~\ref{ppiphi}.  Its
statement and proof mirror those of Lemma~\ref{lssprime}.
\begin{lemma}ma\label{lppstar}
No two distinct elements of $\frak T^j_w\cup(\frak T_w^j)^*$ are comparable.

  In particular, for a given $\beta$ in $\mathfrak S_w$, no two distinct
elements of $\mathfrak P_\beta\cup\mathfrak P_\beta^*$ are comparable.
\end{lemma}
\begin{proposition}oof
We can put the elements in (\ref{epiece}) and (\ref{epiecestar})
together in non-decreasing order of both row and column numbers:
\begin{eqnarray*}
(r_1,C), (r_1,c_1), (r_2,c_1), (r_2,c_2), \ldots,\\
(r_{p},c_{p-1}), (r_p,c_p),  (R,c_p)		\end{eqnarray*}
This means that distinct  elements belonging to $\mathfrak P_\beta
\cup\mathfrak P_\beta^*$,
where $\mathfrak P_\beta$ is a piece of $\frak T_w^j$,  are not comparable.
If $\alpha=(R,C)$ and $\beta=(S,T)$ are distinct elements
of $\mathfrak S_{w,j}$,  then, since $\mathfrak S_{w,j}$ is distinguished and no two
of its distinct elements are comparable,
we may assume without loss of generality that
$C<R<S<T$.    If $(a,b)$ belongs to $\mathfrak P_\alpha\cup\mathfrak P_\alpha^*$ and
$(c,d)$ to $\mathfrak P_\beta\cup\mathfrak P_\beta^*$,  then
\[	C\leq b< a\leq R<S\leq d<c\leq T	\]
so that $(a,b)$ and $(c,d)$ are not comparable, and we are done.
Note that this shows also that $\mathfrak P_\alpha\cup\mathfrak P_\alpha^*$
and $\mathfrak P_\beta\cup\mathfrak P_\beta^*$ are disjoint.\end{proposition}oof

\subsection{Proof of Proposition~\ref{ppiphi}} \label{ssphipi}
We now turn to the proof of Proposition~\ref{ppiphi}.
We first show that $\phi\circ\pi$ is the identity.

Let $\mathfrak S$ be a monomial in ${\mathfrak N}^v$,  and $(w,\mathfrak S')$ its
image under $\pi$.    To show that $\phi(w,\mathfrak S')=\mathfrak S$,
it suffices to prove the following claim:   for $\beta\in\mathfrak Sw$,
if $\mathfrak B_\beta$ is the block of $\mathfrak S$ such that $w(\mathfrak B_\beta)
=\beta$,  and $\mathfrak P_\beta$
the piece of $(w,\mathfrak S')$ corresponding to $\beta$,  then
$\mathfrak B'_\beta=\mathfrak P_\beta$.    Given the claim,   we evidently
have $\mathfrak P_\beta^*=\mathfrak B_\beta$, and so
\[
	\phi(w,\mathfrak S')=\bigcup\limits_{\beta\in\mathfrak Sw}\mathfrak P_\beta^*
		=  \bigcup\limits_{\beta\in\mathfrak Sw}\mathfrak B_\beta = \mathfrak S.	\]

To prove the claim,  it suffices to show that $\mathfrak B'_\beta\subseteq
\mathfrak P_\beta$,  for then, since $\{\mathfrak P_\beta{\,|\,}\beta\in\mathfrak Sw\}$
is a partition of $\mathfrak S'=\cup_\beta\mathfrak B'_\beta$,  equality follows.

Let $(r,c)$ be an element of $\mathfrak B'_\beta$.  Write $\beta=(R,C)$,
and let $j$ denote the depth of $\beta$ in $\mathfrak Sw$.  It follows from the
definition of $\mathfrak B'_\beta$ that $C\leq c$ and $r\leq R$, and
so it suffices to show that $(r,c)$ belongs to ${\frak T}^w_j$, where
we write $\frak T$ instead of $\mathfrak S'$ for notational convenience.

\begin{remark}\begin{rm}\label{rphipi}
By Corollary~\ref{cltwofour},  $\mathfrak B_\beta\subseteq\mathfrak S_j$ so that
$(r,c)$ belongs to $\mathfrak S_j'$.
\end{rm}\end{remark}

We first show 

that every $v$-chain in $\frak T$ with head $(r,c)$ is dominated
by $w^j$.    Let $(r,c)=(r_1,c_1)>\ldots>(r_h,c_h)$ be any $v$-chain in $\frak T$
with head $(r,c)$.    Letting $\beta_i=(R_i,C_i)$ be the element of $\mathfrak Sw$ such that
$(r_i,c_i)$ belongs to $\mathfrak B_{\beta_i}'$ (see Corollary~\ref{clssprime}), it follows from
the definition of $\mathfrak B_{\beta_i}'$ that
$C_i\leq c_i$ and $r_i\leq R_i$.
By Corollary~\ref{cltwo}~(2),  we have $\beta=\beta_1>\ldots>\beta_h$.
Since $\beta$
is $j$-deep,  so are $\beta_2,\ldots,\beta_h$,  and thus $\beta_1,\ldots,\beta_h$
belong to $\mathfrak Swj$.   
By Lemma~\ref{ldom},  we conclude that $w^j$ dominates the $v$-chain
above with head $(r,c)$.

We now construct a $v$-chain with head $(r,c)$ that is not
dominated by $w^{j+1}$.
For this we prove the following lemma.
\begin{lemma}ma
If $\delta=(A,B)$  belongs to $\mathfrak S_{w,j+1}$  with  $B\leq c$ and $r\leq A$.
then there exists $(a,b)\in\mathfrak B_\delta'$ such that $(r,c)>(a,b)$.
\end{lemma}
\begin{proposition}oof

By Corollary~\ref{cltwofour}, $\mathfrak B_\delta\subseteq\mathfrak S_{j+1}$.
Since $w(\mathfrak B_\delta)=\delta=(A,B)$,  three exists an element of $\mathfrak S_{j+1}$
of the form $(A,C)$.    We must have $c<C$,  for otherwise choosing $(x,y)$ in
$\mathfrak S_j$ with $(x,y)>(A,C)$,  we have $(x,y)>(r,c)$,  but distinct elements of
$\mathfrak S_j\cup\mathfrak S_j'$ are not comparable (Lemma~\ref{lssprime}).    Let $(A'b)$ be
the

element of $\mathfrak S_{j+1}$ such that $b$ is the least with the property that
$c<b$, and among those with column index $b$ the least row index
possible is $A'$.   In the arrangement of elements of $\mathfrak S_{j+1}$ in
non-decreasing order of row and column entries,  there is a portion that
looks like this:
\[
		\ldots,(a,d),(A',b),\ldots		\]
Since there exists an element in $\mathfrak B_\delta$ (and so in $\mathfrak S_{j+1}$)
with column index $B$,   and we have $B\leq c\leq b$,  it follows that $(A',b)$ is
not the left most element, and so we may assume that $(a,d)\neq(A',b)$.  By choice
of $(A',b)$,  we have $d\leq c$.  If now $r\leq a$, choosing

$(x,y)$ in $\mathfrak S_j$ with $(x,y)>(a,d)$,   we get $(x,y)>(r,c)$,  but no two distinct
elements of $\mathfrak Sj\cup\mathfrak S_j'$ are comparable (Remark~\ref{rphipi} above and
Lemma~\ref{lssprime}).   Thus $a<r$,  so that the element
$(a,b)$ of $\mathfrak S_{j+1}'$ satisfies $(r,c)>(a,b)$.\end{proposition}oof

We now proceed by decreasing induction on $j$ to obtain
a $v$-chain with the desired property.    If $j=k$  (where $k$ is the
depth of $\mathfrak Sw$),  then $w^{j+1}=v$,  and $(r,c)$ is not dominated by $v$.
For $j<k$,  if a $\delta$ as in the hypothesis of
the lemma does not exist,  then $(r,c)$
by itself is not dominated by $w^{j+1}$.   Assuming such a $\delta$ exists,
let $(a,b)$ be as in the conclusion of the lemma.
By induction there exists a $v$-chain $(a,b)>\ldots$ in $\mathfrak S'$ that is not
dominated by $w^{j+2}$.   The $v$-chain $(r,c)>(a,b)>\ldots$ is then not
dominated by $w^{j+1}$ (see Corollary~\ref{cldom}~(1)),
and the proof that
$\phi\circ\pi$ is the identity is complete.

We now turn to showing that $\pi\circ\phi$ is the identity.
Let $(w,\frak T)$ be a pair consisting of an element $w\gneq v$
of $I(d,n)$ and a $w$-dominated monomial $\frak T$ in ${\mathfrak N}^v$.
Let $\mathfrak S=\phi(w,\frak T)$.     To prove that $\pi(\mathfrak S)=(w,\frak T)$,
it suffices to show that, for any piece $\mathfrak P$ of
$(w,\frak T)$, $\mathfrak P^*$ is a block of $\mathfrak S$.
This in turn follows from the following two assertions (recall that, for
$\beta\in\mathfrak Sw$, $\mathfrak P_\beta$ denotes the piece of $(w,\frak T)$
indexed by $\beta$):
\begin{enumerate}
	\item
		For $\beta\in\mathfrak Sw$,  there exists a block
		$\mathfrak B$ of $\mathfrak S$ such that
		$\mathfrak P_\beta^*\subseteq\mathfrak B$ (this block is
		then uniquely determined, for $\mathfrak P_\beta^*$
		is non-empty and the blocks are disjoint).

	\item
		If $\beta\neq\beta'$ are elements of $\mathfrak Sw$,
                                and $\mathfrak B$, $\mathfrak B'$  are the blocks

		determined as in (1) respectively by $\beta$
		and $\beta'$, then $\beta\neq\beta'$. 
\end{enumerate}
To see why it suffices to prove the above assertions, we fix an element
$\beta$ of $\mathfrak S_w$,  let $\mathfrak P_\beta$ be the piece of $(w,\frak T)$
corresponding to $\beta$,   let $\mathfrak B$ be the block of $\mathfrak S$ as in (1),
and show that $\mathfrak P_\beta=\mathfrak B$.

 Given $(r,c)\in\mathfrak B$,  since $\mathfrak S:=\cup_{\beta\in\mathfrak Sw}
\mathfrak P_\beta^*$ by definition of $\phi$,  there is $\beta'$ in
$\mathfrak Sw$ such that $(r,c)\in\mathfrak P_{\beta'}^*$, and by (1) there
is a $\mathfrak B'$ such that $\mathfrak P_{\beta'}^*\subseteq\mathfrak B'$,
but then $\mathfrak B=\mathfrak B'$ since $\mathfrak B\cap\mathfrak B'$ contains
$(r,c)$ and is therefore non-empty (the blocks form a partition
of $\mathfrak S$),  which means $\beta=\beta'$ by (2), so that
$(r,c)\in\mathfrak P_\beta^*$.

To prove the assertions above,  we make use of the following
lemma:
\begin{lemma}ma\label{lfour}

Let $\beta$ and $\beta'$  be elements of $\mathfrak Sw$, and $(r,c)$
an element of $\mathfrak P_\beta^*$.   Then there exists $(r',c')$
in $\mathfrak P_{\beta'}^*$  with $(r',c')>(r,c)$ if and only if $\beta'>\beta$.
\end{lemma}
\begin{proposition}oof
Let us write $\beta=(R,C)$ and $\beta'=(R',C')$.
Let $j$ and $j'$ denote respectively the depths of $\beta$
and $\beta'$ in $\mathfrak Sw$.
It is clear from the definition of $\mathfrak P_\beta^*$ that $r\leq R$ and $C\leq c$.

First suppose that $\beta'>\beta$. We then have
$R<R'$, $C'<C$,   and $r\leq  R$, $C\leq c$ , 
so that $r<R'$.
 There exists an element in $\mathfrak P_{\beta'}^*$ with row
index $R'$,  say $(R',a)$.   Let $(r',c')$ be the  element
of $\mathfrak P_{\beta'}^*$ such that $r'$ is least with the property
that $r<r'$,   and among those with row index $r'$ the least possible
column index is $c'$.  If $c'<c$,  then $(r',c')$ has the desired
property.   So it is enough to assume that $c\leq c'$
and arrive at a contradiction.

In the arrangement of elements of $\mathfrak P_{\beta'}^*$ in non-decreasing
order of row and column indices,  there is a portion that looks like
this:
\[	\ldots,(a,b),(r',c'),\ldots		\]
Since $C'<c'$  (for $C'<C\leq c\leq c'$) and the first element of
$\mathfrak P_{\beta'}^*$ has $C'$ for its column index,  it follows
that $(a,b)$ exists,  and so we may assume that $(a,b)\neq(r',c')$.
By choice of $(r',c')$,  it follows that $a<r'$, and further
that $a\leq r$.

We now set things up for an application of Corollary~\ref{cldom}.  To this
end, note that $(a,c')$ is an element of $\mathfrak P_{\beta'}$ with
$C\leq c\leq c'$ and $a\leq r\leq R$.   Since $\beta'>\beta$,  we have $j'<j$.  Since
$(a,c')$ belongs to $\mathfrak P_{\beta'}\subseteq\frak T_{j'}^w$,  there
exists a $v$-chain
$(a,c')=\alpha_1>\alpha_2>\ldots$ in $\frak T$ with head $(a,c')$
that is dominated by $w^{j'}$ but not by $w^{j'+1}$.
Now, by Corollary~\ref{cldom},  it follows that
$\alpha_2>\alpha_3>\ldots$
is dominated by $w^{j'+1}$ but not by $w^{j'+2}$,
$\alpha_3>\alpha_4>\ldots$
is dominated by $w^{j'+2}$ but not by $w^{j'+3}$, and so on,
so that
$\alpha_{j-j'+1}>\ldots$
is dominated by $w^{j}$ but not by $w^{j+1}$.
Further,  every $v$-chain  with head $\alpha_{j-j'+1}$ is dominated
by $w^j$, for otherwise by prefixing $\alpha_1>\ldots>\alpha_{j-j'}$ we would
get a $v$-chain with head $(a,c')$ that is not dominated by $w^{j'}$ (again using
Corollary~\ref{cldom}), a contradiction.
Writing $\alpha_{j-j'+1}=(x,y)$,  we have $C\leq c\leq c'<y$
and $x<a\leq r\leq R$,  so that $\beta>(x,y)$.  Thus $(x,y)$ belongs
to $\mathfrak P_\beta$.  We also have $(r,c)>(x,y)$,  but this is a
contradiction since distinct elements of $\mathfrak P_\beta\cup
\mathfrak P_{\beta}^*$ are not comparable (Lemma~\ref{lppstar}),
and the proof of the ``if'' part is complete.

For the converse,  let $(r',c')$ be in $\mathfrak P_{\beta'}^*$
with $(r',c')>(r,c)$.   
Since $\beta$ and $\beta'$ belong to $\mathfrak S_w$ and $\mathfrak S_w$
is distinguished, it follows
that one of the following four possibilities holds:
\begin{eqnarray*}
	 C'<C<R<R', &  \\
	C<C'<R'<R,  \quad
	C<R<C'<R', & \quad
	C'<R'<C<R,  		\end{eqnarray*}
What we want to show is precisely that the first possibility holds.
It therefore suffices to rule out the last three possibilities.

In case (3),   we have $c<r\leq R<C'$ and $C'\leq c'<c$,
a contradiction.   In case (4),  we have $c<r< r'\leq
R'<C$ and $C\leq c$,  a contradiction.

Now suppose that $C<C'<R'<R$.  We have $j'>j$ since
$\beta>\beta'$.  Since
$r<r'\leq R'<R$,  it follows from the way $\mathfrak P_\beta^*$ is
obtained from $\mathfrak P_\beta$ that there exists an element
$(r,a)$ in $\mathfrak P_\beta$ with
$c\leq a$.
Let $(r,a)=\alpha_1>\alpha_2>\ldots$ be a $v$-chain in $\frak T$
with head $(r,a)$
that is dominated by $w^{j}$ but not by $w^{j+1}$.
Note that $C'\leq c'<c\leq a$ and $r<r'\leq R'$.
By Corollary~\ref{cldom}, it follows that
$\alpha_2>\alpha_3>\ldots$
is dominated by $w^{j+1}$ but not by $w^{j+2}$,
$\alpha_3>\alpha_4>\ldots$
is dominated by $w^{j+2}$ but not by $w^{j+3}$, and so on,
so that
$\alpha_{j'-j+1}>\ldots$
is dominated by $w^{j'}$ but not by $w^{j'+1}$.
Now $\alpha_{j'-j+1}$ belongs to $\mathfrak P_{\beta'}$,
and $(r',c')>(r,a)>\alpha_{j'-j+1}$,  but this is a
contradiction since no two distinct elements of $\mathfrak P_{\beta'}\cup
\mathfrak P_{\beta'}^*$ are comparable (Lemma~\ref{lppstar}).\end{proposition}oof

It follows immediately from the lemma that $\mathfrak P_\beta^*
\subseteq\mathfrak Sj$ where $j$ is the depth of $\beta$ in $\mathfrak Sw$.
That all of $\mathfrak P_\beta^*$ is contained in a single block
of $\mathfrak Sj$ follows immediately from the definition of
$\mathfrak P_\beta^*$.   This proves (1).

Let us now prove (2).   Suppose that $j$ and $j'$ are
respectively the depths of $\beta$ and $\beta'$ in $\mathfrak Sw$.

From the lemma we have $\mathfrak P_\beta^*\subseteq\mathfrak Sj$ and
$\mathfrak P_{\beta'}^*\subseteq\mathfrak S_{j'}$, so $\mathfrak B\subseteq\mathfrak Sj$
and $\mathfrak B'\subseteq\mathfrak S_{j'}$.
Suppose that $j\neq j'$.
Then, since
$\mathfrak B$ and $\mathfrak B'$ are non-empty, and $\mathfrak Sj$ and
$\mathfrak S_{j'}$ are disjoint, it follows that
$\mathfrak B\neq\mathfrak B'$.    So suppose that $j=j'$.
Writing $\beta=(R,C)$ and $\beta'=(R',C')$,  we may
assume without loss of generality that $C<R<C'<R'$.
For $(r,c)$ in $\mathfrak P_\beta^*$ and $(r',c')$ in $\mathfrak P_{\beta'}^*$,
we have $r\leq  R<C'\leq c'$, so that,
by the definition of the partition of $\mathfrak S_j$ into blocks, $\mathfrak B\neq\mathfrak B'$.
This finishes the proof that $\phi\circ\pi$ is the identity
and so also that of Proposition~\ref{ppiphi}.

\section{Interpretations}\label{sinterpretation}
Fix elements $v,w$ in $I(d,n)$ with $v\leq w$. 
It follows from Corollary~\ref{cmain} that the
multiplicity of the Schubert variety $X_w$ in
the Grassmannian $G_{d,n}$ at the point $e^v$ can be
interpreted as the cardinality of a certain set
of non-intersecting lattice paths.    We first
illustrate this by means of two examples and
then provide a justification for the interpretation.
In the case $v=(1,\ldots,d)$,  this interpretation
is due to Herzog and Trung \cite[Theorem~3.3]{ht}.

\begin{example}\begin{rm}\label{eone}
Let $d=14$, $n\geq 27$,  
\begin{eqnarray*}
v&=&(1,2,3,4,5,10,11,12,13,18,19,20,21,22),
\mbox{\begin{rm} and \end{rm}}\\
w&=&(1,4,5,9,12,13,16,17,19,22,24,25,26,27)\end{eqnarray*}
so that 
\[
\mathfrak S_w=\left\{(9,3), (16,11), (17,10), (24,21), (25,20),  (26,18),
			(27,2) \right\}	\]

\begin{figure}
\caption{A tuple of non-intersecting lattice paths as in 
	Example~\ref{eone}
\label{feone}
\end{figure}

The grid depicting the points of ${\mathfrak N}^v$ is shown
in Figure 4.  The solid dots represent the
points of $\mathfrak S_w$.   From each point $\beta$
of $\mathfrak S_w$ we
draw a vertical line and a horizontal line.
Let $\beta^{\mbox{\begin{rm}start\end{rm}}}$ and $\beta^{\mbox{\begin{rm}finish\end{rm}}}$ denote respectively the points
where the vertical line and the horizontal line meet
the boundary.     For example, $\beta^{\mbox{\begin{rm}start\end{rm}}}=(14,11)$ and
$\beta^{\mbox{\begin{rm}finish\end{rm}}}=(16,13)$ for $\beta=(16,11)$.

A lattice path between a pair of such points $\beta^{\mbox{\begin{rm}start\end{rm}}}$
and $\beta^{\mbox{\begin{rm}finish\end{rm}}}$ is a sequence $\alpha_1,\ldots,\alpha_q$
of elements of ${\mathfrak N}^v$ with $\alpha_1=\beta^{\mbox{\begin{rm}start\end{rm}}}$,
$\alpha_q=\beta^{\mbox{\begin{rm}finish\end{rm}}}$,  and for $j$, $1\leq j\leq q-1$,
writing $\alpha_j=(r,c)$,  $\alpha_{j+1}$ is either
$(r+1,c)$ or $(r,c+1)$.     If  $\beta^{\mbox{\begin{rm}start\end{rm}}}=(r,c)$ and
$\beta^{\mbox{\begin{rm}finish\end{rm}}}=(R,C)$,   then $q=(R-r)+(C-c)+1$.

Write $\mathfrak S_w=\{\beta_1,\ldots,\beta_p\}$.  Now consider
the set of all $p$-tuples of paths $(\Lambda_1,\ldots,\Lambda_p)$,
where $\Lambda_j$ is a lattice path between $\beta^{\mbox{\begin{rm}start\end{rm}}}j$
and $\beta^{\mbox{\begin{rm}finish\end{rm}}}j$,  and no two $\Lambda_j$ intersect.
A particular such $p$-tuple is shown in Figure 4.
The number of such $p$-tuples is the multiplicity of 
$X_w$ at the point $e^v$.\ $\Box$\end{rm}\end{example}

\begin{example}\begin{rm}\label{etwo}
Let us draw, in a simpler case,
the pictures of all possible tuples of non-intersecting
lattice paths as defined in the above example. 
Let $d=6$, $n\geq 13$, $v=(1,2,3,8,9,10)$, and
$w=(4,6,7,10,11,13)$,  so that $\mathfrak S_w=\{(4,3), (6,2),
(7,1), (11,9), (13,8)\}$.   Figure 5 shows all
the $5$-tuples of 
non-intersecting lattice paths.  There are $9$ of them
and thus the multiplicity in this case is $9$.\ $\Box$\end{rm}\end{example}

\begin{figure}
\caption{All the tuples of non-intersecting lattice paths as in 
	Example~\ref{etwo}
\label{fetwo}
\end{figure}

Let us now see why this interpretation is justified.
Denote by $U^vw$ the set of tuples of non-intersecting lattice
paths corresponding to the pair $(v,w)$,   by $N^v_w$ the set of
maximal square-free $w$-dominated monomials in ${\mathfrak N}^v$.

There is an obvious natural map from $U^vw$ to monomials in ${\mathfrak N}^v$.
In fact,  each element of $U^vw$ can be thought of as a monomial:
each lattice path is a subset of ${\mathfrak N}^v$ and as such is a 
monomial in ${\mathfrak N}^v$;     we identify an element $\Lambda
=(\Lambda_1,\ldots,\Lambda_p)$ of $U^vw$ with the monomial
$\Lambda_1\cup\cdots\cup\Lambda_p$. 
We denote the monomial also by $\Lambda$.
Since the paths are non-intersecting,
$\Lambda$ is square-free.   We will argue below that $\Lambda$
belongs to $N^v_w$ and that this association is a bijection.
The idea is that
the block decomposition of an element of $N^v_w$ identifies it
as an element of $U^vw$.
Since all monomials $\Lambda$ have clearly the same cardinality,
the same will be true for elements of $N^v_w$.

Let us for the moment take for granted this bijection between
$U^vw$ and $N^v_w$ and justify the interpretation.
Denote by $R^v_w$ the set of maximal square-free $w$-dominated
monomials in $\mathfrak R ^v$.

If $\mathfrak S$ is an element of $R^v_w$ and $(r,c)$ an element of
$\mathfrak R ^v\setminus{\mathfrak N}^v$ not belonging to $\mathfrak S$,  then, adding
$(r,c)$ to $\mathfrak S$ would still keep it square-free and $w$-dominated,
violating its maximality.  Thus $\mathfrak S\supseteq\mathfrak R ^v\setminus
{\mathfrak N}^v$,  and the map $\mathfrak S\mapsto\mathfrak S\cap{\mathfrak N}^v$ is a bijection
between $R^v_w$ and $N^v_w$.   Combining this with the bijection
$U^vw\congN^v_w$,  we get a natural bijection $U^vw\congR^v_w$.
Furthermore, the elements
of $R^v_w$ all have the same cardinality.  The justification
is now completed by an appeal to Corollary~\ref{cmain}.

We now sketch a proof that $U^vw$ and $N^v_w$ are naturally bijective.
We first show that $\Lambda$ is $w$-dominated.   It is not hard to see
that $\Lambda=(\Lambda_1,\ldots,\Lambda_p)$ is the block decomposition
of $\Lambda$.      Thus $w$ is the first component of $\pi(\Lambda)$,
where $\pi$ is the map described in subsection~\ref{sspi}.   By
Proposition~\ref{ppi}~(4),   $w$  dominates $\Lambda$.

To show the maximality of $\Lambda$ with respect to being square-free
and $w$-dominated,  let $(r,c)$ be an element of ${\mathfrak N}^v\setminus\Lambda$.
Consider the block decomposition of $\Lambda^{\#}:=\Lambda\cup\{(r,c)\}$.
There is no way in which $(r,c)$ can fit into some block 
$\Lambda_j$ without affecting $w(\Lambda_j)$.     Thus the first component
of $\pi(\Lambda^{\#})$ is strictly larger than $w$,  and  it  follows
from Proposition~\ref{ppi}~(4) that $\Lambda^{\#}$ is not $w$-dominated.

We have thus shown that elements of $U^vw$ when thought of
as monomials belong to $N^v_w$.   We will now show that each
element of $N^v_w$ arises this way.

Let $\mathfrak S$ be an element of $N^v_w$ and $\mathfrak B$ a block of $\mathfrak S$.
Suppose that $(r,c)$ and $(R,C)$ are consecutive members in
the arrangement of elements of $\mathfrak B$ by non-decreasing
row and column indices.    Then either $r<R$ or $c<C$ since
$\mathfrak S$ is square-free.

Suppose that $r<R$.   If $c<C$,  then consider $\mathfrak S\cup\{(r,c)\}$.
It is not hard to see that $\mathfrak S\cup\{(r,c)\}$ has the same
block decomposition as $\mathfrak S$ except that $\mathfrak B$ is replaced
by $\mathfrak B\cup\{(r,c)\}$.  This violates maximality of $\mathfrak S$.
Thus $c=C$.

If $r<R-1$, consider $\mathfrak S\cup\{(R-1,C)\}$.  This again has the same
block decomposition as $\mathfrak S$ except that $\mathfrak B$ is replaces by
$\mathfrak B\cup\{(R-1,C)\}$.   This violates the maximality of $\mathfrak S$.
Thus $r=R-1$.

In a similar fashion,   we can argue that if $c<C$,  then $r=R$ and
$c=C-1$.    Furthermore,  we can show similarly that
the first member of $\mathfrak B$ is $(a,b)$ and the last $(A,B)$,
where $w(\mathfrak B)=(A,b)$,  $a$ is the least element of $\{1,\ldots,n\}
\setminus\{v_1,\ldots,v_d\}$ that is bigger than $b$,  and $B$ is
the biggest element of $\{v_1\ldots,v_d\}$ that is smaller than $A$.

The block decomposition of $\mathfrak S$ thus gives a tuple of non-intersecting
lattice paths that belong to $U^vw$.

\subsection{The Gr\"obner basis interpretation}\label{ssgroebner}
Fix elements $v,w$ in $I(d,n)$ with $v\leq w$.    As in the case
$v=(1,\ldots,d)$ considered in \cite{kl},   the main theorem has
an interpretation in terms of Gr\"obner basis.

Recall from \S\ref{ssmt} that the ideal $\left(f_\theta=p_\theta/p_v{\,|\,}
\mbox{\begin{rm} $\theta$ in $I(d,n)$, $\theta\nleq w$\end{rm}}\right)$
in the polynomial ring $P:=k[X_\beta{\,|\,}\beta\in\mathfrak R ^v]$ defines the
tangent cone to the Schubert variety $X_w$ at the point $e^v$.
The $f_\theta$ are homogeneous polynomials in the variables
$X_\beta$, $\beta\in\mathfrak R ^v$.        The following lemma shows that
a subset of these generators suffices:
\begin{lemma}\label{lgenerator}
The ideals $(f_\theta{\,|\,}\theta\inI(d,n),\theta\nleq w)$ and $(f_\theta{\,|\,}
\theta\inI(d,n), v\leq\theta\nleq w)$ are equal.
\end{lemma}
\begin{proposition}oof
Let $\theta$ be an element of $I(d,n)$ with $\theta\nleq w$.   We will show
that $f_\theta$ belongs to $(f_\mu{\,|\,}\mu\inI(d,n), v\leq\mu\nleq w)$.
Fix $k$, $1\leq k\leq d$, such that $\theta_k>w_k$.     Let $a$ be the largest
integer such that $1\leq a\leq d$ and $v_a\leq w_k$.    Consider the
elements $\mu$ of $I(d,n)$ of the form
\[
        \left\{v_{i_1},\ldots,v_{i_{k-1}}\right\}\cup
      \left\{v_{a+1},\ldots,v_d\right\}\cup
      \left\{\theta_{j_1},\ldots,\theta_{j_{a-k+1}}\right\}\]
where $1\leq i_1<\ldots<i_{k-1}\leq a$, $k\leq j_1<\ldots<j_{a-k+1}\leq n$,
and
 $ \left\{v_{a+1},\ldots,v_d\right\}$ is disjoint from
 $\left\{\theta_{j_1},\ldots,\theta_{j_{a-k+1}}\right\}$.

 Let us first observe that such a $\mu$ satisfies $v\leq \mu\nleq w$.
 For $1\leq j\leq k-1$,   we have $\mu_j=v_{i_j}\geq v_j$  (since $i_j\geq j$).
 For $k\leq j\leq a$,  we have $\mu_j\geq \mbox{\begin{rm}min\end{rm}}
 \left\{v_{a+1},\theta_k\right\}>w_k
 \geq v_a$.   (This also shows that $\mu_k>w_k$.)   Let now $a<j$.   Consider
 the subset of the first $j-k+1$ elements of $\{v_{a+1},\ldots,v_d\}\cup
 \{\theta_{j_1},\ldots,\theta_{j_{a-k+1}}\}$ when the elements are arranged in
 increasing order.    This subset contains $v_j$, and since $\mu_j$ is the largest
 element of this subset,   $\mu_j\geq v_j$.    This finishes the proof that $\mu$
 satisfies $v\leq \mu\nleq w$.

 Let $M$ denote the sub-matrix of a matrix as in Figure~1 consisting of
 the rows $\theta_1,\ldots,\theta_d$.    Let $N$ be the $(d-k+1)\times a$
 sub-matrix of $M$ determined by the rows $\theta_k,\ldots,\theta_d$ and
 the first $a$ columns.    Each $f_\mu$ is the determinant of an $(a-k+1)\times
 (a-k+1)$ sub-matrix of $N$.   And each such non-zero determinant of
 a sub-matrix of $N$ equals $f_\mu$ for some $\mu$.

 That $f_\theta$ belongs to the ideal $(f_\mu{\,|\,} \mu \mbox{\begin{rm}
  as above\end{rm}})$
 follows from
 the following fact about matrices,  which is easily seen (by the Laplace expansion,
 for example):  Let $d,a,k$ be integers such that $1\leq k\leq a\leq d$.
 Let $M$ be a generic matrix of indeterminates of size $d\times d$.     Let $N$
 be a sub-matrix of $M$ of size $(d-k+1)\times a$  (in other words, $N$ is obtained
 by specifying $(d-k+1)$ row indices and $a$ column indices).     Then, in
 the polynomial ring obtained by adjoining to a field the entries of $M$,
 the determinant of $M$ belongs to the ideal generated by the determinants
 of sub-matrices of $N$ of size $(a-k+1)\times (a-k+1)$.\end{proposition}oof

 For $\theta$ in $I(d,n)$ with $v\leq\theta$, let $\mathfrak S_\theta$ denote the
monomial in ${\mathfrak N}^v$ (and so also in $\mathfrak R ^v$)
associated to
$\theta$ as in Proposition~\ref{psw}.   We abuse notation and write
$\mathfrak S_\theta$ also for the corresponding monomial in the variables
$X_\beta$, $\beta\in\mathfrak R ^v$.

\begin{proposition}op\label{pgroebner}
Let $v,w$ be elements of $I(d,n)$ with $v\leq w$.  Fix any term
order on the monomials in the polynomial ring
$k[X_\beta{\,|\,}\beta\in\mathfrak R ^v]$ such that
the initial term of $f_\theta$ with respect to this order is
$\mathfrak S_\theta$
for $\theta$ in $I(d,n)$ with $\theta\geq v$.    Then
$\left\{f_\theta{\,|\,}\theta\inI(d,n), v\leq\theta\nleq w\right\}$ is
a Gr\"obner basis with respect to this order.
\end{proposition}op
\begin{proposition}oof
Denoting by $I$ the ideal $\left(f_\theta
{\,|\,}\theta\inI(d,n), v\leq\theta\nleq w\right)$,  by $\init{f}$ the
initial term of a polynomial $f$ in this term order,  and by $\init{I}$
the ideal $\left(\init{f}{\,|\,} f\in I\right)$,  we clearly have a graded
surjection
\[
P/\left(\init{f_\theta}{\,|\,}\theta\inI(d,n), v\leq\theta\nleq w\right)
\twoheadrightarrow P/\init{I}
\]
The assertion of the proposition is that this map is an isomorphism.
To prove this,  it is enough to show that both graded rings have the
same Hilbert function.

The Hilbert function of $P/\init{I}$ is the same as that of the tangent cone
$P/I$,  and so by Theorem~\ref{tmain} it equals the cardinality of
$S^v_w(m)$ in degree $m$, where $S^v_wm$ is the set of $w$-dominated
monomials in $\mathfrak R ^v$ of degree $m$.  We now show that a monomial
in $\mathfrak R ^v$ belongs to the ideal $\left(\init{f_\theta}{\,|\,}\theta\inI(d,n),
v\leq\theta\nleq w\right)$ if and only if it is not $w$-dominated, and
this will complete the proof.

Suppose that a monomial $\mu$ in $\mathfrak R ^v$ is not $w$-dominated.
Let $\beta_1>\ldots>\beta_t$ be a $v$-chain of elements in $\mu$
such that $w\ngeq s_{\beta_1}\cdots s_{\beta_t}v$.  The monomial
$\{\beta_1,\ldots,\beta_t\}$ is distinguished and so by
Proposition~\ref{psw} it corresponds to an element $\theta$ in
$I(d,n)$ with $v\leq \theta$.   We have $\theta=s_{\beta_1}
\cdots s_{\beta_t}v\nleq w$ so that $\init{f_\theta}$ divides $\mu$.

For the converse, it is enough to show that $\init{f_\theta}$ is
not $w$-dominated for $\theta\nleq w$, and this follows from the
following lemma.\end{proposition}oof
\begin{lemma}ma
For $\theta$ in $I(d,n)$ with $v\leq\theta$,  we have $\theta\leq w$
if and only if $w$ dominates $\mathfrak S_\theta$.
\end{lemma}
\begin{proposition}oof
Let us consider the image of the monomial $\mathfrak S_\theta$ under the
map $\pi$ of subsection~\ref{sspi}.    The blocks of $\mathfrak S_\theta$
are precisely its singleton subsets.   Thus $\pi(\mathfrak S_\theta)
=(\theta,\mbox{{\rm empty monomial}})$.   Proposition~\ref{ppi}~(4)
now says that $\theta$ is the least element of $I(d,n)$ that dominates
$\mathfrak S_\theta$.   The lemma follows.\end{proposition}oof

We finish by listing some term orders that satisfy the requirement
of Proposition~\ref{pgroebner}.    Fix notation and
terminology as in \S15.2 of \cite{ebud}.  Defined below are
four partial orders $>_1$, $>_2$, $>_3$, and $>_4$
on the elements of $\mathfrak R ^v$.  We use $>_j$ to denote also any
total order that refines the partial order $>_j$.  The homogeneous
lexicographic order induced by $>_1$ or by $>_2$ and the
reverse lexicographic order induced by $>_3$ or by $>_4$
satisfy the requirement of Proposition~\ref{pgroebner}.

The partial orders $>_1$, $>_2$, $>_3$, and $>_4$
on elements of $\mathfrak R ^v$ are as follows:
\begin{itemize}
\item
	for $(r,c)$ in ${\mathfrak N}^v$ and $(a,b)$ in $\mathfrak R ^v\setminus{\mathfrak N}^v$,
	$(r,c)>_j(a,b)$ for $j=1,2,3,4$.
\item
	for $(r,c)$ and $(r',c')$ in ${\mathfrak N}^v$,
	\begin{enumerate}
	\item	$(r,c)>_1(r',c')$ if either (a)~$r<r'$ or
			(b)~$r=r'$ and $c>c'$.
	\item	$(r,c)>_2(r',c')$ if either (a)~$c>c'$ or
			(b)~$c=c'$ and $r<r'$.
	\item	$(r,c)>_3(r',c')$ if either (a)~$r<r'$ or
			(b)~$r=r'$ and $c<c'$.
	\item	$(r,c)>_4(r',c')$ if either (a)~$c>c'$ or
			(b)~$c=c'$ and $r>r'$.
			\end{enumerate}
			\end{itemize}

\end{document}