%fpsac.tex
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%% Gr"obner geometry of Schubert polynomials %%%%%%%
%%%%%%% %%%%%%%
%%%%%%% Allen Knutson and Ezra Miller %%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass[12pt]{amsart}%article}
%\hoffset=1.5mm
\voffset=5mm
\oddsidemargin=17pt \evensidemargin=17pt
\headheight=9pt \topmargin=26pt%-24pt
\textheight=624pt \textwidth=433.8pt
\usepackage{latexsym}
\usepackage{amssymb}
\newcommand{\comment}[1]{{$\star$\sf\textbf{#1}$\star$}}
\newcommand{\excise}[1]{}
% Theorem environments with italic font
\newtheorem{thm}{Theorem}[subsection]
\newtheorem{lemma}[thm]{Lemma}
\newtheorem{claim}[thm]{Claim}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{conj}[thm]{Conjecture}
\newtheorem{question}[thm]{Question}
\newtheorem{por}[thm]{Porism}
\newtheorem{result}[thm]{Result}
% Theorem environments with roman or slanted font
\newtheorem{Example}[thm]{Example}
\newtheorem{Remark}[thm]{Remark}
\newtheorem{Alg}[thm]{Algorithm}
\newtheorem{Defn}[thm]{Definition}
\newenvironment{example}{\begin{Example}\rm}
{\mbox{}~\hfill~$\Box$~\end{Example}}
\newenvironment{remark}{\begin{Remark}\rm}
{\mbox{}~\hfill~$\Box$~\end{Remark}}
\newenvironment{alg}{\begin{Alg}\rm}{\end{Alg}}
\newenvironment{defn}{\begin{Defn}\rm}{\end{Defn}}
% For definitions with a boldface parenthetical label
\newenvironment{defnlabeled}[1]{\begin{Defn}[#1]\rm}{\end{Defn}}
% For a theorem-like environment whose number is very out of place
\newenvironment{movedThm}[1]{\begin{trivlist}\item {\bf
{#1}\,}\it}{\end{trivlist}}
% For proofs of statements far from the statements themselves
\newenvironment{proofof}[1]{\begin{trivlist}\item {\it
Proof of {#1}.\,}}{\mbox{}\hfill$\Box$\end{trivlist}}
% For ``diagrams'' containing large matrices or rc-graphs
\newenvironment{rcgraph}{\begin{trivlist}\item\centering\footnotesize$}
{$\end{trivlist}}
% For very small rcgraphs
\def\tinyrc#1{\hbox{\tiny${#1}$}}
%For numbered lists within the main body of the text
\newenvironment{textlist}%
{\begin{list}
{\noindent\makebox[0mm][r]{(\roman{enumi})}}
{\usecounter{enumi} \topsep=1.5mm \itemsep=.25ex}
\renewcommand\theenumi{\roman{enumi}}
}
{\renewcommand\theenumi{\arabic{enumi}}\end{list}}
%For numbered lists in theorems, examples, etc., but not exercises
\newenvironment{thmlist}%
{\begin{list}
{\noindent\makebox[0mm][r]{\arabic{enumi}.}}
{\usecounter{enumi} \topsep=1.5mm \itemsep=.5ex}
}
{\end{list}}
%For separated lists with consecutive numbering
\newcounter{separated}
%For boldface emphasizing
\def\bem#1{\textbf{#1}}
%Single characters, used in math mode
\def\<{\langle}
\def\>{\rangle}
\def\0{{\mathbf 0}}
\def\1{{\mathbf 1}}
\def\AA{{\mathbb A}}
\def\AL{{\mathbb A}^{\!\mathbb L}}
\def\CC{{\mathbb C}}
\def\cC{{\mathcal C}}
\def\cD{{\mathcal D}}
\def\DD{{\mathfrak D}}
\def\EE{{\mathcal E}}
\def\FF{{\mathcal F}}
\def\GG{{\mathcal G}}
\def\HH{{\widetilde H}{}}
\def\II{{\mathcal I}}
\def\JJ{{\mathcal J}}
\def\KK{{\mathcal K}}
\def\bL{{\mathbb L}}
\def\LL{{\mathcal L}}
\def\MM{{\mathfrak M}}
\def\NN{{\mathbb N}}
\def\OO{{\mathcal O}}
\def\PP{{\mathbb P}}
\def\QQ{{\mathbb Q}}
\def\RR{{\mathbb R}}
\def\SS{{\mathfrak S}}
\def\VV{{\mathcal V}}
\def\WW{{\mathbf \Omega}}
\def\ZZ{{\mathbb Z}}
\def\aa{{\mathbf a}}
\def\bb{{\mathbf b}}
\def\cc{{\mathbf c}}
\def\ee{{\mathbf e}}
\def\kk{{\mathbf k}}
\def\mm{{\mathfrak m}}
\def\pp{{\mathfrak p}}
\def\xx{{\mathbf x}}
\def\yy{{\mathbf y}}
\def\zz{{\mathbf z}}
%roman font words for math mode
\def\ch{{\rm ch}}
\def\ev{{\rm ev}}
\def\gr{{\rm gr}}
\def\id{{\rm id}}
\def\nd{{\rm nd}}
\def\rk{{\rm rk}}
\def\st{{\rm st}}
\def\th{{\rm th}}
\def\col{{\rm col}}
\def\del{{\rm del}}
\def\Hom{{\rm Hom}}
\def\hor{{\rm hor}}
\def\low{{\rm low}}
\def\row{{\rm row}}
\def\std{{\rm std}}
\def\sym{{\rm Sym}}
\def\crit{{\rm crit}}
\def\link{{\rm link}}
\def\mass{{\rm mass}}
\def\mdeg{{\rm mdeg}}
\def\mult{{\rm mult}}
\def\prom{{\rm prom}}
\def\rank{{\rm rank}}
\def\SPEC{\mathbf{Spec}}
\def\spec{{\rm Spec}}
\def\supp{{\rm supp}}
\def\vert{{\rm vert}}
\def\west{{\rm west}}
\def\coker{{\rm coker}}
\def\cross{\textrm{`+'} }
\def\point{{\rm point}}
\def\start{{\rm start}}
\def\column{{\rm column}}
\def\facets{{\rm facets}}
\def\length{{\rm length}}
\def\weight{{\rm wt}}
\def\mitosis{{\rm mitosis\hspace{1pt}}}
%math symbols without arguments
\def\FL{{\mathcal F}{\ell}_n}
\def\FLN{{\mathcal F}{\ell}_N}
\def\IN{\mathsf{in}}
\def\mn{{M_n}}
\def\mN{{M_N}}
%\def\mnC{{M_n\CC}}
%\def\mNC{{M_N\CC}}
\def\rc{\mathcal{RC}}
\def\dom{\backslash}
\def\ess{{\mathcal E\hspace{-.2ex}s\hspace{-.1ex}s}}
\def\fln{{B \backslash \gln\CC}}
\def\flN{{B \backslash \glN\CC}}
\def\gln{{G_{\!}L_n}}
\def\glN{{G_{\!}L_N}}
\def\too{\longrightarrow}
\def\from{\leftarrow}
\def\hhom{{\mathcal{H}\hspace{-.2ex}\mathit{om}}}
\def\into{\hookrightarrow}
\def\spot{{\hbox{\raisebox{1.7pt}{\large\bf .}}\hspace{-.5pt}}}
\def\onto{\twoheadrightarrow}
\def\otni{\hookleftarrow}
\def\otno{\twoheadleftarrow}
\def\adots{{.\hspace{1pt}\raisebox{2pt}{.}\hspace{1pt}\raisebox{4pt}{.}}}
\def\minus{\smallsetminus}
\def\congto{\stackrel{\begin{array}{@{}c@{\;}}
\\[-4ex]\scriptstyle\approx\\[-1.6ex]
\end{array}}\to}
\def\goesto{\rightsquigarrow}
\def\implies{\Rightarrow}
\def\nothing{\varnothing}
\def\bigcupdot{\makebox[0pt][l]{$\hspace{1.05ex}\cdot$}\textstyle\bigcup}
\def\toplinedots{\hfill\raisebox{-5.1pt}[0pt][0pt]{\ $\ldots$\ }\hfill}
\renewcommand\iff{\Leftrightarrow}
%math symbols taking arguments
\def\cj#1{\kk[\zz]/J_{#1}}
\def\ci#1{\kk[\zz]/I_{#1}}
\def\ol#1{{\overline {#1}}}
\def\ub#1{\hbox{\underbar{$#1$\hspace{-.25ex}}\hspace{.25ex}}}
\def\wt#1{{\widetilde{#1}}}
\def\GOX#1{{\Gamma(\OO_{\ol X_{#1}})}}
\def\dem#1{{\ol \partial_{#1}}}
\def\sub#1#2{_{[#1,#2]}}
%\def\ddem#1#2{{\widetilde \partial_{#1}^{#2}}}
\def\ddem#1#2{{\varepsilon_{#1}^{#2}}}
\def\aoverb#1#2{{\genfrac{}{}{0pt}{1}{#1}{#2}}}
\def\twoline#1#2{{\aoverb{\scriptstyle {#1}}{\scriptstyle {#2}}}}
% For direct limits
\def\fillrightharpoondown{\mathord- \mkern-6mu
\cleaders\hbox{$\mkern-2mu \mathord- \mkern-2mu$}\hfill
\mkern-6mu \mathord\rightharpoondown}
\def\dirlim#1{\begin{array}{@{}c@{}}% usage: \dirlim t or {}^*\dirlim t
\lim_{\hspace{.5pt}#1}\\[-10pt]
\fillrightharpoondown\hspace{4.0pt}\\[-5pt]
\end{array}{}}
%For rc-graphs, courtesy Nantel Bergeron, command names rewritten by EM
\font\co=circle10
\def\petit#1{{\scriptstyle #1}}
\def\plus{\petit +}
%Pair of avoiding elbows looks kind of like a `j' and then an `r'
\def\jr{\smash{\raise2pt\hbox{\co \rlap{\rlap{\char'005} \char'007}}
\raise6pt\hbox{\rlap{\vrule height6.5pt}}
\raise2pt\hbox{\rlap{\hskip4pt \vrule height0.4pt depth0pt
width7.7pt}}}}
%Single elbow, shaped like a `j' (`j end', or `j elbow')
\def\je{\smash{\raise2pt\hbox{\co \rlap{\rlap{\char'005}
\phantom{\char'007}}}\raise6pt\hbox{\rlap{\vrule height6pt}}}}
%Cross, for pipe dreams (as opposed to \plus, for plus and dot diagrams)
\def\+{\smash{\lower2pt\hbox{\rlap{\vrule height14pt}}
\raise2pt\hbox{\rlap{\hskip-3pt \vrule height.4pt depth0pt
width14.7pt}}}}
%Permutation, for the column labels in a pipe dream
\def\perm#1#2{\hbox{\rlap{$\petit {#1}_{\scriptscriptstyle #2}$}}%
\phantom{\petit 1}}
\def\phperm{\phantom{\perm w3}}
\def\mcc{\multicolumn{1}{@{}c@{}}}
\def\reflection#1#2#3{\raisebox{#1}{${\scriptstyle#2}_{\scriptscriptstyle#3}$}}
\def\ld#1#2{\raisebox{#1 pt}%
{${\scriptstyle\partial}_{\scriptscriptstyle#2}\!\!\!$}}
\def\rd#1#2{\raisebox{#1 pt}%
{$\!\!\!{\scriptstyle\partial}_{\scriptscriptstyle#2}$}}
\def\textcross{\ \smash{\lower4pt\hbox{\rlap{\hskip4.15pt\vrule height14pt}}
\raise2.8pt\hbox{\rlap{\hskip-3pt \vrule height.4pt depth0pt
width14.7pt}}}\hskip12.7pt}
\def\textelbow{\ \hskip.1pt\smash{\raise2.8pt%
\hbox{\co \hskip 4.15pt\rlap{\rlap{\char'005} \char'007}
\lower6.8pt\rlap{\vrule height3.5pt}
\raise3.6pt\rlap{\vrule height3.5pt}}
\raise2.8pt\hbox{%
\rlap{\hskip-7.15pt \vrule height.4pt depth0pt width3.5pt}%
\rlap{\hskip4.05pt \vrule height.4pt depth0pt width3.5pt}}}
\hskip8.7pt}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\raggedbottom
\mbox{}\vspace{-5ex}
\title{Extended abstract:\\Gr\"obner geometry of Schubert polynomials}
\author{Allen Knutson}
\address{Mathematics Department\\ UC Berkeley\\ Berkeley, California}
\email{allenk@math.berkeley.edu}
\author{Ezra Miller}
\address{Mathematics Department\\ MIT\\ Cambridge, Massachusetts}
\email{ezra@math.mit.edu}
\thanks{AK was partly supported by the Clay
Mathematics Institute, Sloan Foundation, and NSF}
\thanks{EM was supported by the Sloan Foundation and
NSF}
%\email{allenk@math.berkeley.edu,\ ezra@math.mit.edu}
\date{10 December 2001}
\begin{excise}{
\begin{abstract}
\noindent
Schubert polynomials, which a priori represent cohomology classes of
Schubert varieties in the flag manifold, also represent torus-equivariant
cohomology classes of certain determinantal loci in the vector space of
$n \times n$ complex matrices. Our central result is that the minors
defining these ``matrix Schubert varieties'' are Gr\"obner bases for any
antidiagonal term order. The Schubert polynomials are therefore positive
sums of monomials, each monomial representing the torus-equivariant
cohomology class of a component (a scheme-theoretically reduced
coordinate subspace) in the limit of the resulting Gr\"obner degeneration.
Interpreting the Hilbert series of the flat limit in equivariant
$K$-theory, another corollary of the proof is that Grothendieck
polynomials represent the classes of Schubert varieties in $K$-theory of
the flag manifold.
An inductive procedure for listing the limit coordinate subspaces is
provided by the proof of the Gr\"obner basis property, bypassing what has
come to be known as Kohnert's conjecture \cite{NoteSchubPoly}. The
coordinate subspaces, which are the facets of a simplicial complex, are
in an obvious bijection with the rc-graphs of Fomin and Kirillov
\cite{FKyangBax}. Thus our positive formula for Schubert polynomials
agrees with (and provides a geometric proof of) the combinatorial formula
of Billey--Jockusch--Stanley \cite{BJS}. Moreover, we shell this complex
(as one of a new class of vertex-decomposable complexes we introduce),
which shows that the initial ideal of the minors is a Cohen--Macaulay
Stanley--Reisner ideal. This provides a new proof that Schubert
varieties are Cohen--Macaulay.
The multidegree of any finitely generated multigraded module, defined
here based on torus-equivariant cohomology classes, generalizes the usual
$\ZZ$-graded degree to finer gradings. Part of the Gr\"obner basis
theorem includes formulae for the multidegrees and Hilbert series of
determinantal ideals in terms of Schubert and Grothendieck polynomials.
In the special case of vexillary determinantal loci, which include all
one-sided ladder determinantal varieties, the multidegree formulae are
themselves determinantal, and our new antidiagonal Gr\"obner basis
statement contrasts with known diagonal \hbox{Gr\"obner basis
statements}.
Interpreting the Schubert polynomials as equivariant cohomology classes
on matrices gives a topological reason (see also \cite{FRthomPoly})
why Schubert polynomials are the characteristic classes for
degeneracy loci \cite{FulDegLoc}: the mixing space construction of Borel
that computes this equivariant cohomology is identified as the
classifying space for maps between flagged vector bundles.
%\vskip 1ex
%\noindent
%{{\it AMS Classification:} ; }
\end{abstract}
}\end{excise}
\maketitle
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
{}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\setcounter{tocdepth}{2}
%\tableofcontents
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\section*{Summary/R\'esum\'e}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\label{sec:intro}
\excise{
Combinatorialists have recognized for some time the intrinsic interest of
the Schubert polynomials $\SS_w$ of Lascoux and Sch\"utzenberger
\cite{LSpolySchub} indexed by permutations $w \in S_n$, and are therefore
producing a wealth of interpretations for their coefficients; see
\cite{BergeronCombConstSchub}, \cite[Appendix to Chapter IV, by N.\
Bergeron]{NoteSchubPoly}, \cite{BJS}, \cite{FKyangBax},
\cite{FSnilCoxeter}, \cite{Kohnert}, and \cite{Winkel}. Geometers, on
the other hand, who take Schubert {\em classes} for granted, generally
remain less convinced of the naturality of Schubert {\em polynomials},
even though they arise in certain universal geometric contexts
\cite{FulDegLoc}, and there are geometric proofs of positivity for their
coefficients \cite{BSskewSchub, KoganThesis}.
}
\subsection*{Summary.}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Let $w \in S_n$ be a permutation. We provide a geometric context in
which both (i)~polynomial representatives for the Schubert classes
$[X_w]$ in the cohomology ring $H^*(\FL)$ of the flag manifold are
uniquely singled out, with no choices other than a Borel subgroup of
$\gln$; and (ii)~it is geometrically obvious that these
% representatives
polynomials have nonnegative coefficients. These polynomials turn out to
be the Schubert polynomials $\SS_w(x_1,\ldots,x_n)$ of Lascoux and
Sch\"utzenberger \cite{LSpolySchub}.
Our investigations lead us to replace topology on the flag manifold with
multigraded commutative algebra, by generalizing the notion of degree for
subschemes of projective space. Identifying the Schubert polynomials in
this context then sheds light on the algebra and geometry of
determinantal ideals specified by rank conditions as in \cite{FulDegLoc},
and especially on the combinatorics of
% their
initial ideals for certain natural term orders. These initial ideals are
the Stanley--Reisner ideals for simplicial complexes whose facets are in
natural bijection with the rc-graphs of Fomin and Kirillov
\cite{FKyangBax,BB}. We give an inductive procedure on the weak Bruhat
order for listing rc-graphs. Our further analysis of rc-graphs is based
on the combinatorics of words and their subwords in general Coxeter
groups, which give rise to shellable simplicial balls or spheres
generalizing the initial ideals constructed from rc-graphs.
{\sl
\subsection*{R\'esum\'e.}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Soit $w\in S_n$ une permutation. Nous fournissons un contexte
g\'eom\'etrique qui (i) nous permet d'exhiber de mani\`ere unique, et
sans autre choix que celui d'un sous groupe de Borel de $GL_n$, des
repr\'esentants polyn\^omiaux des classes de Schubert $[X_w]$ dans
l'anneau de cohomologie $H^*({\mathcal F}\ell_n)$ de la vari\'et\'e des
drapeaux; (ii) rend g\'eom\'etriquement \'evident le fait que les
coefficients de ces polyn\^omes sont tous non n\'egatifs. Ces polyn\^omes
se trouvent \^etre les polyn\^omes de Schubert ${\mathfrak
S}_w(x_1,\ldots,x_n)$ de Lascoux et Sch\"utzenberger \cite{LSpolySchub}.
Nos investigations nous ont men\'es \`a remplacer la topologie de la
vari\'et\'e des drapeaux par de l'alg\`ebre commutative multigradu\'ee,
en g\'en\'eralisant la notion de degr\'e aux sous-ch\'emas de l'espace
projectif. L'apparition des polyn\^omes de Schubert dans ce contexte
\'eclaire l'alg\`ebre et la g\'eom\'etrie des id\'eaux d\'eterminantaux
% ???
sp\'ecifi\'es par des conditions de rang \cite{FulDegLoc}, et
sp\'ecialement la combinatoire des id\'eaux initiaux pour certains ordres
de termes
% ???
apparaissant naturellement. Ces id\'eaux sont les id\'eaux de
Stanley--Reisner de certains complexes simpliciaux, dont les facettes
sont en bijection naturelle avec l'ensemble des rc-graphes de Fomin et
Kirillov \cite{FKyangBax,BB}. Nous donnons une proc\'edure inductive sur
l'ordre de Bruhat faible pour lister les rc-graphes. Notre analyse
ult\'erieure des rc-graphes se base sur la combinatoire des mots et
sous-mots dans les groupes de Coxeter g\'en\'eraux, qui donne lieu \`a
des boules ou sph\`eres effeuillable,
% ``shellables'' ???,
g\'en\'eralisant les id\'eaux construits \`a partir de rc-graphes.
}
\excise{
Let $w \in S_n$ be a permutation. We provide a geometric context in
which both (i)~polynomial representatives for the Schubert classes
$[X_w]$ in the cohomology ring $H^*(\FL)$ of the flag manifold are
uniquely singled out, with no choices other than a Borel subgroup of
$\gln$; and (ii)~it is geometrically obvious that these
% representatives
polynomials have nonnegative coefficients. These polynomials turn out to
be the Schubert polynomials $\SS_w(x_1,\ldots,x_n)$ of Lascoux and
Sch\"utzenberger \cite{LSpolySchub}.
Our investigations lead us to replace topology on the flag manifold with
multigraded commutative algebra, by generalizing the notion of degree for
subschemes of projective space. Identifying the Schubert polynomials in
this context then sheds light on the algebra and geometry of
determinantal ideals specified by rank conditions as in \cite{FulDegLoc},
and especially on the combinatorics of
% their
initial ideals for certain natural term orders. These initial ideals are
the Stanley--Reisner ideals for simplicial complexes whose facets are in
natural bijection with the rc-graphs of Fomin and Kirillov
\cite{FKyangBax,BB}. We give an inductive procedure on the weak Bruhat
order for listing rc-graphs. Our further analysis of rc-graphs is based
on the combinatorics of words and their subwords in general Coxeter
groups, which give rise to shellable simplicial balls or spheres
generalizing the initial ideals constructed from rc-graphs.
}
%\end{section}{Introduction}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Gr\"obner bases and multidegrees of determinantal ideals}%%%%%%%
\label{sec:gb}
\subsection{Matrix Schubert varieties}\label{sub:matSchub}%%%%%%%%%%%%%%%
Let $\mn$ be the $n \times n$ matrices over a field~$\kk$, with
coordinate ring $\kk[\zz]$ in indeterminates $\{z_{ij}\}_{i,j = 1}^n$.
Throughout the paper, $q$ and $p$ will be integers with $1 \leq q,p \leq
n$, and $Z$ will stand for an $n \times n$ matrix. Usually $Z$ will be
the \bem{generic matrix} of variables $(z_{ij})$, although occasionally
$Z$ will be an element of $\mn$. Denote by $Z\sub qp$ the northwest $q
\times p$ submatrix of $Z$. For instance, given a permutation matrix
$w^T$
% (with $w \in S_n$) whose $1$'s lie at $w^T_{i,w(i)}$,
(for $w \in S_n$) with $1$'s in row~$i$ and column~$w(i)$, we find that
\begin{eqnarray*}
\rank(w^T\sub qp) &=& \#\{(i,j) \leq (q,p) \mid w(i) = j\}
\end{eqnarray*}
is the number of $1$'s in the submatrix $w^T\sub qp$.
The following definition was made by Fulton in \cite{FulDegLoc}.
\begin{defn} \label{d:matrixSchub}
%\begin{defnlabeled}{{\cite[Section~3]{FulDegLoc}}}\end{defnlabeled}
Let $w \in S_n$.
The \bem{matrix Schubert variety} $\ol X_w \subseteq \mn$ consists of the
matrices $Z \in \mn$ such that $\rank(Z\sub qp) \leq \rank(w^T\sub qp)$
for all $q,p$.
\end{defn}
Let $B \subset \gln$ denote the Borel group of {\em lower} triangular
matrices, so that $\FL = B \dom \gln$ is the manifold of flags in
$\kk^n$. Intersecting $\ol X_w$ with $\gln \subset \mn$ yields the
variety $\tilde X_w$ of all invertible matrices mapping to the Schubert
variety $X_w \subseteq \FL$. Here, we define $X_w$ to be the closure in
$\FL$ of the orbit $B w^T B^+$, where $B^+$ denotes the upper triangular
matrices in~$\gln$.
Heuristically, in the case $\kk = \CC$, the matrix Schubert variety
determines a $B$-equivariant cohomology class $[\ol X_w]_B \in
H^*_B(\mn)$ that maps to the corresponding class $[\tilde X_w]_B \in
H^*_B(\gln)$ under the inclusion $\gln \into \mn$. Letting $T$ denote
the maximal torus in $B$, observe that $H^*_B(\mn) = H^*_T(\mn) =
\ZZ[x_1,\ldots,x_n]$ because $B$ retracts to~$T$ and $\mn$ is
$T$-equivariantly contractible. Therefore $[\ol X_w]_B \in \ZZ[\xx]$ is
well-defined as a polynomial in $\xx = x_1,\ldots,x_n$. Since the
quotient $\gln \onto \FL$ induces a natural isomorphism $H^*_B(\gln)
\cong H^*(\FL)$, we find that the polynomial $[\ol X_w]_B = [\ol X_w]_T$
represents the Schubert class $[X_w]$ on~$\FL$.
The previous paragraph accomplishes the goal of singling out unique
polynomial representatives for Schubert classes. It can be made
completely precise when $\kk = \CC$ by arguments derived from
\cite{Kaz97} and appearing also in \cite{FRthomPoly}. These techniques
demonstrate why double Schubert polynomials (applied to the Chern roots
of flagged vector bundles) are the characteristic classes for degeneracy
loci \cite{FulDegLoc}: the mixing space construction of Borel whose
cohomology is the equivariant cohomology of $\mn$ agrees with the
classifying space for maps between flagged vector bundles.
Instead of relating equivariant cohomology of $\mn$ to ordinary
cohomology of $\FL$, we employ the notion of multidegree---a commutative
algebra approach to torus-equivariant cohomology (cf.\
\cite{TotChowRing,BrionEqCohEqInt,EGequivInt}) on vector spaces.
Multidegrees work over arbitrary fields~$\kk$, and are in any case
essential for showing geometrically why the coefficients of $[\ol X_w]_T$
are positive.
\subsection{Schubert polynomials as multidegrees}\label{sub:multideg}%%%%
For the purpose of dealing with multidegrees in complete generality,
% for the time being
let $\kk[\zz]$ be the polynomial ring in $m$ variables $\zz =
z_1,\ldots,z_m$, with a grading by $\ZZ^n$ in which each variable $z_i$
has \bem{exponential weight} $\weight(z_i) = \xx^{\aa_i}$ for some vector
% $\aa_1,\ldots,\aa_m \in \ZZ^n$.
$\aa_i \in \ZZ^n$. In the case of interest for later purposes, $m = n^2$
with $\zz = (z_{ij})_{i,j=1}^n$ and $\weight(z_{ij}) = x_i$.
Every finitely generated $\ZZ^n$-graded module $\Gamma = \bigoplus_{\bb
\in \ZZ^n} \Gamma_\bb$ over $k[\zz]$ has a graded free resolution
$\EE_\spot: 0 \from \EE_0 \from \EE_1 \from \cdots \from \EE_m \from 0$.
Suppose $\EE_i = \bigoplus_{k=1}^{\beta_i} k[\zz](-\bb_{ik})$, so that
the $k^\th$ summand of $\EE_i$ is generated in $\ZZ^n$-graded degree
$\bb_{ik}$.
\begin{defn} \label{d:Kpoly}
The
% $\ZZ^n$-graded
\bem{$K$-polynomial} of $\Gamma$ is $\KK(\Gamma;\xx) = \sum_i (-1)^i
\sum_k \xx^{\bb_{ik}}$.
\end{defn}
Geometrically, the $K$-polynomial of $\Gamma$ represents the class of the
sheaf $\tilde \Gamma$ on $\kk^m$ in equivariant $K$-theory for the action
of the $n$-torus whose weight lattice is $\ZZ^n$. Combinatorially, when
the $\ZZ^n$-grading is \bem{positive}, meaning that the ordinary weights
$\aa_1,\ldots,\aa_n$ lie in a single open half-space in $\ZZ^n$, the
$K$-polynomial of $\Gamma$ is the numerator of the $\ZZ^n$-graded Hilbert
series $H(\Gamma;\xx)$:
\begin{eqnarray*}
H(\Gamma;\xx)\:\ :=\:\ \sum_{\bb \in \ZZ^n}
\dim_\kk(\Gamma_\bb)\cdot\xx^\bb &=&
\frac{\KK(\Gamma;\xx)}{\prod_{i=1}^m (1-\weight(z_i))}.
\end{eqnarray*}
This occurs when $\zz = (z_{ij})$ and $\weight(z_i) = x_i$, where the
denominator is $\prod_{i=1}^n (1-x_i)^n$.
Given any Laurent monomial $\xx^\aa$,
% for some $\aa \in \ZZ^n$,
the rational function $\prod_{j=1}^n(1-x_j)^{a_j}$ can be expanded as a
well-defined (i.e.\ convergent in the $\xx$-adic topology) formal power
series $\prod_{j=1}^n(1 - a_jx_j + \cdots)$ in~$\xx$. Doing the same for
each monomial in an arbitrary Laurent polynomial $\KK(\xx)$ results in a
power series denoted by $\KK(\1-\xx)$.
% called a \bem{substituted Laurent polynomial}.
\begin{defn} \label{d:multideg}
The \bem{multidegree} of a $\ZZ^n$-graded $\kk[\zz]$-module $\Gamma$ is
the sum $\cC(\Gamma;\xx)$ of the lowest degree terms in
$\KK(\Gamma;\1-\xx)$. If $\Gamma = \kk[\zz]/I$ is the coordinate ring of
a subscheme $X \subseteq \kk^m$, then write $[X]_{\ZZ^n} =
\cC(\Gamma;\xx)$.
\end{defn}
The letters $\cC$ and $\KK$ stand for `cohomology' and
\hbox{`$K$-theory'}, and the relation between them (`take lowest degree
terms') reflects the Grothendieck--Riemann--Roch transition from
$K$-theory to its associated graded ring.
% , which is cohomology.
When $\kk = \CC$ is the complex numbers, the (Laurent) polynomials
denoted by $\cC$ and $\KK$ are honest torus-equivariant cohomology and
$K$-classes on affine space.
The motivating example is the case $X = \ol X_w \subseteq \mn$. Recall
that the \bem{$i^\th$ divided difference} operator $\partial_i$ acts on
polynomials $f \in \ZZ[\xx]$ by $\partial_i(f) = (f - s_i f)/(x_i -
x_{i+1})$, where the $i^\th$ transposition $s_i \in S_n$ switches the
variables $x_i$ and $x_{i+1}$ in the argument of~$f$. After calculating
explicitly that $[\ol X_{w_0}]_{\ZZ^n} = \prod_{i=1}^n x_i^{n-i}$
% $ = x_1^{n-1} x_2^{n-2} \cdots x_{n-2}^2 x_{n-1}$
% that reverses.
for the long permutation $w_0 = n \cdots 321 \in S_n$, we use a direct
geometric argument using multidegrees to show:
\begin{thm} \label{t:oracle}
If\/ $\length(ws_i) < \length(w)$ then $[\ol X_{ws_i}]_{\ZZ^n} =
\partial_i [\ol X_w]_{\ZZ^n}$. Therefore\/ $[\ol X_w]_{\ZZ^n}$ equals
the Schubert polynomial $\SS_w(\xx)$.% of\/ \cite{LSpolySchub}.
\end{thm}
More generally, for the $\ZZ^{2n}$-grading in which $\weight(z_i) =
x_i/y_j$, the proof actually shows that $[\ol X_w]_{\ZZ^{2n}}$ is the
double Schubert polynomial $\SS_w(\xx,\yy)$. Although all of the results
below hold in this `double' setting, we stick to the $\ZZ^n$-grading for
clarity.
% of notation.
\subsection{Multidegrees as positive sums}\label{sub:sums}%%%%%%%%%%%%%%%
Multidegrees, like ordinary degrees, are additive on unions of schemes
with disjoint support and equal dimension. To make a precise statement,
let $\mult_X(\Gamma)$ denote the multiplicity of $\Gamma$ along the
variety $X$.
\begin{thm} \label{t:additive}
Fix a $\ZZ^n$-graded module~$\Gamma$, and let $X_1,\ldots,X_r$ be the
maximal-dimensional irreducible components of the support variety
of\/~$\Gamma$. Then
\begin{eqnarray*}
\cC(\Gamma;\xx) &=& \sum_{\ell=1}^r\mult_{X_\ell}(\Gamma) \cdot
[X_\ell]_{\ZZ^n}.
\end{eqnarray*}
\end{thm}
Multidegrees are constant in flat families, including the Gr\"obner
degenerations of the next lemma. For positive gradings this is easy,
% resulting from
by the constancy of Hilbert series.
\begin{lemma} \label{l:IN}
Fix a $\ZZ^n$-graded module~$\Gamma$, and let\/ $\Gamma \cong F/K$ be an
expression of\/~$\Gamma$ as the quotient of a free module~$F$ with
kernel~$K$. The multidegree $\cC(\Gamma;\xx)$ equals the multi\-degree
of $F/\IN(K)$ for the initial submodule\/ $\IN(K)$ of~$K$ under any term
order.
\end{lemma}
When $\kk^m = \mn$ and $\weight(z_i) = x_i$, the multidegree
$[L]_{\ZZ^n}$ of a coordinate subspace $L = $ zero set of
$\$ is just the monomial $\xx^L := x_{i_1}
\cdots x_{i_r}$. Therefore multidegrees can always be expressed as
positive sums of monomials.
% , by virtue of their decompositions in Theorem~\ref{t:additive} and
% their stability in Lemma~\ref{l:IN} under Gr\"obner degeneration.
%
% positive formulae abound:
\begin{cor} \label{c:positive}
Suppose $\LL$ is the zero scheme of an initial ideal\/ $\IN(I(\ol X_w))$
of the ideal of\/ $\ol X_w$ for some term order. The equality $[\ol
X_w]_{\ZZ^n} = \sum_L \mult_L(\LL) \cdot \xx^L$ writes the multidegree
$\SS_w(\xx)$ of $\ol X_w$ as a sum of monomials with positive
coefficients, where the sum is over reduced subspaces of $\LL$ having
maximal dimension.
\end{cor}
\subsection{Gr\"obner bases, antidiagonals, and Hilbert series}\label{sub:gb}
A positive sum as in Corollary~\ref{c:positive}
% does not automatically lend themselves
lends itself to combinatorial analysis only if we understand the initial
ideal. Theorem~\ref{t:gb}, which determines an explicit initial ideal,
will therefore be our central result. Ultimately it connects the
geometry of Schubert varieties
% directly
to the combinatorics of permutations, using the methods of
Section~\ref{sec:rc} (which are themselves based on
% combinatorial considerations
techniques in the proof of Theorem~\ref{t:gb}).
The matrix Schubert variety $\ol X_w$ is cut out set-theoretically by
determinants in the generic matrix $Z$. These equations in fact define
$\ol X_w$ scheme-theoretically; see \cite{FulDegLoc} or
Corollary~\ref{c:Iw}, below.
\begin{defn}{} \label{d:Iw}
%\begin{defnlabeled}{{\cite[Section~3]{FulDegLoc}}}
Let $w \in S_n$ be a permutation and $r_{qp} = \rank(w^T\sub qp)$ for
each $q,p$.
\begin{thmlist}
\item
The \bem{Schubert determinantal ideal $I_w \subset \kk[\zz]$} is
generated by all minors in $Z\sub qp$ of size $1 + r_{qp}$ for all $q,p$,
where $Z = (z_{ij})$ is the matrix of variables.
\item
The \bem{antidiagonal ideal} $J_w$ is generated by the antidiagonals of
the minors of $Z = (z_{ij})$ generating $I_w$.
\end{thmlist}
Here, the \bem{antidiagonal} of a square matrix or a minor is the product
of the entries on the main antidiagonal.
\end{defn}
This broad class of determinantal ideals includes all ideals
``cogenerated by a fixed minor'', as in \cite{HerzogTrung}. More
generally, the generators of every ladder determinantal ideal coincide
with the generators of the Schubert determinantal ideal $I_w$ for some
\mbox{vexillary} (also known as 2143-avoiding, or single-shaped)
permutation~$w$. Special cases of these vexillary determinantal ideals
are the objects of study in \cite{ConcaLadDet, MotSoh1, MotSoh2,
ConcaHerLadRatSing, GoncMilMixLadDet, GonLakLadDetSchub}, for example.
Theorem~\ref{t:oracle} yields determinantal formulae for $\ZZ^{2n}$ and
$\ZZ^n$-graded multidegrees in these cases, because vexillary double
Schubert polynomials $\SS_w(\xx,\yy)$ are multiSchur polynomials; see
\cite{NoteSchubPoly,FulDegLoc}.
An \bem{antidiagonal term order} is any term order in which the lead\-ing
monomial of every minor is its antidiagonal; such orders are easy to
construct.
\begin{thm} \label{t:gb}
% If\/ $>$ is an antidiagonal term order, then $\IN_>(I_w) = J_w$;
For any antidiagonal term order, $\IN(I_w) = J_w$; in other words, the
union over $q,p$ of the $(1+r_{qp})$-minors in $Z\sub qp$ constitute a
Gr\"obner basis.
\end{thm}
The hardest step in the proof of Theorem~\ref{t:gb} shows that the
Hilbert series of $\{\cj w\}_{w \in S_n}$ satisfy the recursion defining
the \bem{Grothendieck polynomials} $\GG_w(\xx)$ \cite{LSgrothVarDrap}.
To be precise, $\GG_w(\xx)$ can be defined by downward induction on the
weak order of $S_n$, in analogy with Schubert polynomials. This time,
however, start with $\GG_{w_0}(\xx) = \prod_{i=1}^n (1-x_i)^{n-i}$ and
use the \bem{Demazure} or \bem{isobaric divided difference} operators
$\dem i$, which act by $\dem i(f) = (x_{i+1} f - x_i s_i
f)/(x_{i+1}-x_i)$. Demazure operators work for just as well on power
series, such as $H_w := H(\cj w;\xx)$ for $w \in S_n$, as they do on
polynomials.
\begin{thm} \label{t:Jw}
If\/ $\length(ws_i) < \length(w)$ then $H_{ws_i} = \dem i H_w$. Thus
\begin{eqnarray*}
H(\cj w; \xx) &=& \frac{\GG_w(\xx)}{\prod_{i=1}^n(1-x_i)^n}.
\end{eqnarray*}
\end{thm}
This Hilbert series calculation requires substantial tailor-made
combinatorics, giving rise to Section~\ref{sec:rc}. Assume
Theorem~\ref{t:Jw} henceforth in this exposition.
\smallskip
\begin{trivlist}
\item{\it Proof sketch for Theorem~\ref{t:gb}.\,} Directly from the
definitions of $\partial_i$ and $\dem i$, taking the lowest degree terms
in $\GG_w(\1-\xx)$ yields $\SS_w(\xx)$. Therefore the multidegree of
$\cj w$ equals~$\SS_w(\xx)$ and agrees with $[\ol X_w]_{\ZZ^n}$ by
Theorem~\ref{t:oracle}.
After (nontrivially) showing the dimension $\dim \ol X_w$ purity
of~$J_w$, an easy lemma concerning squarefree monomial ideals reveals why
the equality $[\ol X_w]_{\ZZ^n} = [\LL_w]_{\ZZ^n}$ and the containment
$\IN(I(\ol X_w)) \supseteq J_w$ imply that $\IN(I(\ol X_w)) = J_w$.
Since the containments $\IN(I(\ol X_w)) \supseteq \IN(I_w) \supseteq J_w$
are obvious, we conclude that $\IN(I(\ol X_w)) = \IN(I_w) =
J_w$.\hfill$\Box$
\end{trivlist}
\subsection{Applications}\label{sub:app}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
The two theorems in the previous section
% Theorems~\ref{t:gb} and~\ref{t:Jw}
provide formulae for the $K$-polynomials (i.e.\ Hilbert series) of
Schubert determinantal varieties.
\begin{cor} \label{c:Iw}
The ideal of\/ $\ol X_w$ is $I_w$, and\/
% $\KK(\ol X_w;\xx) = $
$\KK(\ci w;\xx) = \GG_w(\xx)$.
\end{cor}
\begin{proof}
That $I_w$ is reduced follows from Theorem~\ref{t:gb} and the fact that
$J_w$ is reduced. The advertised $K$-polynomial comes from
Theorem~\ref{t:gb} and
% the $S_n$-symmetry of the denominator in
Theorem~\ref{t:Jw}.
\end{proof}
% $\KK(\ol X_w;\xx) = \GG_w(\xx)$,
Being in $K$-theory rather than cohomology, Corollary~\ref{c:Iw} is
substantially stronger than Theorem~\ref{t:oracle}. Although the former
also follows directly from known results \cite{LSgrothVarDrap} with only
a little work (the class of the structure sheaf of $\ol X_w$ in
$K^\circ_T(\mn)$ maps to that of $X_w$ in $K^\circ(\FL)$), the Hilbert
series in Theorem~\ref{t:gb} must in any case be computed during the
course of proving Theorem~\ref{t:gb}. Therefore we recover the
appropriate results from \cite{LSgrothVarDrap} as~consequences.
% A crucial consequence of Theorem~\ref{t:gb} is the fact that $\IN(I_w)$
% is squarefree, each of its generators being a term in a determinant.
The antidiagonal ideal $J_w$ is the Stanley--Reisner ideal for a
simplicial complex~$\LL_w$ (thought of as a set of subspaces in $\mn$).
The combinatorial implications of Theorem~\ref{t:Jw} and the following
corollary will be clarified after our analysis of the simplicial
complexes $\LL_w$ for $w \in S_n$ and their generalizations to arbitrary
Coxeter groups, which occupies all of Section~\ref{sec:rc}.
\begin{cor} \label{c:gb}
$\SS_w(\xx) = [\ol X_w]_{\ZZ^n} = [\LL_w]_{\ZZ^n} = \sum_{\facets\ L \in
\LL_w} \xx^L$.
\end{cor}
% The point of Corollary~\ref{c:gb} is the positive formula for
% $\SS_w(\xx)$ as a sum over the facets of~$\LL_w$. However, the
% equality $[\ol X_w]_{\ZZ^n} = \SS_w(\xx)$
The set of minors in $I_w$ forming a minimal (but not reduced) Gr\"obner
basis can be characterized in terms of essential sets \cite{FulDegLoc}.
As a consequence, we crystallize the relation between determinantal
ideals and open subsets (``opposite cells'') in Schubert varieties of
$\FL$. In particular, let $\mathfrak C$ be a \bem{local condition},
meaning that $\mathfrak C$ holds for a variety whenever it holds on each
subvariety in some open cover. Such local conditions include normality,
Cohen--Macaulayness, and rational singularities.
\begin{thm} \label{t:localcond}
Assume that the local condition $\mathfrak C$ holds for a variety $X$
whenever it holds for the product of $X$ with any vector space. Then
$\mathfrak C$ holds for every Schubert variety in every flag variety if
and only if $\mathfrak C$ holds for all matrix Schubert varieties.
\end{thm}
Theorem~\ref{t:localcond} serves to systematize and even reverse the flow
of results from the algebraic geometry of flag manifolds to
% \cite{FulDegLoc,ConcaHerLadRatSing} and the other
the literature on determinantal ideals.
% , thereby recovering results proved by a number of authors
% \cite{ramanathanCM,RamRamNormSchub,FulDegLoc,ConcaHerLadRatSing}.
However, we know of no new consequences that can be derived from it.
\subsection{An example}\label{sub:ex}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
The following example illustrates the results thus far.
% as well as some of what is to come.
% and serves also to introduce some notation for the results yet to come.
\begin{example} \label{ex:2143}
Let $w=2143 \in S_4$.
% (all our permutations will be written in one-line, not cycle,
% notation).
The matrix Schubert variety $\ol X_w$ is then the set of $4\times 4$
matrices $Z = (z_{ij})$ whose upper left entry is zero and whose upper
left $3\times 3$ block has rank at most one. The equations defining
$\ol X_{2143}$ are the determinants
\begin{eqnarray*}
I_{2143} &=& \Big\< z_{11}, \quad
\det
\left|\begin{array}{ccc}z_{11}&z_{12}&z_{13}\\
z_{21}&z_{22}&z_{23}\\
z_{31}&z_{32}&z_{33}\end{array}\right|
= -z_{13} z_{22} z_{31} + \ldots
\Big\>.
\end{eqnarray*}
Note that this is {\em not} a Gr\"obner basis with respect to
term orders that pick out the diagonal term $z_{11} z_{22} z_{33}$ of
the second generator, since $z_{11}$ divides that.
The term orders that interest us pick out
the \emph{anti}\/diagonal term $-z_{13} z_{22} z_{31}$.
When we Gr\"obner-degenerate the matrix Schubert variety to the scheme
defined by the initial ideal $J_{2143} = \$, we get a union of three coordinate subspaces
$$
L_{11,13}, L_{11,22}, \hbox{ and } L_{11,31}, \quad\hbox{with
ideals}\quad \, \, \hbox{ and }
\.
$$
The resulting equation in $T$-equivariant cohomology, or on
multidegrees, reads:
$$
\begin{array}{cccccccccc}
[\ol X_{2143}]_{\ZZ^n}
&=& [L_{11,13}]_{\ZZ^n} &+& [L_{11,22}]_{\ZZ^n} &+& [L_{11,31}]_{\ZZ^n}
%\\ &=& \weight(z_{11}z_{13})&+&\weight(z_{11}z_{22})&+&\weight(z_{11}z_{31})
\\ &=& x_1^2&+&x_1x_2&+&x_1x_3
\end{array}
$$
in $\ZZ[x_1,x_2,x_3,x_4] \cong H^*_T(M_4)$. The
$\ZZ^n$-graded
% Hilbert series of $I_{2143}$ is $H(\ci{2143};\xx) =
% (1-x_1)(1-x_1x_2x_3)/(1-x_1)(1-x_2)(1-x_3)$
$K$-polynomial $\KK(\ci{2143};\xx)$ equals $(1 - x_1)(1 - x_1x_2x_3) =
\GG_{2143}(\xx)$.
% $ = 1 - x_1 - x_1x_2x_3 + x_1^2x_2x_3 = \GG_{2143}(\xx)$.
Thus
\begin{eqnarray*}
\KK(\ci{2143};\1-\xx) &=& x_1(x_1 + x_2 + x_3 - x_1x_2 - x_1x_3 -
x_2x_3 + x_1x_2x_3),%\:\ =\:\ \GG_{2143}(\1-\xx).
\end{eqnarray*}
% $(1-x_1)(1-x_2)(1-x_3) = 1 - x_1 - x_2 - x_3 + x_1x_2 + x_1x_3 + x_2x_3
% - x_1x_2x_3$
whose lowest degree terms agree with $\SS_{2143}(\xx) = [\ol
X_{2143}]_{\ZZ^n} = x_1(x_1+x_2+x_3)$.\hfill
\end{example}
%\end{section}{Gr\"obner bases and multidegrees}%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Mitosis, rc-graphs, and subword complexes}%%%%%%%%%%%%%%%%%%%%%%
\label{sec:rc}
\subsection{Pipe dreams and rc-graphs}\label{sub:pipe}%%%%%%%%%%%%%%%%%%%
The facets of the initial complex $\LL_w$ correspond to certain subsets
of the grid $[n] \times [n]$. The obvious question becomes: which
subsets? The answer rests on drawing subsets of the grid in the
``right'' way.
\begin{defn} \label{d:pipe}
A \bem{pipe dream} %
%%
% \footnote{In the game Pipe Dream, the player is supposed to guide
% water flowing out of a spigot at one edge of the game board to
% its destination at another edge by laying down given square tiles
% with pipes going through them.
%% This also explains the term \bem{elbow joints}.
% Definition~\ref{d:rc} interprets the spigot placements and
% destinations.}
%%
is a finite subset of $\ZZ_{> 0} \times \ZZ_{> 0}$, identified as the set
of crosses in a tiling by \bem{crosses} $\textcross$ and \bem{elbow
joints} $\textelbow$.%
\end{defn}
\begin{example}
Pictorially, each subspace $L_{11,13}$, $L_{11,22}$, and $L_{11,31}$
from Example~\ref{ex:2143} represents a subset of the $4 \times 4$
grid: place a \cross in each box containing a generator for its ideal.
In other words, given a coordinate subspace~$L$, form the diagram
$D_L$ by placing a \cross at $(i,j)$ if every matrix in $L$ has
$(i,j)$ entry zero:
\begin{rcgraph}
\hbox{\normalsize{$\\ =\ $}}\
\begin{array}{|c|c|c|c|}
\multicolumn{4}{c}{}
\\[-2.5ex]
\hline\!+\!& &\!+\!&
\\\hline &\ \, & &\ \,
\\\hline & & &
\\\hline & & &
\\\hline
\end{array}
\:
\hbox{\normalsize{$,\quad\\ =\ $}}\
\begin{array}{|c|c|c|c|}
\multicolumn{4}{c}{}
\\[-2.5ex]
\hline\!+\!& &\ \, &\ \,
\\\hline &\!+\!& &
\\\hline & & &
\\\hline & & &
\\\hline
\end{array}
\:
\hbox{\normalsize{$,\quad\\ =\ $}}\
\begin{array}{|c|c|c|c|}
\multicolumn{4}{c}{}
\\[-2.5ex]
\hline\!+\!&\ \, &\ \, &\ \,
\\\hline & & &
\\\hline\!+\!& & &
\\\hline & & &
\\\hline
\end{array}
\end{rcgraph}
In the figures below, we draw the zero entries \cross by crossing
pipes, and the nonzero entries by elbow joints (imagine that the
lower-right triangle is filled with elbows).
$$
%\begin{rcgraph}
\qquad\qquad\
\begin{array}{ccccc}
&\perm1{}&\perm2{}&\perm3{}&\perm4{}\\
\petit2& \+ & \jr & \+ & \je \\
\petit1& \jr & \jr & \je &\\
\petit4& \jr & \je & &\\
\petit3& \je & & &\\
\end{array}
\qquad\qquad\hbox{}\qquad\
\begin{array}{ccccc}
&\perm1{}&\perm2{}&\perm3{}&\perm4{}\\
\petit2& \+ & \jr & \jr & \je \\
\petit1& \jr & \+ & \je &\\
\petit4& \jr & \je & &\\
\petit3& \je & & &\\
\end{array}
\qquad\qquad\hbox{}\qquad\
\begin{array}{ccccc}
&\perm1{}&\perm2{}&\perm3{}&\perm4{}\\
\petit2& \+ & \jr & \jr & \je \\
\petit1& \jr & \jr & \je &\\
\petit4& \+ & \je & &\\
\petit3& \je & & &\\
\end{array}
%\end{rcgraph}
$$
These are the three ``rc-graphs'', or ``planar histories'', for the
permutation $2143$.\hfill
%, and we recover the combinatorial formula from \cite{FKyangBax,BB} for
% the Schubert polynomial $[\ol X_w]$ in the case $w=2143$.\hfill
\end{example}
The term `rc-graph' was coined in \cite{BB}, although \cite{FKyangBax}
made the definition.
\begin{defn} \label{d:rc}
An \bem{rc-graph} is a pipe dream in which each pair of pipes crosses at
most once. If $D$ is an rc-graph and $w \in S_n$ is the permutation such
that the pipe entering row~$i$ exits from column $w(i)$, then $D$ is said
to be an \bem{rc-graph for $w$}. The set of rc-graphs for~$w$ is denoted
by $\rc(w)$.
\end{defn}
The next theorem completes the transition from the geometry of $\FL$ to
the combinatorics of $S_n$ through the algebra of determinants. Recall
that the
% travel
itinerary has been: Schubert variety~$X_w \goesto$ matrix Schubert
variety~$\ol X_w \goesto$ determinantal ideal~$I_w \goesto$ antidiagonal
ideal~$J_w \goesto$ initial complex~$\LL_w \goesto$ rc-graphs~$\rc(w)$.
\begin{thm} \label{t:rc}
$\rc(w) = \{D_L \mid L$ is a facet of $\LL_w\}$. In other words,
rc-graphs for~$w$ are complements of maximal supports of monomials
outside $J_w$.
\end{thm}
The proof uses results of \cite{BB}. Theorem~\ref{t:rc} has the famous
`BJS' formula as a consequence, by Corollary~\ref{c:gb}. Previous proofs
\cite{BJS,FSnilCoxeter} were combinatorial.
\begin{cor} \label{c:BJS}
$\SS_w(\xx)\ =\ \sum_{D \in \rc(w)} \xx^D$, where\/ $\xx^D = \prod_{(i,j)
\in D} x_i$.
\end{cor}
\subsection{Mitosis algorithm}\label{sub:mitosis}%%%%%%%%%%%%%%%%%%%%%%%%
The proof in Section~\ref{sub:gb} that the $K$-polynomial of $\cj w$
equals $\GG_w(\xx)$ works by constructing an operator $\ddem iw$ that
takes each monomial outside $J_w$ to a positive sum of monomials
outside~$J_{ws_i}$.
% The coarsening of $\ddem iw$ to the $\ZZ^n$-grading yields simply $\dem
% i$.
Interpreted in terms of rc-graphs, this procedure lists the coefficients
of Schubert polynomials by downward induction on the weak order of~$S_n$.
Our algorithm serves as a geometrically motivated improvement on the
famous conjecture of Kohnert \cite[Appendix to Chapter IV, by N.\
Bergeron]{NoteSchubPoly}, which is similarly inductive but employs Rothe
diagrams instead of rc-graphs.
Given a pipe dream in $[n] \times [n]$, define the column index
\begin{eqnarray*}% \label{eq:pipestart}
\start_i(D) &=& \min(\{j \mid (i,j) \not\in D\} \cup \{n+1\})
\end{eqnarray*}
of the leftmost empty box in row~$i$. Thus in the region to the left of
$\start_i(D)$, the $i^\th$ row of $D$ is filled solidly with crosses.
Let
\begin{eqnarray*}
\JJ_i(D) &=& \{\hbox{columns $j$ strictly to the left of } \start_i(D)
\mid (i+1,j) \hbox{ has no cross in } D\}
\end{eqnarray*}
For $p \in \JJ_i(D)$, construct the \bem{offspring} $D_p$ as follows.
First delete the cross at $(i,p)$ from $D$. Then take all of the crosses
in row~$i$ of $\JJ_i(D)$ that are to the left of column~$p$,
% in~$D$
and move each one down to the empty box below it in row~$i+1$.
\begin{defn} \label{d:mitosis}
The $i^\th$ \bem{mitosis} operator sends a pipe dream $D$ to
\begin{eqnarray*}
\mitosis_i(D) &=& \{D_p \mid p \in \JJ_i(D)\}.
\end{eqnarray*}
Write $\mitosis_i({\mathcal P}) = \bigcup_{D \in {\mathcal P}}
\mitosis_i({\mathcal P})$ whenever ${\mathcal P}$ is a set of pipe
dreams.%
\end{defn}
Observe that all of the action takes place in rows~$i$ and~$i+1$, and
$\mitosis_i(D)$ is an empty set whenever $\JJ_i(D)$ is empty.
\begin{example}
The left pipe dream $D$ below is an rc-graph for $w = 13865742$.
$$
\def\hln{\\[-.2ex]\hline}
\begin{tinyrc}{
\begin{array}{@{}cc@{}}{}\\\\3&\\4\\\\\\\\\\\\\\\end{array}
\begin{array}{@{}|@{\,}c@{\,}|@{\,}c@{\,}|@{\,}c@{\,}|@{\,}c@{\,}
|@{\,}c@{\,}|@{\,}c@{\,}|@{\,}c@{\,}|@{\,}c@{\,}|@{}}
\hline & + & & + & + & & &
\hln & + & & & & + & &\phantom{+}
\hln + & + & + & + & & & &
\hln & & + & & & & &
\hln + & & & & & & &
\hln + & + & & & & & &
\hln + & & & & & & &
\hln & & & & & &\phantom{+}&
\\\hline\multicolumn{4}{@{}c@{}}{}&\multicolumn{1}{@{}c@{}}{\!\!\uparrow}
\\\multicolumn{4}{c}{}&\multicolumn{1}{@{}c@{}}{\makebox[0pt]{$\start_3$}}
\end{array}
\begin{array}{@{\quad}c@{\ }}
\longmapsto\\\mbox{}\\\mbox{}
\end{array}
\begin{array}{c}
\left\{\
\begin{array}{@{}|@{\,}c@{\,}|@{\,}c@{\,}|@{\,}c@{\,}|@{\,}c@{\,}
|@{\,}c@{\,}|@{\,}c@{\,}|@{\,}c@{\,}|@{\,}c@{\,}|@{}}
\hline & + & & + & + & & &
\hln & + & & & & + & &\phantom{+}
\hln & + & + & + & & & &
\hln & & + & & & & &
\hln + & & & & & & &
\hln + & + & & & & & &
\hln + & & & & & & &
\hln & & & & & &\phantom{+}&
\\\hline
\end{array}
\ ,\
\begin{array}{@{}|@{\,}c@{\,}|@{\,}c@{\,}|@{\,}c@{\,}|@{\,}c@{\,}
|@{\,}c@{\,}|@{\,}c@{\,}|@{\,}c@{\,}|@{\,}c@{\,}|@{}}
\hline & + & & + & + & & &
\hln & + & & & & + & &\phantom{+}
\hln & & + & + & & & &
\hln + & & + & & & & &
\hln + & & & & & & &
\hln + & + & & & & & &
\hln + & & & & & & &
\hln & & & & & &\phantom{+}&
\\\hline
\end{array}
\ ,\
\begin{array}{@{}|@{\,}c@{\,}|@{\,}c@{\,}|@{\,}c@{\,}|@{\,}c@{\,}
|@{\,}c@{\,}|@{\,}c@{\,}|@{\,}c@{\,}|@{\,}c@{\,}|@{}}
\hline & + & & + & + & & &
\hln & + & & & & + & &\phantom{+}
\hln & & + & & & & &
\hln + & + & + & & & & &
\hln + & & & & & & &
\hln + & + & & & & & &
\hln + & & & & & & &
\hln & & & & & &\phantom{+}&
\\\hline
\end{array}
\ \right\}
\\
\begin{array}{c}
\mbox{}\\
\mbox{}\\
\end{array}
\end{array}
}\end{tinyrc}
$$
The set of three pipe dreams on the right is obtained by applying
$\mitosis_3$, since $\JJ_3(D)$ consists of columns $1$, $2$, and
$4$.\hfill
\end{example}
\begin{thm} \label{t:mitosis}
$\rc(ws_i)$ is the disjoint union $\bigcupdot_{D \in \rc(w)}
\mitosis_i(D)$. Therefore, if $s_{i_1} \cdots s_{i_k}$ is a reduced
expression for $w_0w$ and $D_0$ is the unique rc-graph for $w_0$, then
\begin{eqnarray*}% \label{eq:alg}
\rc(w) &=& \mitosis_{i_k} \cdots \mitosis_{i_1}(D_0).
\end{eqnarray*}
\end{thm}
The unique rc-graph $D_0$ in Theorem~\ref{t:mitosis} has crosses strictly
above the main antidiagonal, and no other crosses. That is, $(i,j) \in
D_0$ if and only if $i + j \leq n$.
Although combinatorial considerations in the proof of Theorem~\ref{t:gb}
were instrumental in figuring out how to define mitosis in the first
place, it is possible to give a complete proof of Theorem~\ref{t:mitosis}
based entirely on the BJS formula in Corollary~\ref{c:BJS} and the
characterization of Schubert polynomials by divided differences, along
with elementary combinatorial properties of rc-graphs. This argument
exploits an involution on $\rc(w)$ which, for grassmannian (i.e.\ unique
descent) permutations~$w$, reduces to a well-known
% symmetry for
involution on \mbox{semistandard Young tableaux.}
% of appropriate shape and content.
\subsection{Subword complexes}\label{sub:subword}%%%%%%%%%%%%%%%%%%%%%%%%
Given a pipe dream $D$, say that a \cross at $(q,p) \in D$ sits on the
\bem{$i^\th$ antidiagonal} if $q+p-1 = i$. Let $Q_D$ be the ordered list
of simple reflections $s_i$ corresponding to the antidiagonals on which
the crosses sit, starting from the northeast corner of $D$ and reading
{\em right to left}\/ across each row starting from the top and snaking
downwards. Induction on the number of crosses in~$D$ proves:
\begin{lemma} \label{l:subword}
The list $Q_D$ constitutes a reduced expression for $w$ if and only if
the pipe dream $D$ is an rc-graph for~$w$.
\end{lemma}
For example, the rc-graph $D_0$ in Theorem~\ref{t:mitosis} corresponds to
the reduced exression $w_0 = s_4s_3s_2s_1s_4s_3s_2s_4s_3s_4$ when $n =
5$, while the full $3 \times 3$ grid yields the list
$s_3s_2s_1s_4s_3s_2s_5s_4s_3$ of adjacent transpositions in~$S_6$.
Here is the generalization of $\LL_w$ to arbitrary words in Coxeter
systems $(\Pi,\Sigma)$.
\begin{defn} \label{d:subword}
A \bem{word} of size~$m$ is an ordered list $Q = (\sigma_1, \ldots,
\sigma_m)$ of elements of~$\Sigma$. An ordered sublist $P$ of $Q$ is
called a \bem{subword} of $Q$.
\begin{thmlist}
\item
$Q$ \bem{represents} $\pi \in \Pi$ if the ordered product of the simple
reflections in $Q$ is a reduced decomposition for $\pi$.
\item
$Q$ \bem{contains} $\pi \in \Pi$ if some sublist of $Q$ represents $\pi$.
\end{thmlist}
The \bem{subword complex} $\Delta(Q,\pi)$ is the set of subwords $P
\subseteq Q$ whose complements $Q \minus P$ contain $\pi$.
\end{defn}
\begin{example}
Theorem~\ref{t:rc} and Lemma~\ref{l:subword} say that if $\Pi = S_{2n}$
and $Q_{n \times n}$ is the word represented by all of $[n] \times [n]$,
then $\LL_w = \Delta(Q_{n \times n},w)$ when \mbox{$w \in S_n \subset
S_{2n}$}. Thus the combinatorics and Stanley--Reisner theory of general
subword complexes yields information about Schubert and Grothendieck
polynomials; see Corollary~\ref{c:links}.
\end{example}
\begin{thm} \label{t:subword}
Every subword complex $\Delta(Q,\pi)$ is vertex-decomposable and thus
Cohen--Macaulay, and even shellable. $\Delta(Q,\pi)$ is homeomorphic to
a ball or sphere.
\end{thm}
The vertex decomposition rests on the fact that the link and deletion of
the vertex $\sigma_1 \in \Delta(Q,\pi)$ are both subword complexes. The
ball or sphere condition is equivalent to $\Delta(Q,\pi)$ being a
manifold, given shellability; it reduces to showing that every
codimension~1 face lies in at most two facets, which in turn relies on
the strong exchange condition in Coxeter groups
\cite[Theorem~5.8]{HumphCoxGrps}.
% Even when $\Delta(Q,\pi)$ is a cone, it is a cone over another subword
% complex (instead of some other manifold).
In view of \cite{BWbruhCoxetShel}, Theorem~\ref{t:subword} suggests that
the Bruhat and weak orders ``feel'' somewhat similar.
Fulton proved that $\ol X_w$ is Cohen--Macaulay \cite{FulDegLoc}, but he
used Cohen--Macaulay\-ness of Schubert varieties \cite{ramanathanCM} to
do it. Here we provide new proofs of both.
\begin{cor} \label{c:cm}
Every matrix Schubert variety $\ol X_w$, and hence every Schubert variety
$X_w \subseteq B\dom\gln$, is Cohen--Macaulay.
\end{cor}
\begin{proof}
The Cohen--Macaulayness of $\LL_w$ in Theorem~\ref{t:subword} implies
that of $\ol X_w$ by Theorem~\ref{t:gb} and the flatness of Gr\"obner
degeneration.
% See \cite{ConcaHerLadRatSing}, beginning of proof of 2.1 on p. 127
Now use Theorem~\ref{t:localcond}.
\end{proof}
\subsection{Combinatorics of Grothendieck polynomials}\label{sub:groth}%%
Calculating the $\ZZ^m$-graded Hilbert series (that is, the
$K$-polynomial) of the Stanley--Reisner ring
% $k[\zz]/I_{\Delta}$
for a simplicial ball or sphere $\Delta$ amounts to identifying the
boundary faces of $\Delta$.
% By Theorem~\ref{t:subword} this holds
For subword complexes $\Delta(Q,\pi)$, this identification uses a
standard tool from Coxeter group theory.
\begin{defn} \label{d:prod}
Let $R$ be a commutative ring, and $\cD$ a free $R$-module with basis
$\{e_{\pi} \mid \pi \in \Pi\}$. Defining a multiplication on $\cD$ by
\begin{eqnarray} \label{eq:prod}
e_\pi e_\sigma &=& \left\{\begin{array}{ll}
e_{\pi\sigma} & \hbox{if } \length(\pi\sigma) > \length(\pi)\\
e_{\pi} & \hbox{if } \length(\pi\sigma) < \length(\pi)
\end{array}\right.
\end{eqnarray}
for $\sigma \in \Sigma$ yields the \bem{Demazure algebra} of
$(\Pi,\Sigma)$ over $R$. Define the \bem{Demazure product} $\delta(Q)$
of the word $Q = (\sigma_1, \ldots, \sigma_m)$ by $e_{\sigma_1} \cdots
e_{\sigma_m} = e_{\delta(Q)}$.
\end{defn}
When $\Pi = S_n$ and $\Sigma$ is the set of simple reflections $s_1,
\ldots, s_{n-1}$, the algebra $\cD$ is generated over $R$ by the usual
Demazure operators $\dem i$ (hence the name ``Demazure algebra''). In
general, the fact that the equations in~(\ref{eq:prod}) define an
associative algebra is a special case of
\cite[Theorem~7.1]{HumphCoxGrps}.
\begin{prop} \label{p:boundary}
A face $Q \minus P$ is in the boundary of $\Delta(Q,\pi)$ if and only if
$P$ has Demazure product $\delta(P) \neq \pi$.%
\end{prop}
In our final theorem, the variables $\zz = z_1,\ldots,z_m$ are identified
with the locations in the list $Q = (\sigma_1,\ldots,\sigma_m)$---that
is, with the vertices of the subword complex $\Delta(Q,\pi)$. The
$\ZZ^n$-grading is the finest possible, with $n = m$. So as not to
confuse notation in applications with $\zz = (z_{ij})_{i,j=1}^n$, we
write $\ZZ^m$-graded $K$-polynomials in the variables~$\zz$, with each
$z_i$ having tautological exponential weight~$z_i$.
\begin{thm} \label{t:links}
$\!$If\/ $\length(\pi) = \ell$ and $J$ is the Stanley--Reisner ideal of
$\Delta(Q,\pi)$,~then
\begin{eqnarray*}
\KK(\kk[\zz]/J; \zz) &=& \sum_{\delta(P)=\pi} (-1)^{|P| - \ell}
(\1-\zz)^P,
\end{eqnarray*}
where $(\1-\zz)^P = \prod_{i \in P}(1-z_i)$.
\end{thm}
The proof uses Hochster's Betti number formula for the \bem{Alexander
dual ideal}
\begin{eqnarray*}
J^\star &=& \
\hbox{ contains } J\>,
\end{eqnarray*}
which appears in \cite{ER} and \cite{BCP} (for instance).
Theorem~\ref{t:links} then follows from the Alexander inversion formula:
\begin{prop} \label{p:inversion}
If $J \subseteq \kk[\zz]$ is a squarefree monomial ideal and $J^\star$ is
its Alexander dual ideal, then $\KK(\kk[\zz]/J;\zz) =
\KK(J^\star;\1-\zz)$.
\end{prop}
\noindent
The Alexander inversion formula can be interpreted as another way to
define $J^\star$.
As a special case of Theorem~\ref{t:links} we recover a formula for
double Grothendieck polynomials \cite{FKgrothYangBax}. Although the
natural ``double'' specialization for the exponential weight of $z_{ij}$
is $x_i/y_j$, we substitute $z_{ij} \mapsto x_iy_j$ to agree with the
notation in \cite{FKgrothYangBax}.
% To make the statement easier, it is convenient to define the
% \bem{Demazure polynomial} for $w \in S_n$ having length~$\ell$ as the
% sum
% \begin{eqnarray*}
% \DD_w(\zz) &=& \sum_{\delta(D) = w} (-1)^{|D| - \ell} \zz^D
% \end{eqnarray*}
% over pipe dreams~$D$ with Demazure product~$w$, where $\zz^D =
% \prod_{(i,j) \in D} z_{ij}$. Note that $\DD_w(\zz) = \KK(\cj w;
% \1-\zz)$.
\begin{excise}{
\begin{eqnarray*}
\KK(\kk[\zz]/J; \zz) &=& \sum_{\delta(D) = w} \prod_{(i,j) \in D}
(-1)^{|D| - \ell} (1-x_i/y_j) \\ \KK(\kk[\zz]/J; \zz) &=&
\sum_{\delta(D) = w} \prod_{(i,j) \in D} (-1)^{|D| - \ell} (1-x_iy_j)
\\ \KK(\kk[\zz]/J; \zz) &=& \sum_{\delta(D) = w} \prod_{(i,j) \in D}
(-1)^{|D| - \ell} (1-(1-x_i)(1-y_j)) \\ \KK(\kk[\zz]/J; \zz) &=&
\sum_{\delta(D) = w} \prod_{(i,j) \in D} (-1)^{|D| - \ell}
(x_i+y_j-x_iy_j)
\end{eqnarray*}
}\end{excise}
\begin{cor} \label{c:links}
$\displaystyle \GG_w(\1-\xx,\1-\yy)\,\ = \sum_{\delta(D) = w}
\prod_{(i,j) \in D} (-1)^{|D| - \ell} (x_i + y_j - x_iy_j)$.
\medskip
\noindent
The
% (somewhat neater)
single version, in which $z_{ij} \mapsto x_i$ and\/ $\xx^D$ equals\/
$\prod_{(i,j) \in D} x_i$, reads:
\begin{eqnarray*}
\GG_w(\1-\xx) &=&
% \DD_w(\zz)|_{z_{qp} = x_q}\ \:=\ \:
\sum_{\delta(D)=w} (-1)^{|D| - \ell} \xx^D.
\end{eqnarray*}
\end{cor}
Note that Corollary~\ref{c:BJS} is the sum of lowest degree terms in the
latter formula.
%\end{section}{Mitosis, rc-graphs, and subword complexes}%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection*{Acknowledgements.}
This exposition is an extended abstract of \cite{grobGeom}. The authors
are grateful to Bernd Sturmfels, who took part in the genesis of that
project, and to Misha Kogan, as well as to Sara Billey, Anders Buch,
Cristian Lenart, Vic Reiner, Rich\'ard Rim\'anyi, Anne Schilling, Frank
Sottile, and Richard Stanley for inspiring conversations and references.
Nantel Bergeron kindly provided \LaTeX\ macros for drawing pipe dreams.
%AK was
%funded by the Clay Mathematics Institute for part of this project, the
%Alfred P. Sloan Foundation, and the NSF.
%EM was funded by the Alfred P. Sloan Foundation during the earlier stages of
%this project, and by the NSF thereafter.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\raggedbottom
\addcontentsline{toc}{section}{\numberline{}References}
\footnotesize
%\bibliographystyle{amsalpha}
%\bibliography{biblio}
\def\cprime{$'$}
\providecommand{\bysame}{\leavevmode\hbox to3em{\hrulefill}\thinspace}
\begin{thebibliography}{Hum90}
\bibitem[BB93]{BB}
Nantel Bergeron and Sara Billey, \emph{{RC}-graphs and {Schubert} polynomials},
Experimental Math. \textbf{2} (1993), no.~4, 257--269.
\bibitem[BCP99]{BCP}
Dave Bayer, Hara Charalambous, and Sorin Popescu, \emph{Extremal {B}etti
numbers and applications to monomial ideals}, J. Algebra \textbf{221} (1999),
no.~2, 497--512.
\bibitem[BJS93]{BJS}
Sara~C. Billey, William Jockusch, and Richard~P. Stanley, \emph{Some
combinatorial properties of {S}chubert polynomials}, J. Algebraic Combin.
\textbf{2} (1993), no.~4, 345--374.
\bibitem[Bri98]{BrionEqCohEqInt}
Michel Brion, \emph{Equivariant cohomology and equivariant intersection
theory}, Representation theories and algebraic geometry (Montreal, PQ, 1997),
Kluwer Acad. Publ., Dordrecht, 1998, Notes by Alvaro Rittatore, pp.~1--37.
\bibitem[BW82]{BWbruhCoxetShel}
Anders Bj{\"o}rner and Michelle Wachs, \emph{Bruhat order of {C}oxeter groups
and shellability}, Adv. in Math. \textbf{43} (1982), no.~1, 87--100.
\bibitem[CH97]{ConcaHerLadRatSing}
Aldo Conca and J{\"u}rgen Herzog, \emph{Ladder determinantal rings have
rational singularities}, Adv. Math. \textbf{132} (1997), no.~1, 120--147.
\bibitem[Con95]{ConcaLadDet}
Aldo Conca, \emph{Ladder determinantal rings}, J. Pure Appl. Algebra
\textbf{98} (1995), no.~2, 119--134.
\bibitem[EG98]{EGequivInt}
Dan Edidin and William Graham, \emph{Equivariant intersection theory}, Invent.
Math. \textbf{131} (1998), no.~3, 595--634.
\bibitem[ER98]{ER}
John~A. Eagon and Victor Reiner, \emph{Resolutions of {S}tanley-{R}eisner rings
and {A}lexander duality}, J. Pure Appl. Algebra \textbf{130} (1998), no.~3,
265--275.
\bibitem[FK94]{FKgrothYangBax}
Sergey Fomin and Anatol~N. Kirillov, \emph{Grothendieck polynomials and the
{Y}ang--{B}axter equation}, 1994, Proceedings of the Sixth Conference in
Formal Power Series and Algebraic Combinatorics, DIMACS, pp.~183--190.
\bibitem[FK96]{FKyangBax}
Sergey Fomin and Anatol~N. Kirillov, \emph{The {Y}ang-{B}axter equation,
symmetric functions, and {S}chubert polynomials}, Discrete Math. \textbf{153}
(1996), no.~1-3, 123--143, Proceedings of the 5th Conference on Formal Power
Series and Algebraic Combinatorics (Florence, 1993).
\bibitem[FR01]{FRthomPoly}
L{\'{a}}szl{\'{o}} Feh\'er and Rich{\'{a}}rd Rim{\'{a}}nyi, \emph{Classes of
degeneracy loci for quivers---the {Thom} polynomial point of view}, preprint
available at \textsf{http://www.cs.elte.hu/analysis/rimanyi/cikkek/}, 2001.
\bibitem[FS94]{FSnilCoxeter}
Sergey Fomin and Richard~P. Stanley, \emph{Schubert polynomials and the
nil-{C}oxeter algebra}, Adv. Math. \textbf{103} (1994), no.~2, 196--207.
\bibitem[Ful92]{FulDegLoc}
William Fulton, \emph{Flags, {S}chubert polynomials, degeneracy loci, and
determinantal formulas}, Duke Math. J. \textbf{65} (1992), no.~3, 381--420.
\bibitem[GL00]{GonLakLadDetSchub}
N.~Gonciulea and V.~Lakshmibai, \emph{Singular loci of ladder determinantal
varieties and {S}chubert varieties}, J. Algebra \textbf{229} (2000), no.~2,
463--497.
\bibitem[GM00]{GoncMilMixLadDet}
Nicolae Gonciulea and Claudia Miller, \emph{Mixed ladder determinantal
varieties}, J. Algebra \textbf{231} (2000), no.~1, 104--137.
\bibitem[HT92]{HerzogTrung}
J{\"u}rgen Herzog and Ng\^o~Vi\^et Trung, \emph{Gr\"obner bases and
multiplicity of determinantal and {P}faffian ideals}, Adv. Math. \textbf{96}
(1992), no.~1, 1--37.
\bibitem[Hum90]{HumphCoxGrps}
James~E. Humphreys, \emph{Reflection groups and {C}oxeter groups}, Cambridge
University Press, Cambridge, 1990.
\bibitem[Kaz97]{Kaz97}
M.~{\'E}. Kazarian, \emph{Characteristic classes of singularity theory}, The
Arnold-Gelfand mathematical seminars, Birkh\"auser Boston, Boston, MA, 1997,
pp.~325--340.
\bibitem[KM01]{grobGeom}
Allen Knutson and Ezra Miller, \emph{{Gr\"{o}bner} geometry of {Schubert}
polynomials}, \textsf{arXiv: math.AG/0110058}, also available at
\textsf{http://www-math.mit.edu/\~{}ezra}, 2001, in submission.
\bibitem[LS82a]{LSpolySchub}
Alain Lascoux and Marcel-Paul Sch{\"u}tzenberger, \emph{Polyn\^omes de
{S}chubert}, C. R. Acad. Sci. Paris S\'er. I Math. \textbf{294} (1982),
no.~13, 447--450.
\bibitem[LS82b]{LSgrothVarDrap}
Alain Lascoux and Marcel-Paul Sch{\"u}tzenberger, \emph{Structure de {H}opf de
l'anneau de cohomologie et de l'anneau de {G}rothendieck d'une vari\'et\'e de
drapeaux}, C. R. Acad. Sci. Paris S\'er. I Math. \textbf{295} (1982), no.~11,
629--633.
\bibitem[Mac91]{NoteSchubPoly}
I.~G. Macdonald, \emph{Notes on {S}chubert polynomials}, Publications du LACIM,
Universit{\`{e}} du Qu{\'{e}}bec {\`{a}} Montr{\'{e}}al, 1991.
\bibitem[MS96a]{MotSoh1}
J.~V. Motwani and M.~A. Sohoni, \emph{Divisor class groups of ladder
determinantal varieties}, J. Algebra \textbf{186} (1996), no.~2, 338--367.
\bibitem[MS96b]{MotSoh2}
J.~V. Motwani and M.~A. Sohoni, \emph{Normality of ladder determinantal rings},
J. Algebra \textbf{186} (1996), no.~2, 323--337.
\bibitem[Ram85]{ramanathanCM}
A.~Ramanathan, \emph{Schubert varieties are arithmetically {C}ohen-{M}acaulay},
Invent. Math. \textbf{80} (1985), no.~2, 283--294.
\bibitem[Tot99]{TotChowRing}
Burt Totaro, \emph{The {Chow} ring of a classifying space}, Algebraic
$K$-theory (Seattle, WA, 1997), Amer. Math. Soc., Providence, RI, 1999,
pp.~249--281.
\end{thebibliography}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\excise{
\vbox{\footnotesize \baselineskip 10pt
\bigskip\noindent
Department of Mathematics, University of California, Berkeley, CA
94720
e-mail: {\tt allenk@math.berkeley.edu}
\smallskip\noindent
Applied Mathematics, 2-363A, Massachusetts Institute of Technology, 77
Massachusetts Avenue,
Cambridge, MA 02139 \qquad email: {\tt ezra@math.mit.edu}}
}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{document}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%