A Construction of\\ Coxeter Group Representations (II)
Ron M. Adin% \thanks{Department of Mathematics
Ramat-Gan 52900
Francesco Brenti% \thanks{Dipartimento di Matematica
Universit\'{a} di Roma ``Tor Vergata''
Via della Ricerca Scientifica
00133 Roma
Yuval Roichman% \thanks{Department of Mathematics
An axiomatic approach to the representation theory of Coxeter groups and their Hecke algebras was presented in~\cite{U-I}. %This was carried out by a natural assumption on %the representation matrices and avoiding %a priori use of external concepts (such as Young tableaux). Combinatorial aspects of this construction are studied in this paper. In particular, the symmetric group case is investigated in detail. The resulting representations are completely classified and include the irreducible ones.
math0412506.tex
\documentclass[11pt]{article}
\usepackage{amsfonts}
\usepackage{latexsym}
\newcommand{\bbn}{{\mathbb N}}
\newcommand{\bbz}{{\mathbb Z}}
\newcommand{\bbq}{{\mathbb Q}}
\newcommand{\bbr}{{\mathbb R}}
\newcommand{\bbc}{{\mathbb C}}%{\mbox{\boldmath $C$}}
\newcommand{\bbf}{{\mathbb F}}%{\mbox{\boldmath $F$}}
\newcommand{\qed}{\hfill$\Box$}
\newcommand{\too}{\longrightarrow}
\newcommand{\then}{\Longrightarrow}
\newcommand{\der}{{\Delta\,}}%{{\bigtriangledown}}
\newcommand{\G}{{X}}%{{\Gamma}}
\newcommand{\C}{{\cal K}}
\newcommand{\T}{{\rho}}
\newcommand{\sn}{{\it span}}
\newcommand{\tr}{{\it Tr}}
\newcommand{\sh}{{\it sh}}
\newcommand{\cont}{{\it cont}}
\newcommand{\inv}{^{-1}}
\newcommand{\inver}{{\it inv}}
\newcommand{\D}{{\it Des}}
\newcommand{\des}{{\it des}}
\newcommand{\maj}{{\it maj}}
\newcommand{\DN}{{\it NDes}}
\newcommand{\N}{{\it Neg}}
\newcommand{\n}{{\it neg}}
\newcommand{\dn}{{\it ndes}}
\newcommand{\mn}{{\it nmaj}}
\newcommand{\fd}{{\it fdes}}
\newcommand{\fm}{{\it fmaj}}
\newcommand{\al}{\alpha}
\newcommand{\la}{\lambda}
\newcommand{\tw}{{\tilde{w}}}
\newcommand{\ts}{{\tilde{s}}}
\newcommand{\bs}{{\dot{s}}}
\newcommand{\hgt}{{ht}}
\newcommand{\hk}{{h}}
\newcommand{\ua}{{\dot{a}}}%{{\hat{a}}}%{{a}}  \dot\ddot\acute\grave\vec
\newcommand{\ub}{{\dot{b}}}%{{\hat{b}}}%{{b}}
\newcommand{\ud}{{\dot{d}}}%{{\hat{d}}}%{{d}}
\newcommand{\da}{{\ddot{a}}}%{{\check{a}}}%{{\bar a}}
\newcommand{\db}{{\ddot{b}}}%{{\check{b}}}%{{\bar b}}
\newcommand{\dd}{{\ddot{d}}}%{{\check{d}}}%{{\bar d}}
\newcommand{\oa}{{\vec a}}
\newcommand{\ob}{{\vec b}}
\newcommand{\aws}{{a_{wsw^{-1}}}}
\newcommand{\awt}{{a_{wtw^{-1}}}}
\newcommand{\awsts}{{a_{wstsw^{-1}}}}
\newcommand{\awtst}{{a_{wtstw^{-1}}}}

\newtheorem{thm}{Theorem}[section]
\newtheorem{pro}[thm]{Proposition}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{cla}[thm]{Claim}
\newtheorem{con}[thm]{Conjecture}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{fac}[thm]{Fact}
\newtheorem{prb}[thm]{Problem}
\newtheorem{exa}[thm]{Example}
\newtheorem{obs}[thm]{Observation}
\newtheorem{rem}[thm]{Remark}
\newtheorem{df}[thm]{Definition}


\newenvironment{note}[1]{\par\addvspace{\medskipamount}\noindent
                         {\bf {#1}}\sl
                       }{\par\addvspace{\medskipamount}\rm}

%\newcommand{\eqdef}{{\mathop=\limits^{\rm d}}}
%\newcommand{\eqdef}{\stackrel{\rm def}{=}}
\newcommand{\eqdef}{:=}
\newcommand{\suml}{\sum\limits}
\newcommand{\de}{\partial}
\newcommand{\half}{{1\over 2}}
\font\gotic=eufm10
\newcommand{\gots}{{\hbox{\gotic\char'123}}}

\begin{document}

\title{A Construction of\\ Coxeter Group Representations (II)}
\bibliographystyle{acm}
\author{Ron M. Adin%
\thanks{Department of Mathematics, Bar-Ilan University,
Ramat-Gan 52900, Israel. Email: {\tt radin@math.biu.ac.il}}\ $^\S$
\and Francesco Brenti%
\thanks{Dipartimento di Matematica,
Universit\'{a} di Roma ``Tor Vergata'',
Via della Ricerca Scientifica,
00133 Roma, Italy. Email: {\tt brenti@mat.uniroma2.it}}\ $^\S$
\and Yuval Roichman%
\thanks{Department of Mathematics, Bar-Ilan University,
Ramat-Gan 52900, Israel. Email: {\tt yuvalr@math.biu.ac.il}}
\thanks{Research of all authors was supported in part by
the Israel Science Foundation, founded by the Israel Academy of Sciences and Humanities
and
by the EC's IHRP Programme, within the Research Training Network ``Algebraic Combinatorics
in Europe'', grant HPRN-CT-2001-00272.}}
%and by internal research grants from Bar-Ilan University.}}
\date{submitted January 6, 2006; revised July 5, 2006\\ \medskip
Dedicated to Gordon James on the occasion of his 60th birthday}

%\subjclass{Primary 05E10, 13A50; Secondary 05A19, 13F20, 20C30.}

\maketitle

\begin{abstract}
An axiomatic approach to the representation theory of Coxeter
groups and their Hecke algebras was presented in~\cite{U-I}.
%This was carried out by a natural assumption on
%the representation matrices and avoiding
%a priori use of  external concepts (such as Young tableaux).
Combinatorial aspects of this construction are studied in this paper.
In particular,  the symmetric group case is investigated in detail.
The resulting representations are completely classified and
include the irreducible ones.
\end{abstract}

\section{Introduction}\label{s.intro}

\subsection{Outline}
An axiomatic construction of Coxeter group representations  was
presented in~\cite{U-I}.
 This was carried out by a natural assumption on the
representation matrices, avoiding a priori use of  external
concepts (such as Young tableaux).

\smallskip

Let $(W,S)$ be a Coxeter system, and let $\C$ be a finite subset of $W$.
Let $\bbf$ be a suitable field of characteristic zero (e.g., the
field $\bbc(q)$ in the case of the Iwahori-Hecke algebra), and let
$\T$ be a representation of (the Iwahori-Hecke algebra of) $W$ on
the vector space $V_{\C}:=\sn_{\bbf}\{C_w\,|\,w\in\C\}$, with
basis vectors indexed by elements of $\C$. We want to study the
sets $\C$ and representations $\T$ which satisfy the following
axiom:

\begin{itemize}
\item[$(A)$] {\it For any generator $s\in S$ and any element $w\in
\C$ there exist scalars $a_s(w),b_s(w)\in\bbf$ such that
$$
\T_s(C_w) = a_{s}(w)C_w + b_{s}(w)C_{ws}.
$$
If $w\in\C$ but $ws\not\in\C$ we assume $b_s(w)=0$.%
}
\end{itemize}

%\noindent
A pair $(\T,\C)$ satisfying Axiom $(A)$ is called an {\em abstract
Young (AY) pair;} $\T$ is an {\em AY representation,} and $\C$ is
an {\em AY cell.} If $\C\ne \emptyset$ and has no proper subset
$\emptyset \subset \C' \subset \C$ such that $V_{\C'}$ is
$\T$-invariant, then $(\T,\C)$ is called a {\em minimal AY pair.}
(This is much weaker than assuming $\T$ to be irreducible.)

%\bigskip

%Combinatorial aspects of this construction are studied in this
%paper. In particular,  the symmetric group case is investigated in
%detail. The resulting representations are completely classified
%and include the irreducible ones.

\medskip

In~\cite{U-I} it was shown that  an AY representation of a simply
laced Coxeter group is determined by a linear functional on the
root space. In this paper it is shown that, furthermore, the
values of the linear functional on the ``boundary" of the AY cell
determine the representation (see Theorem~\ref{t.7} below).
%\smallskip
In Section~\ref{s.cells_Sn} this result is used
%in the proof of the following result.
to characterize AY cells in the symmetric group.
%%AY cells in the symmetric group. are characterized in
%%Section~\ref{s.cells_Sn}.
% A subset $\C$ in the symmetric group $S_n$
%is a minimal AY cell if and only if there exists a standard Young
%tableau $Q$ of size $n$ such that
%$$
%\sigma^{-1}\C=\{\pi\in S_n|\ Q^{\pi\inv} \hbox{ is standard}\},
%$$
%where $Q^{\pi\inv}$ is the tableau obtained from $Q$ by replacing each
%entry $i$ by $\pi(i)$ and $\sigma\in \C$ (see Theorem~\ref{t.symm}
%below).
%
This characterization is then applied to show that every
irreducible representation of
%the symmetric group
$S_n$ may be realized as a minimal abstract Young representation
(see Theorem~\ref{t.irr} below). AY representations of Weyl groups
of type $B$ are not determined by a linear functional. However, it
is shown that a similar result holds for these groups
(Theorem~\ref{B.irr} below). Finally, we characterize the elements
$\pi\in S_n$ for which the interval $[id,\pi]$ forms a minimal AY
cell, carrying an irreducible representation (see
Theorem~\ref{t.s5} below).

%\bigskip

%Other results in the paper include combinatorial procedures for
%induction and restriction of AY representations, analogous to
%Barbasch-Vogan rules for Kazhdan-Lusztig
%representations~\cite{BV2} (see Section~\ref{s.induce} below), and
%study of interval AY cells (see Section~\ref{s.inter} below).
%%A summary of main results in the paper is given in
%%Section~\ref{s.main} below.

%\bigskip

%The rest of this paper is organized as follows.

\subsection{Main Results}\label{s.main}

%\subsubsection{General}



%The proof relies on the lattice property of the weak Bruhat order
%and its quotients (see~\cite[Theorem 4.1]{BW}).

%\medskip

In Section~\ref{s.bound} it is shown that the action of the group
$W$ on the boundary of a cell determines the representation up to
isomorphism.

\begin{thm}\label{t.7m}{\rm (see Theorem~\ref{t.7})}
%Thm 1:
Let $(\T,\C)$ be a minimal AY pair for a simply laced Coxeter group $W$,
where $\C$ is finite.
%Let $f$ be a $\C$ generic vector.
Then the behavior of $\T$ at the boundary of $\C$
(i.e., the values $a_{s}(w)$ for $w\in \C, s\in S, ws\not\in\C$)
determines $\T$ up to isomorphism.
%, where $\T^f$ is the associated AY representation defined in~\ref{d.CF}.
\end{thm}

The proof combines continuity arguments with the reduction of AY
representations to distinguished linear functionals, carried out
in~\cite{U-I} (see Theorems~\ref{t.main11} and~\ref{t.main12} below).

%\subsubsection{Symmetric Group}

AY cells in the symmetric group are characterized
%in~\cite[Theorem ???]{U-II}
in Section~\ref{s.cells_Sn}.

\begin{thm}\label{t.main.symm}{\rm (see Theorem~\ref{t.symm})}
Let $\C\subseteq S_n$
%be a nonempty subset of the symmetric group $S_n$,
and let $\sigma\in \C$. Then $\C$ is a minimal AY cell if and only
if there exists a standard skew Young tableau $Q$ of size $n$ such that
$$
\sigma^{-1}\C=\{\pi\in S_n|\ Q^{\pi\inv} \hbox{ is standard}\},
$$
where $Q^{\pi\inv}$ is the tableau obtained from $Q$ by replacing each
entry $i$ by $\pi\inv(i)$.
\end{thm}

The proof applies Theorem~\ref{t.7m} together with
Theorems~\ref{t.main11} and~\ref{t.main12} below.
%\begin{thm}{\rm (see Theorem~\ref{t.tabl2})}
%Let $(W,S)$ be the symmetric group $S_n$ with its standard Coxeter
%generators, and let $f$ be an integer-valued vector in $V$. Then
%$f$ is $\C$-generic, for some minimal AY cell $\C$ containing the
%identity element, if and only if $f$ is the content vector of a
%skew standard Young tableau.
%\end{thm}
%A combinatorial bijection between elements of minimal AY cells and
%standard Young tableaux of the same shape will be given (see
%Theorem~\ref{t.cell} below).
%\medskip
Theorem~\ref{t.main.symm} is then used to prove the following.

\begin{thm}\label{t.main.irr} {\rm (see Corollary~\ref{t.irr2})}
The complete list of minimal AY representations of the symmetric
group $S_n$ is given (up to isomorphism) by the skew Specht
modules $S^{\lambda/\mu}$, where $\la/\mu$ is of order $n$
(and $\mu$ possibly empty).

In particular, every irreducible representation of the symmetric
group $S_n$ may be realized as a minimal abstract Young
representation.
\end{thm}

Combining this theorem with the combinatorial induction rule for
minimal AY representations (Theorem~\ref{induction} below) we
prove

\begin{thm}\label{B.main.irr} {\rm (see Theorem~\ref{B.irr})}
Every irreducible representation of the classical Weyl group $B_n$
may be realized as a minimal abstract Young representation.
\end{thm}

%\bigskip

%Analogous results for finite and affine Weyl groups will be given
%in~\cite{U-III}.
%In particular, all irreducible representations of Weyl groups of type $B$
%are minimal AY.
%%A classification of the minimal abstract Young
%%representations will be carried out in~\cite{U-II}.

%\smallskip

% Interval AY cells are studied in Section~\ref{s.inter}.

\begin{df}\label{d.main.top}
%%Def'n:
%\begin{itemize}
%\item[1.] Elements $w\in W$ are called good elements if
%the interval $[id,w]$ is a minimal and simple AY cell
%(see Definition~\ref{i6} above).
%\item[2.]
An element $w\in W$ is a {\em top} element if the interval $[id,w]$
is a minimal AY cell carrying an {\em irreducible} AY representation of $W$.
%\end{itemize}
\end{df}

The top elements of the symmetric group $S_n$ are characterized in
Section~\ref{s.inter}.

\begin{thm}\label{t.main.s5} {\rm (see Theorem~\ref{t.s5})}
%Thm 11:
%The interval
%$[id,\pi]$ (in the right weak Bruhat order of $S_n$) is
%an irreducible AY cell for
A permutation $\pi\in S_n$ is a top element if and only if $\pi$
is the column word of a row standard Young tableau (see
Definition~\ref{d.row} below).
\end{thm}

\noindent{\bf Note:} %After completing a first version of this
Having completed the first version of this paper, we were informed that
results equivalent to Theorems~\ref{t.7m} and~\ref{t.main.irr},
with entirely different proofs, appear in~\cite{KR, Ram03b}.

\section{Preliminaries}\label{s.prelim}

For the necessary background on Coxeter groups see~\cite{Hum};
on convex sets and generalized descent classes see~\cite{BW};
and on symmetric group representations see~\cite{Ja, JK, Sa}.
See also~\cite{DJ, KL, OV, Ram03}.

%\medskip

\subsection{Young Forms}

%\noindent{\bf 2.1. Young Forms.}
Let $Q$ be a standard Young tableau of skew shape. 
If $k\in \{1,\dots,n\}$ is in box $(i,j)$ of $Q$ 
then the {\em content} of $k$ in $Q$ is $ c(k):= j - i$.
For  $1\le k < n$, the $k$th {\em hook-distance} is
defined as $ \hk(k):=c(k+1)-c(k)$.
Denote by $Q^{s_k}$ the tableau obtained from $Q$ by interchanging
$k$ and $k+1$. 
The classical Young orthogonal form for $S_n$ (see, e.g.,
\cite[\S 25.4]{Ja}) is generalized naturally to skew shapes.

\begin{thm}\label{t.yof-skew}
{\bf (Young Orthogonal Form for Skew Specht Modules)}
%{\rm\cite[\S 25.4]{Ja}}
Let $\{v_Q\,|\,Q$ standard Young tableau of shape $\la/\mu\}$
be the basis of the skew Specht module $S^{\la/\mu}$ obtained by
the Gram-Schmidt process from the polytabloid basis. Then
\begin{equation}\label{e.yofi}
\T^{\la/\mu}(s_i)(v_Q)= \frac{1}{\hk(i)}\,v_Q +
\sqrt{1-\frac{1}{\hk(i)^2}}\,v_{Q^{s_i}}.
\end{equation}
\end{thm}

\noindent{\bf Proof.}
(Due to J.\ Stembridge~\cite{Ste}; see also~\cite{Greene}.)
Matrices determined by (\ref{e.yofi})
must satisfy the Coxeter relations of $S_n$, because the same is true
when the skew tableaux are completed to full tableaux of non-skew shape.
Therefore they define a representation of $S_n$, which we denote
$Y^{\lambda/\mu}$. Upon restricting the action of $S_n$ to
$S_k\times S_{n-k}$ (where $n=|\lambda|, k=|\mu|$), $Y^\lambda$ decomposes
into the direct sum
$\bigoplus_{\{\mu\subseteq\lambda\,|\,|\mu|=k\}}Y^\mu \otimes Y^{\lambda/\mu}$.
On the other hand, Specht modules have exactly the same decomposition.
This follows, for example, from the corresponding identity on Schur
functions~\cite[(7.66)]{St2} (using the inverse Frobenius image).
Since $Y^\lambda\cong S^\lambda$, $Y^{\lambda/\mu}$ must be
isomorphic to $S^{\lambda/\mu}$.
\qed

\bigskip

$B_n$, the classical Weyl group of type $B$, is a Coxeter system
with $S=\{s_i|\ 0\le i<n\}$, $m(s_0,s_1)=4$,
$m(s_i,s_{i+1})=3$ for $1\le i<n$, and $m(s_i,s_j)=2$ otherwise.
The irreducible representations of $B_n$ are indexed by
pairs of partitions $(\lambda,\mu)$, where
$\lambda$ is a partition of some $0\le k\le n$ and
$\mu$ is a partition of $n-k$.
A basis for the irreducible representation of shape $(\lambda,\mu)$
may be indexed by all pairs $(P,Q)$ of standard Young tableaux of shapes
$\lambda$ and $\mu$, respectively, where
$P$ is a tableau on a subset of $k$ letters from $\{1,\dots,n\}$ and
$Q$ is a tableau on the complementary subset of letters.
There exists a basis such that the following Young form holds
(see, e.g., \cite{P}).

\begin{thm}\label{B-yof}{\bf (Classical Young Orthogonal Form for $B_n$)}
Denote the above basis elements by $v_{(P,Q)}$.
%Then for $1 \le i< n-1$,
%$$
%\rho^{\la,\mu}(s_i)(v_{(P,Q)}) =
%\cases{%
%\frac{1}{\hk(i)}\,v_{(P,Q)} +
%\sqrt{1-\frac{1}{\hk(i)^2}}\,v_{{(P,Q)}^{s_i}}, &if i,i+1  \quad
%\mbox{are in same tableaux};\cr v_{{(P,Q)}^{s_i}} & i,i+1  \quad
%\mbox{are in different tableaux},}
%$$
For $1\le i<n$ define the hook distance $\hk(i)$ as follows:
$$
\hk(i) :=
\cases{%
h_P(i), &if $i$ and $i+1$ are both in $P$;\cr
h_Q(i), &if $i$ and $i+1$ are both in $Q$;\cr
\infty, &if $i$ and $i+1$ are in different tableaux.}
$$
Then, for $1\le i<n$,
$$
\rho^{\la,\mu}(s_i)(v_{(P,Q)}) =
\frac{1}{\hk(i)}\,v_{(P,Q)} +
\sqrt{1-\frac{1}{\hk(i)^2}}\,v_{{(P,Q)}^{s_i}},
$$
where ${(P,Q)}^{s_i}$ is the pair of tableaux obtained from
$(P,Q)$ by interchanging $i$ and $i+1$, whereas
$$
\rho^{\la,\mu}(s_0)(v_{(P,Q)})=\cases{%
v_{(P,Q)}, &if $1$ is in $P$;\cr
-v_{(P,Q)}, &if $1$ is in $Q$.}
$$
\end{thm}

\subsection{Abstract Young Representations}

%\noindent{\bf 2.2. Abstract Young Representations.}
Recall the definition of AY cells and representations from the
introduction.

\begin{pro}\label{t.main.convex}{\rm\cite[Corollary 4.4]{U-I}}
Every minimal AY cell is convex in the Hasse diagram of the
%right Cayley graph
%$\G(W,S)$ or, equivalently, under
right weak Bruhat order.
% In particular, $b_s(w)\ne 0$ whenever $s\in S$ and $w, ws\in\C$.
\end{pro}

\begin{df}
For a convex subset $\C\subseteq W$ define:
\begin{eqnarray*}
T_{\C}          &:=& \{wsw^{-1}\,|\,s\in S,\,w\in \C,\,ws\in \C\},\\
T_{\partial \C} &:=& \{wsw^{-1}\,|\,s\in S,\,w\in \C,\,ws\not\in \C\}.%,\\
%T_{\bar\C}      &:=& \{wsw^{-1}\,|\,s\in S,\,w\in \C\}
%                = T_{\C} \cup T_{\partial \C}.
\end{eqnarray*}
\end{df}

\begin{df}\label{d.cg} ($\C$-genericity)\\
Let $\C$ be a convex subset of $W$ containing the identity element.
A linear functional $f$ on the root space $V$ is {\rm $\C$-generic} if:
\begin{itemize}
\item[{\bf (i)}]
For all $t\in T_{\C}$,
$$
\langle f,\al_t\rangle \not\in \{0, 1, -1\}.
$$
\item[{\bf (ii)}]
For all $t\in T_{\partial \C}$,
$$
\langle f,\al_t\rangle \in \{1, -1\}.
$$
\item[{\bf (iii)}]
If $w\in \C$, $s,t\in S$, $m(s,t)=3$ and $ws, wt\not\in \C$ then
$$
\langle f,\al_{wsw^{-1}}\rangle =
\langle f,\al_{wtw^{-1}}\rangle\;(= \pm1).
$$
\end{itemize}
\end{df}

%By Observation~\ref{t.main_unitcell}, we may assume that $id\in\C$.

By~\cite[Observation 3.3]{U-I}, we may assume that
$id\in\C$. By~\cite[Theorem 11.1]{U-I}, under mild conditions,
Axiom $(A)$ is equivalent to the following:

\begin{itemize}
\item[$(B)$] {\it For any reflection $t$ there exist scalars
$\ua_t, \ub_t, \da_t, \db_t \in\bbf$ such that, for all $s\in S$
and $w\in \C$:
$$
\T_s(C_w) =\cases{%
\ua_{wsw^{-1}}C_w+\ub_{wsw^{-1}}C_{ws}, &if $\ell(w)<\ell(ws)$;\cr
\da_{wsw^{-1}}C_w+\db_{wsw^{-1}}C_{ws}, &if
$\ell(w)>\ell(ws)$.\cr}
$$
%If $w\in\C$ and $ws\not\in\C$ we assume that $\ub_{wsw^{-1}}=0$
%(if $\ell(w)<\ell(ws)$) or
%$\db_{wsw^{-1}}=0$ (if $\ell(w)>\ell(ws)$).%
}
\end{itemize}

\begin{thm}\label{t.main11}{\rm\cite[Theorem 7.4]{U-I}}
Let $(W,S)$ be an irreducible simply laced Coxeter system,
and let $\C$ be a convex subset of $W$ containing the identity element.
%Let $\langle\ ,\ \rangle$ be an arbitrary positive definite
%bilinear form on the root space $V$.
If $f\in V^*$ is $\C$-generic then
$$
\ua_t := {1\over \langle f,\al_t\rangle}
\qquad(\forall t\in T_{\C} \cup T_{\partial\C}),
$$
together with $\da_t$, $\ub_t$ and $\db_t$ satisfying
\begin{eqnarray*}
\ua_t + \da_t &=& 0\\
\ub_t \cdot \db_t &=& (1 - \ua_t)(1 - \da_t)
\end{eqnarray*}
%$$
%\ua_{wsw^{-1}} := {1\over \langle f,\al_{wsw^{-1}}\rangle}
%\qquad(\forall w\in \C, s\in S),
%$$
%together with $\da_{wsw^{-1}}:=1-\ua_{wsw^{-1}}$, and
%$\ub_{wsw^{-1}}, \db_{wsw^{-1}}$ which satisfy the equation
%$\ub_{wsw^{-1}}\cdot \db_{wsw^{-1}}+\da_{wsw^{-1}}\cdot
%\ua_{wsw^{-1}}=1$,
%satisfying any one of the normalizations in Subsection~\ref{s.normal},
%satisfying conditions (a) and (b) of Lemma~\ref{t.l1} (with $q = 1$),
define a representation $\T$ such that $(\T,\C)$ is a minimal AY pair
satisfying Axiom $(B)$.
\end{thm}

The following theorem is complementary.

\begin{thm}\label{t.main12}{\rm\cite[Theorem 7.5]{U-I}}
Let $(W,S)$ be an irreducible simply laced Coxeter system
and let $\C$ be a subset of $W$ containing the identity element.
%Assume that $\ua_{wsw^{-1}}\ne 0$ ($\forall w\in \C, s\in S$
%%$t\in T_{\C}$
%).
If $(\T,\C)$ is a minimal AY pair satisfying Axiom $(B)$
and $\ua_t\ne 0$ ($\forall t\in T_{\C}$)
%and $\ua_{wsw^{-1}}\ne 0$ ($\forall w\in \C, s\in S$)
then
there exists a $\C$-generic $f\in V^*$ such that
%$$
%\ua_t={1\over \langle f,\al_t\rangle}\qquad (\forall t\in T_{\C} \cup T_{\partial \C}).
%$$
$$
\ua_t = \frac{1}{\langle f,\al_t\rangle}\qquad
(\forall\ t\in T_{\C} \cup T_{\partial\C}).
$$
%$$
%\ua_{wsw^{-1}}={1\over \langle f,\al_{wsw^{-1}}\rangle}\qquad
%(\forall\ w\in \C, s\in S).
%$$
\end{thm}

%For an Iwahori-Hecke algebra analogue see~\cite[Theorem t.rep2f.q]{U-I}.

%\bigskip

%Extended Young orthogonal forms (for simply laced groups) follow.
%See~\cite[Theorem~\ref{t.yof1}]{U-I} and~\ref{???} below.

The following combinatorial rule for induction of AY
representations is analogous to the one for Kazhdan-Lusztig
representations~\cite{BV2,Geck}.

%, proved by Barbasch and Vogan for Weyl groups~\cite[Prop.
%3.15]{BV2} and by Geck for Coxeter groups \cite{Geck}. For other
%closely related results see~\cite{Sc, GR, Ro}.


\begin{thm}\label{induction}{\rm \cite[Theorem 9.3]{U-I}}
Let $(W,S)$ be a finite Coxeter system, $P=\langle J\rangle$
$(J\subseteq S)$ a parabolic subgroup,
%Let $\cal D$ a minimal AY cell for $P$ and let $\rho^{\cal D}$ be an AY
%representation of $P$ associated to $\cal D$.
and $W^J$ the set of all representatives of minimal length of the
right cosets of $P$ in $W$. Let $(\psi,\cal D)$ be a minimal AY
pair for $P$. Then
\begin{itemize}
\item[1.]
${\cal D} W^J$ is a minimal AY cell for $W$.
\item[2.]
The induced representation $\psi\uparrow ^W_P$ is isomorphic to
an AY representation on $V_{{\cal D} W^J}$.
\end{itemize}
\end{thm}

\begin{rem}\label{induction1}
By~\cite[Lemma 9.7]{U-I}, for every $s\in S$ and $r\in W^J$
either $rs\in W^J$, or $rs\not\in W^J$ and $rs=pr$ with $p\in J$.
Then, by the proof of~\cite[Theorem 9.3]{U-I},
the representation matrices of the generators in the
resulting induced representation are as follows:
for $s\in S$, $m\in {\cal D}$, $r\in W^J$,
$$
\rho_s(C_{mr}) = \cases{%
C_{mrs}, &if $rs\in W^J$;\cr a_p(m)C_{mr} + b_p(m)C_{mrs},
&otherwise $(rs = pr,\,p\in J)$,}
$$
where the coefficients $a_p$ and $b_p$ are given by the AY
representation $\psi$; namely, $ \psi_p(C_m) = a_p(m) C_m + b_p(m)
C_{mp}.$
\end{rem}

\section{Boundary Conditions}\label{s.bound}

In this section it is shown that the action of the group $W$ on
the boundary of a minimal AY cell determines the representation up to isomorphism.


%\begin{thm}\label{t.1}
%Let $W$ be a finite Weyl (Coxeter??) group,
%and let $f\in V^*$ be $W$-generic (i.e. $\langle f,\al_t\rangle \ne 0, %\forall t\in T$).
%Then the corresponding representation $\T^f$
%on $W$ is isomorphic to the regular representation of $W$.
%\end{thm}

%\noindent{\bf Proof.}
%For any scalar $0\ne \mu\in \bbr$, the vector $\mu f\in V^*$ is also
%$W$-generic. By continuity arguments (on the entries of the matrices %representing each element $w\in W$),
%the representations $\T^{\mu f}$ and $\T^f$ are isomorphic (due to the %discreteness of characters).
%On the other hand, when $\mu\to \pm \infty$,
%$$
%a_s^{(\mu f)}(w)={1\over \langle \mu f,\al_{wsw^{-1}}\rangle}\to 0
%\qquad (\forall s\in S, w\in W))
%$$
%and consequently $b_s^{(\mu f)}(w)\to 1$. Thus the representation
%matrices of $\T^{(\mu f)}(s)$ $\ (\forall s\in S)$, and  thus also
%of $\T^{(\mu f)}(w)$ $\ (\forall w\in W)$ tend to those of the regular %representation.
%The character of $\T^f$ is thus the character of the %regular representation.

%\qed

%\begin{rem}\label{t.2}
%The $W$-genericity of $f$ implies that $\T^f$ can be defined on all of %$W$,
%although possibly $\C^f_{w_0}\ne W$ for some (or all) $w_0\in W$,
%since some $\langle f,al_t\rangle$ amy be $\pm 1$.
%\end{rem}

%\medskip

%Recall the notation $\C_A(w)$ from Definition~\ref{d.A_equiv}.

For a subset of reflections $A$ let the (left) {\em $A$-descent
set} of an element $w\in W$ is defined by
$$
\D_A(w):=\{t\in A\,|\,\ell(tw)<\ell(w)\}.
$$

\begin{df}\label{d.CF}
%(The Cell $\C^f_w$)\\
Let $w\in W$, and let $f\in V^*$ be an arbitrary linear functional on
the root space $V$ of $W$.
\begin{itemize}
\item[(1)] Define
$$
A_f := \{t\in T\,|\,\langle f,\al_t\rangle \in\{1, -1\}\},
$$
and
$$
\C^f_{w}:=\{v\in W|\D_A(v)=\D_A(w)\}.
$$
%where the notation $\C_A(w):=\{v\in W|\D_A(v)=\D_A(w)\}$
%is as in Definition~\ref{d.A_equiv} and
%$$
%A_f := \{t\in T\,|\,\langle f,\al_t\rangle \in\{1, -1\}\}.
%$$
\item[(2)] If $f$ is $\C^f_w$-generic (as in Definition~\ref{d.cg})
then the corresponding AY representation of $W$ (as in Theorem~\ref{t.main11}),
with the
symmetric normalization $\db_t =\ub_t\,(\forall t\in T_{\C^f_w})$,
%row-stochastic normalization $\ua_t + \ub_t = \da_t + \db_t = 1\,(\forall t\in T_{\C^f_w})$,
will be denoted $\T^f_w$ (or just $\T^f$ in case there is no ambiguity).
\end{itemize}
\end{df}

%Note that if $q=1$ then, under
%%$\da_t = -\ua_t$ and $\ua_t^2 + \ub_t\db_t = 1$, so
%%that under this
%he symmetric normalization, the matrix representing each
%generator $\T_s$ (in the natural basis of $V_{\C}$) is {\em
%orthogonal}
%%(with determinant $-1$)
%as well as symmetric.

\begin{rem}\label{r.indep}
By~\cite[Theorem 11.1]{U-I}, the representation $\T^f_w$
is independent of the normalization (up to isomorphism).
\end{rem}

%\begin{rem}\label{t.2}
%The $W$-genericity of $f$ implies that $\rho^f$ can be defined on
%all of $W$, although possibly $\C^f_w\ne W$ for some (or all)
%$w\in W$, since some $\langle f,\al_t\rangle$ may be $\pm 1$.
%\end{rem}

\begin{df}\label{d.flat}
Let $W$ be a Coxeter group, and let $V$ be its root space.
A {\em basic (affine) hyperplane} in $V^*$ has the form
$$
H_{t,\varepsilon}:=\{f\in V^* \,|\, \langle
f,\al_t\rangle=\varepsilon\},
$$
for some $t\in T$ and $\varepsilon \in \{1,-1\}$.

A {\em basic flat} in $V^*$ is an intersection of basic hyperplanes.
It is {\em proper} if different from $\emptyset$ and $V^*$.

%A vector $f$ in a basic flat $H$ is $H$-generic if
%$\langle f,\al_t\rangle\ne 0,\pm 1$ for all $t\in T$ other than those defining the flat $H$.
For a basic flat $L$, let
$$
A = A_L := \{\,t\in T \,|\, L\subseteq H_{t,\varepsilon}
\hbox{\rm\ for some\ } \varepsilon \in \{1,-1\}\,\}.
$$
Then $\{W_A^D \,|\, D\subseteq A\}$, where $W_A^D:=\{ w\in
W|\D_A(w)=D\}$,
%(see Section~\ref{s.prelim} for the definition of $W_A^D$)
is a partition of $W$ into convex
subsets, called the {\em $L$-partition} of $W$.
\end{df}

%\begin{fac}
%A basic flat $H$ defines a partition of $W$ into a disjoint union
%of convex subsets $\{\C^f_w\ |\ w\in W\}$, where $f$ is
%$H$-generic. The partition is independent of the choice of (the
%$H$-generic vector) $f$, and will be called the {\it
%$H$-partition} of $W$.
%\end{fac}

Note that, for the two ``improper'' flats:
\begin{eqnarray*}
L = \emptyset &\then& A_L = T\\
L = V^*       &\then& A_L = \emptyset
\end{eqnarray*}


\begin{thm}\label{t.5}
Let $W$ be a simply laced Coxeter group. Let $L$ be a basic %proper
flat in $V^*$, and fix a nonempty finite convex set $\C$ in the
$L$-partition of $W$. Then, for any two elements $v,v'\in\C$ and
any two $\C$-generic vectors $f,f'\in L$,
$\C^f_v = \C^{f'}_{v'} = \C$ and
the representations $\T^f_v$ and $\T^{f'}_{v'}$ are isomorphic.
\end{thm}

\noindent{\bf Proof.}
First of all,
$$
f\in L \iff \langle f, \al_t \rangle = \varepsilon_t\quad(\forall t\in A_L)
       \iff A_L \subseteq A_f
$$
and therefore, for any $\C$ in the $L$-partition of $W$ and any $v\in\C$,
$$
\C^f_v \subseteq \C.
$$
If $f$ is also $\C$-generic then $\langle f, \al_t \rangle \ne \pm1$
for all $t\in T_{\C}$, so that $\C^f_v = \C$.

Now choose $f_0\in L$, and let $\{f_1,\dots,f_k\}$ be a basis for
the linear subspace $L-f_0$ of $V^*$. Each $f\in L$ has a unique expression as
$$
f=f_0+r_1 f_1+\dots+r_k f_k,
$$
where $r_1,\ldots,r_k\in \bbr$. For any $t\in T_{\C} \cup T_{\partial\C}$,
$\langle f,\al_t\rangle$ is a linear combination of $1,r_1,\ldots,r_k$,
and is nonzero if $f$ is $\C$-generic.
For $v\in\C$, use the represetation $\T^f_v$ with the row-stochastic 
normalization $\ua_t + \ub_t = \da_t + \db_t = 1\,(\forall t\in T_{\C^f_v})$;
see Remark~\ref{r.indep}.


Thus, for any $v\in\C$ and $\C$-generic $f\in L$, each entry of the matrix
$\T^f_v(s)$ ($\forall s\in S$) is a rational function of $r_1,\dots,r_k$;
and the same therefore holds for each entry of $\T^f_v(w)$ ($\forall w\in W$)
and for the character values $\tr(\T^f_v(w))$. Note that these
rational functions (unlike the actual values of $r_1,\ldots,r_k$)
do not depend on the choice of $v$ and $f$, even though
the set $L^{\rm gen}$ of all $\C$-generic $f\in L$ may be disconnected
(see example below). By discreteness of the character values and
continuity of the rational function, each character value is
constant in each connected component of $L^{\rm gen}$,
and at the same time represented by one rational function
throughout $L^{\rm gen}$. It is therefore the same constant for all
$f\in L^{\rm gen}$ (and $v\in\C$), as claimed.
\qed

\begin{exa}
Take $W=S_3=\langle s_1,s_2\rangle$ (type $A_2$) and the basic
flat $L = \{f\in V^*\ |\ \langle f,\al_{s_1s_2s_1}\rangle=-1\}$.
Then $A = \{s_1s_2s_1\}$, and we may choose $\C =\{id,s_1,s_2\}$.
In that case, $T_{\C} = \{s_1,s_2\}$ and
$T_{\partial\C} = \{s_1s_2s_1\} = A$.
$L$ is an affine line in $V^* \cong \bbr^2$, and the $\C$-generic points
in $L$ form five disjoint open intervals (three of them bounded). For any
$\C$-generic vector $f\in L$ and any $v\in\C$, $\T^f_v$ is the 3-dimensional
representation isomorphic to the direct sum of the sign representation and
the unique irreducible 2-dimensional representation of $S_3$.
\end{exa}

An important special case is $L = V^*$ ($\C = W$).

\begin{thm}\label{t.1}
Let $W$ be a finite simply laced Coxeter group, and let $f\in V^*$
be $W$-generic (i.e.,
$\langle f,\al_t\rangle \not\in\{0,1,-1\}, \forall t\in T$).
Then, for any $v\in W$, the representation $\rho^f_v$ on $V_W$
is isomorphic to the regular representation of $W$.
\end{thm}

\noindent{\bf Proof.}
Fix $v\in W$ (and ignore it in the notation).
For all but finitely many values of $\mu\in \bbr$, the
linear functional $\mu f\in V^*$ is also $W$-generic.
The representations $\rho^{\mu f}$ and $\rho^f$ are isomorphic,
by Theorem~\ref{t.5}. On the other hand, if $|\mu| \to \infty$ then
$$
a_s^{(\mu f)}(w) = {\pm1\over \langle \mu f,\al_{wsw^{-1}}\rangle}\to 0
\qquad (\forall s\in S, w\in W)
$$
and consequently $b_s^{(\mu f)}(w)\to 1$. The representation
matrices of $\rho^{(\mu f)}(s)$ $(\forall s\in S)$, and thus
also those of $\rho^{(\mu f)}(w)$ $(\forall w\in W)$, tend to those of
the regular representation. The character of $\rho^f$ is thus the
character of the regular representation.
\qed

\medskip

Theorem~\ref{t.5} may be reformulated as follows.

\begin{thm}\label{t.7}
Let $(\T,\C)$ be a minimal AY pair for a simply laced Coxeter group $W$,
where $\C$ is finite.
%Let $f$ be a $\C$ generic vector.
Then the behavior of $\T$ at the boundary of $\C$
(i.e., the values $a_{s}(w)$ for $w\in \C, s\in S, ws\not\in\C$)
determines $\T$ up to isomorphism.
%, where $\T^f$ is the associated AY representation defined in~\ref{d.CF}.
%Thm 1:
%Let $\C$ be a finite convex set in a simply laced Coxeter group
%$W$, and let $f$ be a $\C$-generic vector. The values of $f$ at the
%boundary $T_{\partial \C}$ determine the representation $\T^f$ on $V_\C$.
\end{thm}

%\noindent{\bf Proof.} Combine Theorem~\ref{t.main.c1} ???? with
%Theorem~\ref{t.5}.
%
%\qed


\section{Minimal Cells in $S_n$}\label{s.cells_Sn}

In this section we show that integer-valued $\C$-generic vectors for $W=S_n$
lead to standard Young tableaux (of skew shape).
%We also assume that $\C$ is a minimal AY cell containing the identity
%element of $W$.
%The analysis for
%general minimal AY cell and
%general $q$  is similar. 
Theorem~\ref{t.5} is then applied to give a
complete characterization of minimal AY cells in $S_n$. Finally,
it is shown that all irreducible representations of $S_n$ are
minimal AY.

%The treatment of general cells will be done in \cite{U-II}.

\subsection{Identity Cells and Skew Shapes}\label{s.IdCT}

In this subsection we study minimal AY cells $\C\subseteq S_n$. 
By~\cite[Observation 3.3]{U-I}, every minimal AY cell is
a translate of a minimal AY cell containing the identity element;
thus we may assume that $id\in\C$.

\medskip

For a vector $v=(v_1,\dots,v_n)\in \bbr^n$ denote
$$
\der v:=(v_2-v_1,\dots,v_n-v_{n-1})\in \bbr^{n-1}.
$$
For a (skew) standard Young tableau $Q$ denote $c(k):=j-i$, where $k$ is
the entry in row $i$ and column $j$ of $Q$.
Call $cont(Q):=(c(1),\dots,c(n))$ the {\em content vector} of $Q$, and
call $\der cont(Q)$ the {\em derived content vector} of $Q$.

Note that for $W=S_n$ we may identify the root space $V$ with a subspace
(hyperplane) of $\bbr^n$:
$$
V \cong \{(v_1,\ldots,v_n)\in\bbr^n\,|\,v_1+\ldots+v_n=0\}.
$$

\noindent
The positive root $\al_{ij}\in V$ corresponding to
the transposition $(i,j)\in S_n$ may be identified with
the vector $\varepsilon_i - \varepsilon_j$ ($1\le i < j\le n$),
where $\{\varepsilon_1,\ldots,\varepsilon_n\}$ is
the standard basis of $\bbr^n$.
%The coordinates of a vector
%$f\in V$ will always be taken with respect to the ordered basis
%$(\varepsilon_1-\varepsilon_2,\ldots,\varepsilon_{n-1}-\varepsilon_n)$
The dual space $V^*$ is then a {\em quotient} of $\bbr^n$:
$$
V^* \cong \bbr^n/\,\bbr e,
$$
where $e := (1,\ldots,1)\in \bbr^n$.
We shall abuse notation and represent a linear functional $f\in V^*$ by
any one of its representatives $f=(f_1,\ldots,f_n)\in \bbr^n$; the
natural pairing $\langle\cdot,\cdot\rangle : V^* \times V \to \bbr$ is
then given by $\langle f,\varepsilon_i-\varepsilon_j\rangle = f_i-f_j$.

%Recall the notation $\C^f_{id}$ from Section~\ref{s.des_rep}.


\medskip

Recall the notations $\C^f_w$ and $\T^f_w$ from Definition~\ref{d.CF}.

%\begin{df}\label{d.CF2}
%(The Cell $\C^f_w$)\\
%Let $w\in W$, and let $f$ be an arbitrary vector in the root space $V$ of $W$.
%Let
%$$
%A = A_f := \{t\in T\,|\,\langle f,\al_t\rangle \in\{1, -1\}\}.
%$$
%\begin{itemize}
%\item[(1)]
%Define
%$$
%\C^f_w:=\C_A(w).
%$$
%\item[(2)]
%If $f$ is $\C^f_w$-generic then the corresponding AY
%representation of $W$, with the stochastic normalization
%(see Subsection~\ref{s.normal}),
%will be denoted $\T^f_w$.
%\end{itemize}
%\end{df}


\begin{thm}\label{t.tabl2}
Let  $f\in \bbr^n$ have integer coordinates. Then:
$(\T^f_{id},\C^f_{id})$ is a minimal AY pair for $W=S_n$ if and only if
there exists a standard skew Young tableau $Q$ of size $n$ such that
$$
\der f=\der cont(Q).
$$
\end{thm}

%\begin{rem}\label{r.remark1}
%\begin{itemize}
%\item[(1)]
%By Theorem~\ref{t.rep2f}, if $\C$ is a minimal AY cell,
%containing the identity, for $W = S_n$,
%then there exists a ($\C$-generic) vector $f\in V$ such that %$\C=\C^f_{id}$.
%Thus the starting point for Theorem~\ref{t.tabl2} can be
%a minimal AY cell $\C$ instead of a vector $f\in V$.
%\item[(2)]
%The assumption that $f$ is integral is not essential.
%This will be shown in \cite{U-II}.
%\end{itemize}
%\end{rem}

The proof of Theorem~\ref{t.tabl2} relies on the following lemmas.

%\medskip
%
%To prove Lemma \ref{t.rep-cell2}
%we need the following further lemma.

\begin{lem}\label{t.monotone}
%Under the assumptions of Theorem~\ref{t.tabl2},
Let $f\in \bbr^n$ and $1\le i < j\le n$.
If either $\langle f,\al_{ij}\rangle = \pm 1$,
or $f$ is $\C^f_{id}$-generic and $\langle f,\al_{ij}\rangle = 0$,
then $w^{-1}(i)<w^{-1}(j)$ for all $w\in \C^f_{id}$.
\end{lem}

\noindent{\bf Proof.}
The claim clearly holds for $w=id$. It thus suffices to show that
if $w,ws\in \C^f_{id}$ ($s\in S$) then $w^{-1}(j)-w^{-1}(i)$ and
$(ws)^{-1}(j)-(ws)^{-1}(i)$ have the same sign.

Since $s$ is an adjacent transposition, say $s=(t,t+1)$ ($1\le t\le n-1$),
the two signs differ if and only if $\{w^{-1}(i),w^{-1}(j)\}=\{t,t+1\}$.
This implies that $(i,j)=wsw^{-1}\in T_{\C^f_{id}}$.
Thus $\langle f,\al_{ij}\rangle \ne\pm 1$ and, if $f$ is $\C^f_{id}$-generic,
also $\langle f,\al_{ij}\rangle \ne 0$. This contradicts the assumption.
\qed

\begin{lem}\label{t.rep-cell2}
Let $f\in \bbr^n$ be an arbitrary vector.
Then $f$ is $\C^f_{id}$-generic if and only if, for all $1\le i < j\le n$:
\begin{equation}\label{e.R1}
\langle f, \al_{ij}\rangle=0\ \then\
\exists\ r_1,r_2\in[i+1,j-1]\ \hbox{\rm s.t.}\
\langle f, \al_{ir_1}\rangle=-\langle f, \al_{ir_2}\rangle=1.
\end{equation}
\end{lem}

\noindent{\bf Proof.}
Let $\C := \C^f_{id}$.

\noindent{\bf A - (necessity).}
%Assume that $\C$ is a minimal AY cell containing the identity.
%By Theorem~\ref{t.rep2f}, there exists a $\C$-generic vector $f\in V$
%such that $\C=\C^f_{id}$.
%
%By Definition~\ref{d.cg} (of $\C$-genericity)
%\begin{itemize}
%\item[{\bf (i)}]
%For all $t\in T_{\C}$,
%$$
%\langle f,\al_t\rangle \ne 0.
%$$
%\item[{\bf (iii)}]
%If $w\in \C$, $s,t\in S$, $m(s,t)=3$ and $ws, wt\not\in \C$ then
%$$
%\langle f,\al_{wsw^{-1}}\rangle=
%\langle f,\al_{wtw^{-1}}\rangle.
%$$
%\end{itemize}
Note that, since $f$ is $\C$-generic,
\begin{equation}\label{e.9}
\langle f, \alpha_{ij}\rangle=0 \then (i,j)\not\in T_\C\cup T_{\partial \C}.
\end{equation}
%
Consider the set
$$
Z:=\{(i,j)\ |\ 1\le i<j\le n, \langle f,\al_{ij}\rangle =0\}.
$$
We shall prove that
$$
(i,j)\in Z \then \exists\,r_1,r_2\in[i+1,j-1] \hbox{ such that }
\langle f,\al_{ir_1}\rangle=\langle f,\al_{r_2 j}\rangle=1.
$$
The proof will proceed by induction on $j-i$,
the height of the root $\al_{ij}$.%, as in Section~\ref{s.prelim}.

\smallskip

%{\bf $j-i=1$ :}
Assume first that $j-i = 1$. Then $(i,j)=(i,i+1)\in S$.
Since $id\in\C$, $S \subseteq T_{\C} \cup T_{\partial\C}$.
%By condition (i) of Definition \ref{d.cg} of $\C$-genericity,
%$\langle f,\al_t\rangle \ne 0$ for all $t\in T_{\C}$.
%Thus $(i,i+1)\not\in T_\C$, and therefore $(i,i+1)\in T_{\partial\C}$.
%By condition (ii) of Definition \ref{d.cg}
%$\langle f,\al_{ij}\rangle = \pm1$,
%contradicting our assumption $\langle f,\al_t\rangle = 0$.
This contradicts (\ref{e.9}) above.

%\smallskip

%{\bf Induction step :}

For the induction step, assume
that $(i,j)\in Z$ with $j-i>1$ and that the claim is true for all
reflections in $Z$ with smaller heights.
%Again, by condition (i) of Definition~\ref{d.cg}, $(i,i+1)\not\in T_\C$.
Choose $w\in \C$ such that $d_w:=|w^{-1}(j)-w^{-1}(i)|$ is minimal.
Note that, by Lemma~\ref{t.monotone}, actually $d_w=w^{-1}(j)-w^{-1}(i)>0$.

If $d_w=1$ then there exists $1\le t\le n-1$ such that $w(t)=i$ and $w(t+1)=j$,
so that $(i,j) = w(t,t+1)w^{-1} \in T_{\C} \cup T_{\partial\C}$,
%; but then the action of $(t,t+1)$ on $C_w$
%in our representation is not defined (since
%$\ua_{w(t,t+1)w^{-1}}={1\over \langle f,\al_{ij}\rangle}={1\over 0}$).
which is a contradiction to (\ref{e.9}).

Thus $d_w\ge 2$.

Define $1\le r_1,r_2\le n$ by $w^{-1}(r_1)=w^{-1}(i)+1$ and $w^{-1}(r_2)=
w^{-1}(j)-1$. By minimality of $d_w$, $(i,r_1)\in T_{\partial\C}$ so that
$\langle f,\al_{i r_1}\rangle = \pm1$; similarly
$\langle f,\al_{r_2 j}\rangle = \pm1$.
%Since $\langle f,\al_{ij}\rangle = 0$, we have
%$\langle f,\al_{i r_2}\rangle = -\langle f,\al_{r_2 j}\rangle = \pm1$ and
%$\langle f,\al_{r_1 j}\rangle = -\langle f,\al_{i r_1}\rangle = \pm1$.
%By Lemma~\ref{t.monotone}, $w^{-1}(i) < w^{-1}(r_1) < w^{-1}(j)$
%implies $i<r_1<j$ and similarly for $r_2$.
Now $\langle f, \al_{i j}\rangle = 0$ and $\langle f, \al_{i r_1}\rangle = \pm1$
imply
\begin{eqnarray*}
\langle f, \al_{r_1 j}\rangle &=&
\langle f, \al_{r_1 i}\rangle + \langle f, \al_{i j}\rangle = \pm1\quad
\hbox{\rm (if $r_1 < i$)};\cr
\langle f, \al_{r_1 j}\rangle &=&
\langle f, \al_{i j}\rangle - \langle f, \al_{i r_1}\rangle = \pm1\quad
\hbox{\rm (if $i < r_1 < j$)};\cr
\langle f, \al_{j r_1}\rangle &=&
\langle f, \al_{i r_1}\rangle - \langle f, \al_{i j}\rangle = \pm1\quad
\hbox{\rm (if $j < r_1$)}.
\end{eqnarray*}
Since $w^{-1}(i) < w^{-1}(r_1) < w^{-1}(j)$ we conclude, by Lemma~\ref{t.monotone},
that $i < r_1 < j$. Similarly  $i < r_2 < j$.


If $\langle f,\al_{i r_1}\rangle = -\langle f,\al_{i r_2} \rangle = 1$ or
$\langle f,\al_{i r_1}\rangle = -\langle f,\al_{i r_2} \rangle = -1$
we are done.
We can thus assume, with no loss of generality, that
$\langle f,\al_{i r_1}\rangle = \langle f,\al_{i r_2} \rangle = \varepsilon = \pm1$
and $r_1\le r_2$.

If $r_1=r_2$ then $w^{-1}(j)-w^{-1}(i)=2$. Denote $t := w^{-1}(i)$.
Then
$\langle f,\al_{w (t,t+1)w^{-1}}\rangle = \langle f,\al_{ir_1}\rangle = \varepsilon$
and $\langle f,\al_{w (t+1,t+2)w^{-1}}\rangle = \langle f,\al_{r_1 j}\rangle = -\varepsilon$.
This contradicts condition (iii) of $\C$-genericity (Definition~\ref{d.cg}).
Therefore $r_1<r_2$.
Thus
$$
\langle f,\al_{r_1 r_2}\rangle =
\langle f,\al_{i r_2}\rangle - \langle f,\al_{i r_1}\rangle = 0.
$$
Since $r_2-r_1<j-i$, by the induction hypothesis there exists
$r_1<r_3<r_2$ such that $\langle f,\al_{r_1 r_3}\rangle=-\varepsilon$.
Thus $\langle f,\al_{i r_3} \rangle=0$
(and $\langle f,\al_{r_3 j} \rangle=0$).
Again, by the induction hypothesis, there exist
$i<r_4,r_5<r_3$ such that
$\langle f,\al_{i r_4} \rangle=
\langle f,\al_{r_5 r_3} \rangle=1$.
Noting that
$\langle f,\al_{r_5 r_3} \rangle=
\langle f,\al_{r_5 j} \rangle$ completes the proof that
condition~(\ref{e.R1}) is necessary.

\medskip

\noindent{\bf B - (sufficiency).}

Assume now that $f\in \bbr^n$ satisfies condition~(\ref{e.R1}).
%In order to prove that $\C=\C^f_{id}$ is a minimal AY cell
%it suffices (by Theorem~\ref{t.f2rep}) to show that $f$ is $\C$-generic.
Condition (ii) of Definition~\ref{d.cg} holds by the definition of $\C^f_{id}$.
Assume that $\langle f,\al_{i j} \rangle=0$.
By condition~({\ref{e.R1}) and Lemma~\ref{t.monotone},
there exist
$i<r_1<r_2<j$ such that $w^{-1}(i)<w^{-1}(r_1)<w^{-1}(r_2)<w^{-1}(j)$
for all $w\in \C$.
Thus $w^{-1}(j)-w^{-1}(i)>2$, and this implies conditions (i) and (iii)
of $\C$-genericity as follows :

For condition (i), if $w,ws\in \C$, $s=(t,t+1)\in S$
and $\langle f,\al_{wsw^{-1}} \rangle=0$ then, denoting $i:=w(t)$ and $j:=w(t+1)$,
we get $i<j$ and $\langle f,\al_{i j} \rangle=0$, so that
$w^{-1}(j)-w^{-1}(i)=1$ contradicting our conclusion above.

For condition (iii), if $w\in \C$, $ws,wt\not\in\C$,
$s=(k,k+1)$ and $t=(k+1,k+2)$
%(the general case of $m(s,t)=3$ in $S_n$)
then denote $i:=w(k)$, $r:=w(k+1)$, and $j:=w(k+2)$. Then $i<r<j$ and
$\langle f,\al_{wsw^{-1}} \rangle=\pm 1$, $\langle
f,\al_{wtw^{-1}} \rangle=\pm 1$. If $\langle f,\al_{wsw^{-1}}
\rangle \ne \langle f,\al_{wtw^{-1}} \rangle$ then $\langle
f,\al_{wsw^{-1}} \rangle + \langle f,\al_{wtw^{-1}} \rangle =0$,
that is $\langle f,\al_{ir} \rangle + \langle f,\al_{rj} \rangle
=0$ or equivalently $\langle f,\al_{ij} \rangle=0$, and
$w^{-1}(j)-w^{-1}(i) = 2$ contradicts our conclusion above. \qed

\medskip

\begin{lem}\label{t.rep-cell4}
A vector  $c=(c_1,\ldots,c_n)\in \bbz^n$ is a content
vector for some skew standard Young tableau if and only if for all $1\le i<j\le n$
\begin{equation}\label{e.cont}
c_i = c_j \then \exists\,r_1, r_2\in[i+1,j-1] \hbox{ such that }
c_{r_1} = c_i+1 \hbox{ and } c_{r_2} = c_i-1.
\end{equation}
\end{lem}

\noindent{\bf Proof.}
It is clear that if $(c_1,\ldots,c_n)$ is the content vector of
a skew standard Young tableau then it satisfies condition~(\ref{e.cont}).

Conversely, let $(c_1,\ldots,c_n)\in \bbz^n$ be such that (\ref{e.cont}) holds.
We will show, by induction on $n$, that there exists
a skew standard Young tableau $Q$ such that $\cont(Q) = (c_1,\ldots,c_n)$.
The existence of $Q$ is clear for $n\le 2$.
By the induction hypothesis, there exists a skew standard Young tableau
$Q'$ such that $\cont(Q') = (c_1,\ldots,c_{n-1})$.
Let $C := \{c_\ell\,|\,\ell\in[n-1]\}$.

If $c_n\in C$, let
$$
k := \max \{\ell\in [n-1]: \; c_{\ell}=c_{n}\}.
$$
By our hypothesis there exist $r_1,r_2 \in [k+1,n-1]$ such that
$c_{r_1}=c_k + 1$ and $c_{r_2}=c_k - 1$.
If $k$ is in box $(i,j)$ of $Q'$ then
box $(i+1,j+1)$ must be empty (since $k$ is maximal). Therefore
$r_1$ must be in box $(i,j+1)$ and $r_2$ must be in box $(i+1,j)$.
Placing $n$ in box $(i+1,j+1)$ yields a skew standard Young tableau $Q$
such that $\cont(Q) = (c_1,\ldots,c_n)$, as desired.

If $c_n\not\in C$ then $Q'$ is the disjoint union of two (possibly empty)
tableaux, $Q'_+$ and $Q'_-$, consisting of the boxes of $Q'$ with contents
strictly larger (respectively, smaller) than $c_n$.
Let $(i_+,j_+)$ be the (unique) box with the smallest (closest to $c_n$)
content in $Q'_+$, and define similarly $(i_-,j_-)$ for $Q'_-$.
All of $Q'_+$ is (weakly) northeast of $(i_+,j_+)$,
all of $Q'_-$ is (weakly) southwest of $(i_-,j_-)$, and
$(i_+,j_+)$ is (strictly) northeast of $(i_-,j_-)$.
If the difference in contents between $(i_+,j_+)$ and $(i_-,j_-)$ is $2$
(the smallest possible) then these boxes have a common corner, and we can
place $n$ in box $(i_-,j_- +1) = (i_+ +1, j_+)$ to form $Q$.
If the difference is larger than we can shift all the boxes of $Q'_+$
diagonally (preserving their contents) until $i_+ = i_- -1$ (and thus
$j_+ > j_- +1$). Now we can place $n$ in box $(i_-,j_- +1)$ to form $Q$.
The discussion is even simpler if either one of $Q'_+$ and $Q'_-$ is empty.
\qed

\bigskip

\noindent{\bf Proof of Theorem~\ref{t.tabl2}.} Combine
Lemma~\ref{t.rep-cell2} with Lemma~\ref{t.rep-cell4}. \qed

\subsection{Cell Elements and Standard Tableaux}\label{s.CET}

By Theorem~\ref{t.tabl2}, a minimal AY cell (containing the identity) in $S_n$
is defined by a linear functional represented by a vector $f\in \bbz^n$
such that $\der f=\der cont(Q)$ for some standard skew Young tableau $Q$.
We will show that there is a bijection between the elements of $\C^f_{id}$
and the standard Young tableaux of the same shape as $Q$.

%\smallskip

%Let $Q$ be a standard skew Young tableau, and let $f\in \bbz^n$
%be any vector with $\der f = \der cont(Q)$.
%View $f$ as (a representative of) a linear functional in $V^*$,
%and consider the corresponding cell $\C^f_{id}$.

\begin{thm}\label{t.cell}
Let $Q$ be a standard skew Young tableau, and let $f\in \bbz^n$
be any vector satisfying $\der f = \der cont(Q)$.
Then, for any $\pi\in S_n$,
$$
\pi\in \C^f_{id} \iff \hbox{\ the tableau }Q^{\pi\inv}\hbox{\ is standard},
$$
where $Q^{\pi\inv}$ is the tableau obtained from $Q$
by replacing each entry $i$ by $\pi\inv(i)$ ($1\le i\le n$).
\end{thm}

\begin{cor}\label{t.card}
The size of $\C^f_{id}$ is equal to the number of standard Young tableaux
of the same shape as $Q$.
\end{cor}

%Note Remark~\ref{r.remark1}(2) ???.

%Theorem~\ref{t.cell} follows from the following observation.
In order to prove Theorem~\ref{t.cell}, we first make the following observation.

\begin{obs}\label{t.adjacent}
For a standard skew Young tableau $Q$ and any $1\le i< n$, exactly one of
the following 3 cases holds:
\begin{itemize}
\item[(1)]
$i+1$ is adjacent to $i$ in the same row of $Q$, and then
$$
[\der cont(Q)]_i = 1.
$$
\item[(2)]
$i+1$ is adjacent to $i$ in the same column of $Q$, and then
$$
[\der cont(Q)]_i = -1.
$$
\item[(3)]
$i+1$ and $i$ are not in the same row or column of $Q$, and then
$$
|[\der cont(Q)]_i| \ge 2.
$$
\end{itemize}
Note that $i+1$ and $i$ cannot be in the same diagonal of $Q$:
$[\der cont(Q)]_i \ne 0$.
\end{obs}

\begin{lem}\label{t.si}
Assume that $\pi\in \C^f_{id}$ and $Q^{\pi\inv}$ is standard. Then, for any
$1\le i< n$:
$$
\pi s_i\in \C^f_{id} \iff Q^{(\pi s_i)\inv} \hbox{\ is standard}.
$$
\end{lem}

\noindent{\bf Proof.}
Consider $\pi\in \C^f_{id}$ and $1\le i< n$. Then:
\begin{eqnarray}\label{e.78}
\frac{1}{\ua_{\pi s_i \pi^{-1}}} &=&
\langle f,\alpha_{\pi s_i \pi^{-1}} \rangle =
\langle f,\alpha_{(\pi(i),\pi(i+1))} \rangle =\cr
&=& \pm\,(f_{\pi(i+1)} - f_{\pi(i)}) =
\pm\,[\der cont(Q^{\pi\inv})]_i,
\end{eqnarray}
where ``$\pm$'' is the sign of $\pi(i+1) - \pi(i)$.
Thus
$$
\ua_{\pi s_i \pi^{-1}} \ne \pm 1 \iff
[\der cont(Q^{\pi\inv})]_i \ne \pm 1.
$$
On the other hand, since $\pi\in\C^f_{id}$,
$$
\ua_{\pi s_i\pi^{-1}}\ne \pm 1 \iff \pi s_i\in \C^f_{id}.
$$
By Observation~\ref{t.adjacent}, this means that
$\pi s_i\in \C^f_{id}$ if and only if $i$ and $i+1$ are not in
the same row or column of $Q^{\pi\inv}$.
Thus, for $\pi\in \C^f_{id}$ with $Q^{\pi\inv}$ standard:
$$
\pi s_i\in \C^f_{id} \iff
(Q^{\pi\inv})^{s_i} = Q^{s_i \pi\inv} = Q^{(\pi s_i)\inv}
\hbox{\ is standard}.
$$
\qed

\medskip

\noindent{\bf Proof of Theorem~\ref{t.cell}.}
By Lemma~\ref{t.si}, it suffices to show that any $\pi\in\C^f_{id}$
may be reduced to the identity permutation by
a sequence of multiplications (on the right) by adjacent transpositions
$s_i\in S$ such that all the intermediate permutations are also in $\C^f_{id}$;
and that a similar property holds for any $\pi\in S_n$ such that
$Q^{\pi\inv}$ is standard. In other words, we need to show that
$\C^f_{id}$ and $\{\pi\in S_n\,|\,Q^{\pi\inv}\hbox{\ is standard}\}$ are
{\em connected} subsets in the right Cayley graph of $S_n$ with respect to
the Coxeter generators.

For $\C^f_{id}$ this follows from the {\em convexity} of minimal
AY cells %~\cite[Corollary 4.4]{U-I}.
(Proposition~\ref{t.main.convex}).

For $\{\pi\in S_n\,|\,Q^{\pi\inv}\hbox{\ is standard}\}$ we give the
outline of an argument.
An {\em inversion} in a standard skew Young tableau $Q$ is a pair $(i,j)$
such that $1\le i < j \le n$ and $i$ appears in $Q$ strictly south of $j$.
The {\em inversion number} $\inver(Q)$ is the number of inversions in $Q$
(see~\cite{St_sign}).
%For any skew shape there is a unique standard tableau $T_0$ of that shape
%for which $\des(T_0)$ is minimal; this is the {\em ro
If $i$ appears in $Q$ strictly south of $i+1$ Then $Q^{s_i}$ is also
a standard tableau, with $\inver(Q^{s_i}) = \inver(Q)-1$. Thus
every standard tableau $Q$ leads, by a sequence of applications of
generators $s_i\in S$, to the unique standard tableau of the same skew shape
for which $i$ is always weakly north of $i+1$ ($1\le i < n$), i.e.,
the corresponding {\em row tableau} (see Definition~\ref{d.row} below).
Thus any two standard skew tableaux of the same shape are connected by
such a sequence, and this is the connectivity result that we need.
\qed

\bigskip

%The following is a full characterization of minimal AY cells in $S_n$.
%
%\begin{thm}\label{t.symm}
%Let $\C$ be a nonempty subset of the symmetric group $S_n$
%and let $\sigma\in \C$. Then $\C$ is a minimal AY cell
%if and only if there exists a standard Young tableau $Q$ such that
%$$
%\sigma^{-1} \C= \{\pi\in S_n|\ Q^{\pi\inv} \hbox{ is standard }\}.
%$$
%\end{thm}


%The detailed proof will be given in~\cite{U-II}.
%
%\bigskip

In contrast to Kazhdan-Lusztig theory,
where the bijection between cell elements and tableaux
is given by the RSK algorithm,
the above bijection between elements of the cell $\C^f_{id}$ and tableaux
is extremely simple.

%\noindent{\bf Proof of Theorem~\ref{t.cell}.}
%We shall first prove that
%$$
%\pi\in \C^f_{id} \then Q^{\pi\inv}\hbox{\ is standard}
%$$
%by induction on the length $\ell(\pi)$.
%
%If $\ell(\pi) = 0$ then $\pi = id$, and $Q^{\pi\inv} = Q$ is standard.
%Assuming $\ell(\pi) > 0$, since $id, \pi\in \C^f_{id}$ it follows
%(by convexity of the cell) that there exists $1\le i< n$ such that
%$\pi s_i < \pi$ and $\pi s_i\in \C^f_{id}$. By the induction hypothesis,
%$Q^{(\pi s_i)\inv}$ is standard, and by Lemma~\ref{t.si}
%(interchanging $\pi$ and $\pi s_i$) $Q^{\pi\inv}$ is also standard.
%
%In the other direction, let $\pi\in S_n$ such that $Q^{\pi\inv}$ is standard.
%It is well known that there exists a sequence of permutations
%$id = \pi_0, \pi_1, \ldots, \pi_t = \pi$ such that
%$\pi_j^{-1} \pi_{j+1}$ is a simple reflection and $Q^{\pi_j\inv}$ is standard
%($0\le j\le t$).
%By Lemma \ref{t.si}, since $\pi_0=id\in \C^f_{id}$,
%it follows that $\pi_j\in \C^f_{id}$ for $0\le j\le t$,
%and in particular $\pi\in \C^f_{id}$.
%
%\qed

%\begin{thm}\label{t.bijection}
%The map $\ \varphi\circ c_f\ $ is a bijection
%from permutations in $\C^f_{id}$ to standard Young tableaux of a fixed shape.
%\end{thm}

%\subsection{Minimal $AY$ Cells}\label{s.cells_Sn}

\bigskip

A complete characterization of minimal AY cells in $S_n$ now follows.

\begin{thm}\label{t.symm}
Let $\C$ be a nonempty subset of the symmetric group $S_n$, and
let $\sigma\in \C$. Then $\C$ is a minimal AY cell if and only if
there exists a standard skew Young tableau $Q$ such that
$$
\sigma^{-1}\C=\{\pi\in S_n\,|\,Q^{\pi\inv} \hbox{ is standard}\},
$$
where $Q^{\pi\inv}$ is the tableau obtained from $Q$ by replacing each
entry $i$ by $\pi\inv(i)$.
\end{thm}

\noindent{\bf Proof.}
%of Theorem~\ref{t.symm}.}
%Theorem~\ref{t.symm} is proved by
Given $Q$, define $f:=cont(Q)$ and use Theorem~\ref{t.cell} to conclude that
$$
\{\pi\in S_n\,|\,Q^{\pi\inv} \hbox{ is standard}\} = \C^f_{id}
$$
is a minimal AY cell containing the identity element. Thus, if $\sigma\in\C$
and $\sigma\inv\C = \C^f_{id}$ then $\C$ is a minimal AY cell.

In the other direction, if $\C$ is a nonempty minimal AY cell and $\sigma\in\C$
then $\sigma\inv\C = \C^f_{id}$ for some $\C$-generic vector $f\in V^*$.
If $L$ is the basic flat corresponding to $\C$ (see Definition~\ref{d.flat} above)
then actually $f\in L$.
Now observe that, due to the special form of the roots of $S_n$,
any (nonempty) basic flat contains a vector with integral coordinates.
By Theorem~\ref{t.5} we may thus assume that $f\in\bbz^n$, and thus
Theorem~\ref{t.tabl2} gives us the $Q$ we are looking for.
\qed

\subsection{Young Orthogonal Form}\label{s.YOF}

This subsection contains explicit representation matrices,
which are deduced from the previous analysis.
In particular, it is shown that all irreducible $S_n$-representations
may be obtained from our construction (Theorem \ref{t.irr} below).

Let ${\C}\subseteq S_n$ be a convex set and let
$f$ be an integer $\C$-generic vector.
Consider the $S_n$-representation $\T^f_{id}$.
By Corollary \ref{t.card},
a basis $\cal{B}$ of the representation space of $\T^f_{id}$
may be indexed by the set of standard Young tableaux of a certain shape.

%\begin{cor}\label{t.yof2}{(\bf Young Orthogonal Form for Skew Shapes)}\\
%Let $P$ be a skew standard Young tableau of shape $\la/\mu$ ($\mu$ possibly empty)
%and let $f=\der\cont(P)$. Then  the action of the generators
%in $\T^f_{id}$ on a basis indexed by tableaux is given by
%$$
%\T_{s_i}(Q)=
%\cases
%{{1\over\hk(i)}Q + \sqrt{1-{1\over\hk(i)^2}}s_iQ, &if $\ell(w)<\ell(ws)$;\cr
%-{1\over\hk(i)}Q + \sqrt{1-{1\over\hk(i)^2}}s_iQ, &if $\ell(w)>\ell(ws)$,\cr}
%$$
%where $\hk(i):=c(i+1)-c(i)$ in $Q$, and $s_iQ$ is the tableau obtained
%from $Q$ by interchanging $i$ and $i+1$.
%\end{cor}
\begin{cor}\label{t.yof2}{\bf (Young Orthogonal Form for Skew Shapes)}\\
Let $Q_0$ be a standard Young tableau of skew shape $\la/\mu$ 
($\mu$ possibly empty), 
let $f\in \bbz^n$ satisfy $\der f = \der cont(Q_0)$,
and let $\T:=\T^f_{id}$.
Then the $\T$-action of the generators of $S_n$ on the basis $\cal{B}$
is given by
$$
\T_{s_i}(v_Q)=
{1\over\hk(i)}v_Q + \sqrt{1-{1\over\hk(i)^2}}v_{Q^{s_i}}
\qquad(1\le i < n,\, v_Q\in\cal{B}),
$$
where $\hk(i):=c(i+1)-c(i)$ in $Q$, and $Q^{s_i}$ is the tableau obtained
from $Q$ by interchanging $i$ and $i+1$.
\end{cor}

\noindent{\bf Proof.} Combine Theorem~\ref{t.main12}
%~\ref{t.rep2f}
with Theorem~\ref{t.cell} and equation~(\ref{e.78}), noticing that,
by definition, $h(i)=\der cont(Q)_i$. \qed

\begin{thm}\label{t.irr}
Let $Q_0$ be a standard Young tableau of skew shape $\la/\mu$ 
($\mu$ possibly empty).
If $f\in \bbz^n$ satisfies $\der f = \der cont(Q_0)$ then
$$
\T^f_{id}\cong S^{\la/\mu},
$$
where $S^{\la/\mu}$ is the skew Specht module corresponding to $\la/\mu$.
\end{thm}

\noindent{\bf Proof.} For a skew shape $\la/\mu$ the
representation matrices of the generators in
Corollary~\ref{t.yof2} are identical to those given by the
classical Young orthogonal form (Theorem~\ref{t.yof-skew}). \qed

\begin{cor}\label{t.irr2}
The complete list of minimal AY representations of the symmetric
group $S_n$ is given (up to isomorphism) by the skew Specht
modules $S^{\lambda/\mu}$, where $\la/\mu$ is of order $n$
(and $\mu$ possibly empty).

In particular, every irreducible representation of the symmetric
group $S_n$ may be realized as a minimal abstract Young
representation.
\end{cor}

%\begin{rem}
%One concludes that the derived content vector of a standard Young
%tableau of shape $\lambda/\mu$ gives an irreducible representation
%if and only if $\mu$ is the empty partition.
%\end{rem}

%\medskip

%\begin{thm}\label{t.skew}
%Let $\la$ be a normal shape and $Q$ be a standard Young tableau
%of shape $\la$.
%If $f=\der\cont(Q)$
%then
%$$
%\T^f_{id}\cong S^{\la/\mu},
%$$
%where $S^{\la/\mu}$ is the $S_n$-representation corresponding to %$\la/\mu$.
%\end{thm}

%\noindent{\bf Proof.}
%Find a reference ?? or prove YOF for skew shapes and
%compare.

%\qed

%\bigskip


\section{The Irreducibles Representations of $B_n$ are AY}

We begin with the following lemma.

\begin{lem}\label{ind}
Let $(W,S)$ be a finite Coxeter system and let $J_1, J_2$ be
disjoint subsets of $S$. Let $({\cal K}_1, \rho_1)$ and $({\cal K}_2,\rho_2)$
be minimal AY pairs for $W_{J_1}$ and $W_{J_2}$, respectively,
and let $W^{J_1\cup J_2}$ be the set of representatives of minimal
length of the right cosets of the parabolic subgroup $W_{J_1\cup J_2}$ in $W$.
Then
$$
({\cal K}_1{\cal K}_2 W^{J_1\cup J_2},
(\rho_1\otimes\rho_2)\uparrow _{W_{J_1}\times W_{J_2}}^W)
$$
is a minimal AY pair for $W$.
\end{lem}

\noindent{\bf Proof.} By the definition of a minimal AY pair,
$({\cal K}_1 {\cal K}_2, \rho_1\otimes \rho_2)$ is a minimal AY
pair for $W_{J_1} W_{J_2}= W_{J_1\cup J_2}$. The lemma now follows
from Theorem~\ref{induction}.

\qed

Let $\lambda$ be a partition of $k$ ($1\le k\le n-1$),
$\mu$ a partition of $n-k$,
$P$ a standard Young tableau of shape $\lambda$ on the letters $1,\dots,k$,
and $Q$ a standard Young tableau of shape $\mu$ on the letters $k+1,\dots,n$.
Denote by $S_{[i,j]}$
the symmetric group on the letters $i, i+1, \dots, j$.

\begin{df}
A {\em shuffle} of a permutation $\pi\in S_{[1,k]}$ with
a permutation $\sigma\in S_{[k+1,n]}$ is a permutation $\tau\in S_n$
such that the letters $1,\ldots,k$ appear in $(\tau(1),\ldots,\tau(n))$
in the order $(\pi(1),\ldots,\pi(k))$ and the letters $k+1,\ldots,n$
appear in $(\tau(1),\ldots,\tau(n))$ in the order
$(\sigma(k+1),\ldots,\sigma(n))$.
\end{df}

\begin{cor}\label{t.ind-symm}
The set of all shuffles of permutations from
$$\{\pi\in S_{[1,k]}|\ P^{\pi\inv} \hbox{ is standard}\}$$
with permutations from
$$\{\sigma\in S_{[k+1,n]}|\ Q^{\sigma\inv} \hbox{ is standard}\}$$
is a minimal AY cell in $S_n$, which carries a minimal AY
representation isomorphic to the outer product
$(S^\lambda\otimes S^\mu)\uparrow_{S_k\times S_{n-k}}^{S_n}$.
\end{cor}

\noindent{\bf Proof.} Denote by $\Omega_{k,n}$ the set of all
shuffles of $(1,\ldots,k)$ with $(k+1,\ldots,n)$:
$\Omega_{k,n} = \{\tau\in S_n\,|\,\tau^{-1}(j) < \tau^{-1}(j+1), \forall j\ne k\}$.
It is well known
that $\Omega_{k,n}$ is the set of all representatives of minimal
length of right cosets of $S_{[1,k]}\times S_{[k+1,n]}$ in $S_n$.
The set considered in the corollary is the product
$$
\{\pi\in S_{[1,k]}\,|\,P^{\pi\inv} \hbox{ is standard}\}\cdot
\{\sigma\in S_{[k+1,n]}\,|\,Q^{\sigma\inv} \hbox{ is standard}\}\cdot
\Omega_{k,n}.
$$
The corollary now follows from Theorem~\ref{t.cell} and %Lemma~\ref{t.si} and
Theorem~\ref{t.irr} together with Lemma~\ref{ind}.

\qed

Denote the set of all shuffles considered in Corollary~\ref{t.ind-symm}
by ${\cal B}_{P,Q}$ and the associated AY representation by $\rho$.
The representation matrices of the Coxeter generators of $S_n$ on
$V_{{\cal B}_{P,Q}}$ are given by

\begin{cor}\label{t.yof-ind}
For all $1\le i< n$ and $\pi\in {\cal B}_{P,Q}$,
$$
\rho_{s_i} C_\pi=\cases{%
C_{\pi s_i}, &if either $\pi(i)\le k< \pi(i+1)$ \cr
             &or $\pi(i+1)\le k< \pi(i)$;\cr
\frac{1}{\hk(\pi,i)}C_\pi +
\sqrt{1-\frac{1}{\hk(\pi,i)^2}}C_{\pi s_i}, &otherwise,}
$$
where $\hk(\pi,i):=c(\pi(i+1))-c(\pi(i))$ in $P$ if both $\pi(i)$
and $\pi(i+1)$ are $\le k$, and in $Q$ if both are $>k$.
\end{cor}

\noindent{\bf Proof.}
Use Remark~\ref{induction1} with $W=S_n$ and
$J=\{s_1,\ldots,s_{n-1}\} \setminus \{s_k\}$.
Note that if $\pi=mr$, where $m\in S_{[1,k]}\times S_{[k+1,n]}$
and $r$ is a shuffle in $W^J = \Omega_{k,n}$, then
$rs_i\in \Omega_{k,n}$ if and only if
either $\pi^{-1}(i)\le k< \pi^{-1}(i+1)$
or $\pi^{-1}(i+1)\le k< \pi^{-1}(i)$.
The coefficients in the case $rs_i\not\in \Omega_{k,n}$
are determined, by Remark~\ref{induction1} together with
Theorem~\ref{t.tabl2} and Corollary~\ref{t.yof2}, by the content
vectors of $P$ and $Q$.

\qed

\medskip

We will show now that the subset ${\cal B}_{P,Q}\subseteq S_n$
is a minimal AY cell in $B_n$, when $S_n$ is naturally embedded in $B_n$ as
a maximal parabolic subgroup.
% In order to accomplish this goal we have to define the action of
% the exceptional Coxeter generator $s_0$.

\begin{pro}\label{B-AY-yof}
The subset ${\cal B}_{P,Q}\subseteq B_n$ is a minimal AY
representation of $B_n$, where the action of the simple
reflections $s_i$, $1\le i<n$, is determined as in
Corollary~\ref{t.yof-ind} and the action of $s_0$ is determined by
$$
\rho_{s_0} C_\pi=\cases{%
C_{\pi},  &if $\pi(1)\le k$;\cr
-C_{\pi}, &otherwise.}
$$
\end{pro}

\noindent{\bf Proof.}
By Corollaries~\ref{t.ind-symm} and~\ref{t.yof-ind} it suffices to verify
the relations involving $s_0$. Clearly, $\rho_{s_0}$ commutes with $\rho_{s_i}$
for all $i>1$ since $\pi s_i(1) = \pi(1)$ for all $i>1$. To verify the
relation $(\rho_{s_0}\rho_{s_1})^4=1$ we have to check four cases:
\begin{itemize}
\item[(1)]
If $\pi(1)$ and $\pi(2)$ are $\le k$ then both $C_\pi$
and $C_{\pi s_1}$ are invariant under $\rho_{s_0}$;
thus $(\rho_{s_0}\rho_{s_1})^2 C_\pi = \rho_{s_1}^2 C_\pi = C_\pi$.
\item[(2)]
If $\pi(1)$ and $\pi(2)$ are $> k$ then both $C_\pi$ and $C_{\pi s_1}$
are eigenvectors of $\rho_{s_0}$ with eigenvalue $-1$;
%$\rho_{s_0}C_\pi=-C_\pi$ and $\rho_{s_0}C_{\pi s_1}=-C_{\pi s_1}$,
thus again $(\rho_{s_0}\rho_{s_1})^2 C_\pi = (-\rho_{s_1})^2 C_\pi = C_\pi$.
\item[(3)]
If $\pi(1)\le k$ and $\pi(2)>k$ then
$\rho_{s_0}C_\pi = C_\pi$, $\rho_{s_0}C_{\pi s_1} = -C_{\pi s_1}$,
$\rho_{s_1}C_\pi = C_{\pi s_1}$, and $\rho_{s_1}C_{\pi s_1} = C_{\pi}$;
thus
$$
(\rho_{s_0}\rho_{s_1})^2 C_\pi= \rho_{s_0} \rho_{s_1}\rho_{s_0}
C_{\pi s_1} = -\rho_{s_0} \rho_{s_1} C_{\pi s_1}=-\rho_{s_0}
C_{\pi}=-C_{\pi}.
$$
Hence, $(\rho_{s_0}\rho_{s_1})^4 C_\pi= C_\pi$. \item[(4)] The
case $\pi(1)> k$ and $\pi(2)\le k$ is similar to Case (3) and is
left to the reader.
\end{itemize}
\qed

We deduce

\begin{thm}\label{B.irr}
All the irreducible representations of the classical Weyl group $B_n$
are minimal AY.
\end{thm}

\noindent{\bf Proof.} As before, let $\lambda$ be a partition of
$k$, $\mu$ a partition of $n-k$, $P$ a standard
Young tableau of shape $\lambda$ on the letters $1,\dots,k$  and
$Q$ a standard Young tableau of shape $\mu$ on the letters
$k+1,\dots,n$. There is a natural bijection between all pairs of
standard Young tableaux of shapes $\lambda$ and $\mu$ and elements
in the subset ${\cal B}_{P,Q}$: $(P,Q)^\pi \longleftrightarrow \pi\inv$,
where $(P,Q)^\pi$ is the ordered pair of tableaux obtained from
$(P,Q)$ by replacing each entry $i$ by $\pi(i)$. The Young Orthogonal Form
presented in Proposition~\ref{B-AY-yof} reduces to the
classical one given in Theorem~\ref{B-yof}, along this bijection.

\qed


%Abstract Young representations of other types (e.g., $B,D,\tilde
%A$) will be studied in \cite{U-III}. In particular, it will be
%shown that all irreducible representations of the Hecke algebra of
%type $B$ may be constructed using the AY method.

%%Examples of interesting representations or more ??


\section{Top Elements}\label{s.inter}

%\subsection{Intervals and Convexity}

%A {\em convex set} $\C$ in a poset $P$ is a subset $\C\subseteq P$ such that:
%if $x,y\in \C$ and $(x=x_0,\dots,x_k=y)$ is a path on the Hasse diagram of $P$
%(so $x_i$ either covers or is covered by $x_{i+1}$, for all $0\le i \le k-1$)
%of smallest possible length from $x$ to $y$
%then $x_i\in \C$ ($\forall i$).

%\begin{pro}\label{t.int_conv}
%All intervals in the weak Bruhat poset are convex.
%\end{pro}

%To prove this proposition we recall the notion of generalized
%descent classes from
%~\cite[Ch. 2]{T}\cite{BW, BW2}. See
%Section~\ref{s.prelim}. We shall use Tits Theorem
%(Theorem~\ref{t.tits}). We shall also use the following elementary result.

%Let $T$ be the set of all reflections in $W$, and let $A\subseteq T$
%be any subset. The (left) {\em $A$-descent set} of an element $w\in W$
%is defined by
%$$
%\D_A(w):=\{t\in A\,|\,\ell(tw)<\ell(w)\}.
%$$
%For $D\subseteq A\subseteq T$, the corresponding
%{\em generalized descent class} is
%$$
%W_A^D := \{w\in W\,|\,\D_A(w)=D\}.
%$$
%%
%%\medskip
%%
%%These sets were studied by Tits \cite[Ch. 2]{T} and Bj\"orner-Wachs
%%\cite{BW, BW2}.
%%Our notation follows \cite{BW}.
%%
%%\smallskip
%%
%The following theorem is a consequence of \cite[Theorem 2.19 ]{T}.
%See \cite[Theorem 5.3]{BW} and \cite[Proposition 6.2]{BW2}.

%\begin{thm}\label{t.tits}{\bf (Tits)}
%A subset $\C$ of $W$ is convex under right weak Bruhat order
%if and only if $\C=W_A^D$ for suitable subsets
%$D\subseteq A\subseteq T$.
%\end{thm}

%\begin{pro}\label{t.des_diff}{\rm\cite[Proof of Corollary 1.4.5]{BB}}
%If $w\in W$, $s\in S$ and $\ell(w)<\ell(ws)$ then
%$$
%\D_T(ws)=
%%\{t\in T\,|\, \ell(tws)<\ell(ws)\} =
%\D_T(w)
%%\{t\in T\,|\,\ell(tw)<\ell(w)\}
%\cup \{wsw^{-1}\}\qquad\mbox{\rm(disjoint union)}.
%$$
%\end{pro}

%\noindent{\bf Proof of Proposition~\ref{t.int_conv}}.
%Let $[v,w]$ be an interval in the right weak Bruhat poset
%of a Coxeter group $W$. By Proposition~\ref{t.des_diff},
%for every element $u\in [v,w]$
%$$
%\D_T(v)\subseteq \D_T(u) \subseteq \D_T(w).
%$$
%On the other hand, by Proposition (refer to~\cite{BB} ??) for
%every element $u\in W$
%$$
%\D_T(v)\subseteq \D_T(u) \subseteq \D_T(w)\Longrightarrow u\in[v,w].
%$$
%Thus, the interval $[u,v]$ is the generalized descent class $W_A^D$
%with $D=\D_T(v)$ and $A=(T\setminus \D_T(w) )\cup \D_T(v)$.
%Theorem~\ref{t.tits} completes the proof.
%
%\qed
%!!!!!!!!!!!!!!!!!!!

%\noindent{\bf Proof.} % of Proposition~\ref{t.int_conv}}.
%Let $[v,w]$ be an interval in the right weak Bruhat poset of a
%Coxeter group $W$.
%\begin{pro}{\rm\cite[Proposition~3.1.3]{BB}}\label{t.weak_des}
%For $w_1, w_2\in W$, $w_1\le w_2$ (in weak Bruhat order) if and
%only if $\D_T(w_1)\subseteq \D_T(w_2)$.
%\end{pro}
%By Proposition~\ref{t.weak_des}, %\cite[Prop. 3.1.3]{BB},
%By~\cite[Proposition~3.1.3]{BB},  for every element $u\in W$:
%$$
%u\in[v,w] \Longleftrightarrow \D_T(v)\subseteq \D_T(u) \subseteq
%\D_T(w).
%$$
%Thus, the interval $[v,w]$ is the generalized descent class
%$W_A^D$ with $D=\D_T(v)$ and $A=(T\setminus \D_T(w) )\cup
%\D_T(v)$. Tits' result (Theorem~\ref{t.tits}) completes the proof.
%\qed

%\medskip

%It should be noted that intervals in the strong Bruhat poset are
%not necessarily convex.

%\begin{prb}
%Characterize partial orders on $W$ for which all intervals are
%convex.
%\end{prb}

%\medskip

%\begin{thm}\label{t.x1}
%%Thm ABR1
%{\rm\cite[Prop. 1.3]{U1}} Let $W$ be a simply laced Coxeter group. Then
%every minimal AY cell is convex (in the right weak Bruhat poset).
%\end{thm}
%
%\medskip

This section is motivated by the following reformulation of a theorem of
Kriloff and Ram, based on results of Loszoncy~\cite{Lo}.

\begin{thm}\label{t.x2}{\rm\cite[Theorem 5.2]{KR}}
Let $W$ be a crystallographic reflection group. Then every minimal
AY cell is a left translate of an interval (in the right weak
Bruhat poset).
\end{thm}

\begin{rem}
%Remark:
By~\cite[Observation 3.3]{U-I}, one can assume that
the intervals are of the form $[id,w]$.
\end{rem}

%In~\cite[Corollary 4.4(i)]{U-I} we proved that every minimal AY
%cell in a simply laced (???) Coxeter group is convex (in the right
%weak Bruhat poset). Combining Theorem~\ref{t.x2} with
%Proposition~\ref{t.int_conv} gives

%\begin{cor}
%Let $W$ be a crystallographic reflection group. Then every minimal
%AY cell is convex (in the right weak Bruhat poset).
%\end{cor}

%%\medskip

%%\begin{prb}\label{p.x4}
%%%Q8: Does Ram's thm imply ABR1 ?
%%Are all intervals in the weak Bruhat poset necessarily convex?
%%\end{prb}
%%
%%In other words: Does Theorem~\ref{t.x2} imply Theorem~\ref{t.x1}?
%%
%%%\medskip

%\section{The Symmetric Group Revisited}
%
%In this section we address the above open problems
%(Problems~\ref{p.rep-cell1} and~\ref{p.x4})
%in the symmetric group $S_n$.
%In the first subsection minimal AY cells in $S_n$ are characterized.
%A solution of Problem~\ref{p.rep-cell1} follows.
%In the second subsection we characterize the top elements in $S_n$.


%\subsection{Top Elements in $S_n$}\label{s.inter_Sn}

%
%\begin{df}\label{d.top}
%%Def'n:
%\begin{itemize}
%\item[1.] Elements $w\in W$ are called good elements if
%the interval $[id,w]$ is a minimal and simple AY cell
%(see Definition~\ref{i6} above).
%\item[2.] Elements $w\in W$ are called top elements if
%any minimal AY representation on the interval $[id,w]$ is irreducible.
%\end{itemize}
%\end{df}

%\medskip


%\begin{prb}\label{p.x6}
%%Problem 9:
%Characterize  good and top elements.
%\end{prb}

\begin{df}\label{d.top}
%%Def'n:
%\begin{itemize}
%\item[1.] Elements $w\in W$ are called good elements if
%the interval $[id,w]$ is a minimal and simple AY cell
%(see Definition~\ref{i6} above).
%\item[2.]
An element $w\in W$ is a {\em top} element if the interval $[id,w]$
is a minimal AY cell which carries an {\em irreducible} AY representation
of $W$.
%\end{itemize}
\end{df}

The goal of this section is to characterize the top elements in
the symmetric group $S_n$.

\begin{df}\label{d.row}
Let $Q$ be a standard skew Young tableau.
\begin{itemize}
\item[1.]
$Q$ is a {\em row (column) tableau} if and only if the
entries in each row (column) are larger than the entries in all
preceding rows (columns).
\item[2.]
The {\em row word} of $\, Q$ is obtained by reading $Q$
row by row from right to left.
The {\em column word} of $\, Q$ is obtained by reading $Q$
column by column from bottom to top.
\end{itemize}
\end{df}

\begin{exa}
The tableau
\[
\begin{array}{ccc}
1 & 2 & 3 \\
4 & 5     \\
\end{array}
\]
is a row tableau. Its row word is the permutation $[3,2,1,5,4]\in S_5$
and its column word is  $[4,1,5,2,3]\in S_5$.
\end{exa}


%Recall the definition of top elements (Definition~\ref{d.top}) above.
Our result is that there is a bijection between top elements of $S_n$ and partitions
of $n$. More explicitly:

\begin{thm}\label{t.s5}
%Thm 11:
%The interval $[id,\pi]$ (in the right weak Bruhat order of $S_n$) is
%an irreducible AY cell for
A permutation $\pi\in S_n$ is a top element if and only if $\pi$
is the column word of a row standard Young tableau of shape $\lambda$,
where $\lambda$ is a partition of $n$.
\end{thm}

To prove this theorem we need the following lemma.

%\begin{df}
%Let $\la$ be a partition of $n$ and
%$Q$ be a fixed SYT of shape $\la$.
%Define a partial order on the set
%of SYT of shape $\la$ as follows:
%
%Assume $P=Q^{\pi\inv}$ and $T=Q^{\sigma\inv}$ are two SYT of shape $\la$. Then
%
%$P\le_Q T$ if and only if $\pi\le \sigma$ in the right weak Bruhat order
%of $S_n$.
%
%Denote this poset by $(SYT_{\la}, \le_Q)$.
%\end{df}

%\begin{lem}\label{t.s7}
%$(SYT_\la, \le_Q)$ is an interval if and only if $Q$
%is either row or column tableau.
%\end{lem}

\begin{lem}\label{t.s7}
Let $Q$ be a standard Young tableau of order $n$.\\
The set $\{\pi\in S_n\,|\,Q^{\pi\inv} \hbox{is standard}\}$ is
an interval in the right weak Bruhat order if and only if
$Q$ is either a row tableau or a column tableau.
The maximal element in the interval is the column (respectively, row)
word of the tableau.
\end{lem}

\noindent{\bf Proof.}
Denote $B_Q:=\{\pi\in S_n|\ Q^{\pi\inv} \hbox{ is standard}\}$.

First, we prove the easy direction. Assume that $Q$ is a row
tableau. By Theorem~\ref{t.symm} and %\cite[Corollary 4.4]{U-I}
Proposition~\ref{t.main.convex}, $B_Q$ is convex. Thus, to prove
that $B_Q$ is an interval $[id,\pi]$ it suffices to show that
there  is a unique element $\pi\in B_Q$ such that $\pi s\not\in
B_Q$ for all $s\not\in \D(\pi)$. Indeed, if $\sigma\in B_Q$ and
$Q^{\sigma\inv}$ is not the column tableau then there exists $i$
$(1\le i\le n-1)$ such that $i+1$ is southwest of $i$ in
$Q^{\sigma\inv}$. In this case, $\sigma s_i\in B_Q$ and
$\ell(\sigma s_i)> \ell(\sigma)$. If $\sigma\in B_Q$ and
$Q^{\sigma\inv}$ is the column tableau then there is no $i$ $(1\le
i\le n-1)$ such that $i+1$ is southwest of $i$ in
$Q^{\sigma\inv}$. In this case, if $\sigma s_i\in B_Q$ then
$\ell(\sigma s_i)<\ell(\sigma)$. We conclude that the unique
maximum $\sigma$ is the column word of the row tableau $Q$.

Similarly for a column tableau $Q$.

\medskip

Now we prove the opposite direction. Assume that $Q$ is a not a
row or column tableau. We will show that $B_Q$ has at least two
maximal elements (with respect to right weak Bruhat order).
Thus, $B_Q$ is not an interval.

If the standard Young tableau  $Q$ is a not a row or column
tableau then $Q$ has at least two rows and two columns. Without
loss of generality, the letter $2$ is in the first row
(i.e., in box $(1,2)$) of $Q$.
Then the letter in box $(\la'_1,1)$ is bigger than 2.

To find the first maximal element, start with $\pi\in B_Q$ such
that $Q^{\pi\inv}$ is a column tableau
%of shape of $Q$
and proceed ``up" in $B_Q$.
%Look at the corresponding tableaux and
Observe that each step in this process is a right multiplication
by $s_i$ such that the resulting permutation is in $B_Q$ and
longer. To satisfy this, $i$ and $i+1$ could not be in the same row or
column in $Q^{\pi\inv}$ (where at each step we substitute $\pi
s_i:=\pi$). Also, the letter of $Q$ in the box of $i$ in $Q^{\pi\inv}$
must be bigger than the letter of $Q$ in the box of $i+1$ in
$Q^{\pi\inv}$. The letter in $(1,2)$  is the minimal one in the
subtableau consisting all columns except the first one. Thus
cannot move along the process. We conclude

\smallskip

\noindent{\bf Claim 1.} For every $j$, $1\le j \le\la'_1+1$, the
position of the letter $j$ is invariant under this process. For
$j\le \la'_1$ the position is $(j,1)$; the position of $\la'_1+1$
is $(1,2)$.

\smallskip

Thus, we obtained one maximal element, which is determined
by a tableau with $1,...,\la'_1$ in the first column.

\smallskip

As $Q$ is not a row tableau there exists a minimal row $j$ for
which the letter in box $(j,\la_j)$ of $Q$ is bigger than the letter
in box $(j+1,1)$. To find the second maximal element, start with a
permutation in $B_Q$ determined by the standard Young tableau of the
same shape as $Q$, in which the first letters are placed in the
subshape $\{(a,b)|\ b\le \la_j\}$ in lexicographic order, and
the rest are placed in the remaining ``upper right corner" in
lexicographic order. We proceed ``up" as before; namely, by
right multiplication by $s_i$ such that the resulting permutation
is in $B_Q$ and longer.

\smallskip

\noindent{\bf Claim 2.} The set of boxes in which the letters
$1,...,j\cdot \la_j-1$  are located (in the resulting tableau) and
the locations of $j\cdot \la_j$ and $j\cdot \la_j+1$ are invariant
under this process.

\smallskip

To verify this, it suffices to show that the location of $j\cdot
\la_j+1$ is invariant under this process. Indeed, notice that as
long as $j\cdot \la_j+1$ is in the box $(j+1,1)$ $j\cdot \la_j$
must be located in box $(j,\la_j)$ (as it cannot switch with
$j\cdot\la_j-1$ which is located either in same row or column of $j\cdot\la_j$).
But the letters in boxes $(j+1,1)$ and $(j,\la_j)$ of $Q$ are
in reverse order; thus replacing $j\cdot \la_j+1$ with $j\cdot\la_j$
will shorten the permutation (and is not ``up"!).

We also cannot replace $j\cdot \la_j+1$ with $j\cdot \la_j+2$. To
verify this notice that $j\cdot \la_j+2$ has three possible
locations during our process: $(j+1,2)$, $(j+2,1)$ and $(1,\la_j+1)$.
If it is located in box $(j+1,2)$ then it is in the same row as
$j\cdot \la_j+1$, and thus switching them gives a nonstandard
tableau; thus sends us out of $B_Q$. If it is located in box $(j+2,1)$
then it is in the same column as $j\cdot \la_j+1$, and thus switching them
sends us out of $B_Q$. So, we may assume that $j\cdot \la_j+2$ is
located in box $(1,\la_j+1)$. In this case $j>1$ and, by the definition
of $j$, the letter in box $(1,\la_j+1)$ of $Q$ is less than the letter
in box $(2,1)$ of $Q$ which is, in turn,
%(by standard),
less than the letter in box $(j+1,1)$. Thus we cannot switch $j\cdot \la_j+1$ and
$j\cdot \la_j+2$ in this case as well.

\medskip

To complete the proof, notice that the letter in box $(\la'_1,1)$ in
the first maximal tableau is $\la'_1$, while in the second maximal
tableau it is bigger. Thus the processes determine two different
maximal tableaux.
\qed

\medskip

\noindent{\bf Proof of Theorem~\ref{t.s5}.} By
Corollary~\ref{t.irr2}, the derived content vector of a standard
Young tableau of shape $\lambda/\mu$ gives an irreducible
representation if and only if $\mu$ is the empty partition. This
fact together with Theorem~\ref{t.symm} imply that $\sigma\in S_n$
is a top element if and only if
$[id,\sigma] = \{\pi\in S_n\,|\,Q^{\pi\inv} \hbox{ is standard}\}$
for some standard tableau $Q$.
Lemma~\ref{t.s7} completes the proof. \qed


\bigskip

\noindent{\bf Acknowledgments.}
The authors thank Eli Bagno and Yona Cherniavsky
for useful comments.


\begin{thebibliography}{ABR}

\bibitem{U-I}
R.\ M.\ Adin, F.\ Brenti and Y.\ Roichman,
{\em A unified construction of Coxeter group representations (I)},
Adv.\ Appl.\ Math., to appear, arXiv:math.RT/0309364.
%preprint, 2003,\\
%{\tt <http://arXiv.org/abs/math.RT/0309364>}.


%\bibitem{U-III}
%R.\ M.\ Adin, F.\ Brenti and Y.\ Roichman, {\em A unified
%construction of Coxeter group representations (III)}, in
%preparation.

%\bibitem{ABR}
%R.\ M.\ Adin, F.\ Brenti and Y.\ Roichman,
%{\em Descent representations and multivariate statistics},
%Trans.\ Amer.\ Math.\ Soc., to appear.

%{\em Descent numbers and major indices for the hyperoctahedral group},
%Adv.\ Appl.\ Math.~27 (2001), 210--224.

%\bibitem{APR}
%R.\ M.\ Adin, A.\ Postnikov and Y.\ Roichman,
%{\em On characters of Weyl groups},
%Discrete Math.~226 (2001), 355--358.

%\bibitem{BR}
%H.\ Barcelo and A.\ Ram,
%{\em Combinatorial representation theory},
%in: New Perspectives in Geometric Combinatorics,
%MSRI Publications Vol. 38, 1999, 23--90.

%\bibitem{BGG}
%I.\ N.\ Bernstein, I.\ M.\ Gelfand and S.\ I.\ Gelfand,
%{\em Schubert cells and cohomology of Schubert spaces $G/P$},
%Usp.\ Mat.\ Nauk.~28 (1973), 3--26.

%\bibitem{BB}
%A.\ Bj\"{o}rner and F.\ Brenti,
%{\em Combinatorics of Coxeter Groups},
%Springer Verlag, to appear.

\bibitem{BV2}
D.\ Barbasch and D.\ Vogan, \ {\em Primitive ideals and orbital
integrals in complex exceptional groups}, J.\ Algebra~80 (1983),
350--382.

\bibitem{BW}
A.\ Bj\"{o}rner and M.\ Wachs,
{\em Generalized quotients in Coxeter groups},
Trans.\ Amer.\ Math.\ Soc.~308 (1988), 1--37.

%\bibitem{BW2}
%A.\ Bj\"{o}rner and M.\ Wachs,
%{\em Permutation statistics and linear extensions of posets},
%J. Combin. Theory Ser. A~58 (1991), 85--114.

%\bibitem{B}
%N.\ Bourbaki,
%{\em Elements of Mathematics, Lie Groups and Lie Algebras},
%Springer-Verlag, Berlin, 2002.

%\bibitem{BH}
%B.\ Brink and R.\ Howlett,
%??.

%\bibitem{Deo}
%Deodhar,
%??.

\bibitem{DJ} R.\ Dipper and G.\ D.\ James, {\em Representations of Hecke
algebras of general linear groups}, Proc. London Math. Soc. 52
(1986), 20--52.

%\bibitem{GR} A.\ M.\ Garsia and J.\ Remmel, {\em Shuffles of permutations
%and the Kronecker product}, Graphs and Combinatorics 1 (1985),
%217--263.

\bibitem{Geck} M.\ Geck,
%Geck, Meinolf(F-LYON-GD)
{\em On the induction of Kazhdan-Lusztig cells}, Bull.\ London\
Math.\ Soc.~35 (2003), 608--614.

%\bibitem{Le}
%J.\ J.\ Graham and G.\ I.\ Lehrer,
%{\em Cellular algebras},
%Invent.\ Math.~123 (1996), 1--34.

%\bibitem{Hi}
%H.\ L.\ Hiller,
%{\em Geometry of Coxeter Groups},
%Res.\ Notes in Math.~54, Pitman, Boston, 1982.

%\bibitem{Ho}
%P.\ N.\ Hoefsmit,
%{\em Representations of Hecke algebras of finite groups with $BN$-pairs of
%classical type},
%PhD Thesis, Univ.\ of British Columbia, 1974.

%\bibitem{Hum2}
%J.\ E.\ Humphreys,
%{\em Introduction to Lie Algebras and Representation Theory},
%Springer-Verlag, New-York, 1972.

\bibitem{Greene} C.\ Greene,
{\em A rational-function identity related to the
Murnaghan-Nakayama formula for the characters of $S_n$}, J.\ Alg.
Combin. (1992), 235--255.

\bibitem{Hum}
J.\ E.\ Humphreys,
{\em Reflection Groups and Coxeter Groups},
Cambridge Studies in Adv.\ Math.~29,
Cambridge Univ.\ Press, Cambridge, 1990.

\bibitem{Ja}
G.\ D.\ James,
{\em The Representation Theory of the Symmetric Groups},
Lecture Notes in Math.~682, Springer-Verlag, 1978.

\bibitem{JK}
G.\ D.\ James and A.\ Kerber,
{\em The Representation Theory of the Symmetric Group},
Encyclopedia of Math. and its Appl.~16,
Addison-Wesley, 1981.

%\bibitem{Jo}
%A.\ Joseph, ??

%\bibitem{Ka}
%D.\ Kazhdan,
%personal communication, 2003.

\bibitem{KL}
D.\ Kazhdan and G.\ Lusztig,
{\em Representations of Coxeter groups and Hecke algebras},
Invent.\ Math.~53 (1979), 165--184.

\bibitem{KR}
C.\ Kriloff and A.\ Ram, {\em Representations of graded Hecke
algebras}, Rep. Theory~6 (2002), 31--69.

\bibitem{Lo} J.\ Loszoncy,
{\em Standard Young tableaux in the Weyl group setting}, J.
Algebra~220 (1999), 255--260.

%\bibitem{Md}
%I.\ G.\ Macdonald,
%{\em Symmetric Functions and Hall Polynomials},
%second edition, Oxford Math.\ Monographs,
%Oxford Univ.\ Press, Oxford, 1995.

\bibitem{OV}
A.\ Okounkov and A.\ M.\ Vershik,
{\em A new approach to representation theory of symmetric groups},
Selecta Math.\ (N.~S.) 2 (1996), 581--605.

\bibitem{P}
I.\ A.\ Pushkarev, {\em On the theory of representations of the
wreath products of finite groups and symmetric groups}, Zap.\
Nauchn.\ Sem.\ S.-Peterburg.\ Otdel.\ Mat.\ Inst.\ Steklov (POMI)
240 (1997), Teor.\ Predst.\ Din.\ Sist.\ Komb.\ i Algoritm.\
Metody.~2, 229--244, 294--295; translation in J.\ Math.\ Sci. (New
York) 96 (1999), 3590--3599.

%\bibitem{Ra}
%A.\ Ram,
%{\em Seminormal representations of Weyl groups and Iwahori-Hecke algebras},
%Proc.\ London Math.\ Soc.~75 (1997), 99--133.

\bibitem{Ram03}
A.\ Ram,
{\em Affine Hecke algebras and generalized standard Young tableaux},
J.\ Algebra~230 (2003), 367--415.


\bibitem{Ram03b}
A.\ Ram,
{\em Skew representations are irreducible},
Contemp.\ Math.~325 (2003), 161--189.

%\bibitem{Re}
%C.\ Reutenauer,
%{\em Free Lie Algebras},
%London Math.\ Soc.\ Monographs, New Series 7, Oxford Univ.\ Press, 1993.

%\bibitem{Ro}
%Y.\ Roichman,
%{\em Induction and restriction of Kazhdan-Lusztig cells},
%Adv.\ Math.~134 (1998), 384--398.

\bibitem{Sa}
B.\ E.\ Sagan,
{\em The Symmetric Group: Representations, Combinatorial Algorithms \&
Symmetric Functions},
Wadsworth and Brooks/Cole, Monterey, CA, 1991.

%\bibitem{Sc} M.-P.\ Sch\"utzenberger,
%{\em La correspondence de Robinson},
%in: Combinatoire du Groupe Symmetrique,
%Lecture Notes in Math. 579, pp. 59--113, Springer-Verlag, 1977.

%\bibitem{So}
%L.\ Solomon,
%{\em The orders of the finite Chevalley groups},
%J. Algebra~3 (1966), 376--393.

%\bibitem{Sta76}
%R.\ P.\ Stanley,
%{\em Binomial posets, M\"{o}bius inversion, and permutation enumeration},
%J. Combin.\ Theory Ser.~A 20 (1976), 336--356.

%\bibitem{St1}
%R.\ P.\ Stanley,
%{\em Enumerative Combinatorics}, Vol.~1,
%Wadsworth and Brooks/Cole, Monterey, CA, 1986.

\bibitem{St2}
R.\ P.\ Stanley,
{\em Enumerative Combinatorics}, Vol.~2,
Cambridge Studies in Adv.\ Math.~62,
Cambridge Univ.\ Press, Cambridge, 1999.

\bibitem{St_sign}
R.\ P.\ Stanley,
{\em Some remarks on sign-balanced and maj-balanced posets},
Adv.\ Appl.\ Math.~34 (2005), 880--902.

\bibitem{Ste}
J.\ Stembridge,
{\em personal communication}, 2004.

%\bibitem{T}
%J.\ Tits,
%{\em Buildings of Spherical Type and Finite BN-Pairs},
%Lecture Notes in Math.~386, Springer-Verlag, Berlin and New-York, 1974.

%\bibitem{V}
%A.\ Vershik,
%{\em Local algebras and a new version of Young's orthogonal form},
%in: Topics in Algebra, Banach Center Publications, Vol.~26 Part~2,
%PWN-Polish Scientific Publications, Warsaw 1990, 467--473.

\end{thebibliography}
\end{document}


\section{Induction and Restriction}\label{s.induce}

The following observation gives a combinatorial procedure for
restricting AY representations to parabolic subgroups. This
procedure is analogous to the one given by Barbasch and Vogan for
Kazhdan-Lusztig cell representations~\cite[Prop. 3.11]{BV2}.

\begin{obs}\label{t.i1}
Let $(W,S)$ be a finite Coxeter system, and let $P=\langle
J\rangle$ $(J\subseteq S)$ be a parabolic subgroup of $W$.
%Let $^J W$ be the set of representatives of minimal length of
%the left cosets of $P$ in $W$.
Let $(\rho,\C)$ be a minimal AY pair for $W$. Then
\begin{itemize}
\item[(1)] $\C$ is a disjoint union of sets of the form $r_i{\cal
D}_i$ where, for each $i$, $r_i\in W$ and ${\cal D}_i$ is a
minimal AY cell in $P$. \item[(2)] The restricted representation
${\rho\downarrow}_P^W$ is isomorphic to the direct sum
$\bigoplus_{i}\psi^{{\cal D}_i}$, where the sum runs over the
${\cal D}_i$ in (1) above and, for each $i$, $\psi^{{\cal D}_i}$
is a minimal AY representation of $P$ on $V_{{\cal D}_i}$.
\end{itemize}
\end{obs}

\noindent{\bf Proof.} Axiom $(A)$ is equivalent to the following
statement:
%\begin{itemize}
%\item[$(A')$]
for any parabolic subgroup $P = \langle J\rangle$ of $W$ (where
$J\subseteq S$) and any $w\in \C$, the ``coset subspace'' $V_{wP
\cap \C}$ is invariant under $\T(p)$, for all $p\in P$
%\end{itemize}
(see~\cite[Observation 3.2]{U-I}). \qed

\begin{rem}
Here $\psi^{{\cal D}_i}$ is some AY representation on the AY cell
${\cal D}_i$. Note that, unlike the analogous restriction rule for
Kazhdan-Lusztig representations, $\psi^{{\cal D}_i}$ is not
uniquely determined by ${\cal D}_i$.
%See discussion in Section~\ref{Kazhdan} below.
\end{rem}

The following is a combinatorial procedure for induction, which is
analogous to the one for Kazhdan-Lusztig cells, proved by Barbasch
and Vogan for Weyl groups~\cite[Prop. 3.15]{BV2} and by Geck for
Coxeter groups~\cite{Geck}.

\begin{thm}\label{t.i4}
Let $(W,S)$ be a finite Coxeter system, $P=\langle J\rangle$
$(J\subseteq S)$ a parabolic subgroup of $W$,
%Let $\cal D$ a minimal AY cell in $P$ and let $\rho^{\cal D}$ be an AY
%representation of $P$ associated to $\cal D$.
and $W^J$ be the set of all representatives of minimal length of
the right cosets of $P$ in $W$. If $(\psi,\cal D)$ is a minimal AY
pair for $P$, then:
\begin{itemize}
\item[(1)] ${\cal D} W^J$ is a minimal AY cell in $W$. \item[(2)]
The induced representation $\psi\uparrow ^W_P$ is isomorphic to a
(minimal) AY representation on $V_{{\cal D} W^J}$.
\end{itemize}
\end{thm}

\begin{rem}
${\cal D} W^J$ is a minimal AY cell, and not a just a union of
such cells as in the analogous theorem for Kazhdan-Lusztig cells.
\end{rem}

For the proof of Theorem~\ref{t.i4} we shall need the following

%1111111111111111111111111111 from now on: erase old proof (using Bjorner-Wachs)
%
%\begin{thm}\label{t.lattice}{\rm\cite[Theorem 4.1]{BW}}
%%of [Bjorner and Wachs, "Generalized quotients in
%%coxeter groups", Trans. AMS 308(1988)], we show that
%For every Coxeter system $(W,S)$ and $J\subseteq S$, $W^J$ is a
%complete meet semilattice with respect to the weak Bruhat order,
%and is therefore a lattice if $W^J$ is finite.
%\end{thm}

\begin{pro}{\rm\cite[Proposition~3.1.3]{BB}}\label{t.weak_des}
For $w_1, w_2\in W$, $w_1\le w_2$ (in weak Bruhat order) if and
only if $\D_T(w_1)\subseteq \D_T(w_2)$.
\end{pro}

The proof of~\cite[Proposition~3.1.3]{BB} actually gives an
explicit result (to be used later).

\begin{pro}\label{t.des_diff}
If $w\in W$, $s\in S$ and $\ell(w)<\ell(ws)$ then
$$
\D_T(ws)= \D_T(w) \cup \{wsw^{-1}\}\qquad\mbox{\rm(disjoint
union)}.
$$
\end{pro}

Since $r$ belongs to $W^J$ if and only if $\D_T(r)\cap
J=\emptyset$, we conclude

\begin{cor}\label{t.fact}
If $r\in W^J$ and $r'\le r$ in weak Bruhat order, then $r'\in
W^J$.
\end{cor}

%\begin{cor}\label{t.cor-lattice}
%Let $(W,S)$ be a finite Coxeter system and $J\subseteq S$. Let
%$r\in W^J$, $s,t\in S$, and $w_{s,t}$ be the longest element in
%the parabolic subgroup $\langle s,t \rangle$. Then
%$$
%rs\in  W^J \hbox{ {\em and} } rt\in  W^J \Longrightarrow
%rw_{s,t}\in W^J.
%$$
%\end{cor}
%
%\noindent{\bf Proof.} By Theorem~\ref{t.lattice}, there exists a
%join $v$ of $rs$ and $rt$ in $W^J$. Clearly, $rw_{s,t}$ is the
%join of $rs$ and $rt$ in the weak Bruhat poset $W$. Thus
%$rw_{s,t}<v$ in the weak Bruhat order. By Corollary~\ref{t.fact},
%$rw_{s,t}\in W^J$ (hence $v=rw_{s,t}$). \qed

\begin{lem}\label{t.i5}
Let $(W,S)$ be a finite Coxeter system, $P = \langle J \rangle$
$(J\subseteq S)$ a parabolic subgroup of $W$, and $W^J$ the set of
minimal right coset representatives of $P$ in $W$. Let $s\in S$ be
a simple reflection and let $r\in W^J$. Then: either
\begin{itemize}
\item[(1)] $rs\in W^J$; or \item[(2)] $rs\not\in W^J$ and $rs=pr$,
where $p\in J = S\cap P$ is a simple reflection in $P$.
\end{itemize}
\end{lem}


\noindent{\bf Proof.} If $\ell(rs) < \ell(r)$ then, by
Proposition~\ref{t.des_diff}, $\D_T(rs) =
\D_T(r)\setminus\{rsr^{-1}\} \subseteq \D_T(r)$ and therefore
$rs\in W^J$. Assume, therefore, that $\ell(rs) > \ell(r)$. Then
$\D_T(rs) = \D_T(r)\cup\{rsr^{-1}\}$. If $rsr^{-1}\not\in J$ then
$\D_T(rs) \cap J = \emptyset$, so that again $rs\in W^J$. If
$rsr^{-1}\in J$ then $rs=pr$ with $p=rsr^{-1}\in J$, as claimed.
\qed


%\noindent{\bf Proof.} (we give a complete proof for simply laced
%groups; the proof for other groups is similar.)
%
%By induction on the length of $r$. For $\ell(r)=0$ (i.e., $r=1$)
%the lemma clearly holds. Assume that the lemma holds for all
%representatives $r\in W^J$ of length $\ell(r)<k$. Let $r\in W^J$
%be a representative of length $k$ and let $s\in S$ be a simple
%reflection.
%
%\begin{itemize}
%\item[{\bf Case (a)}] There is a reduced expression of $r$,
%$r=s_1\cdots s_k$ with $s_k s=s s_k$.
%
%Then $rs=s_1\cdots s_k s= s_1\cdots s_{k-1} s s_k$.
%By~\cite[Propositions 3.1.3 and ??]{BB},
%%combined with Lemma~\ref{t.des_dif},
%a prefix of a reduced expression of $r\in W^J$ belongs to $W^J$. Thus
%By Corollary~\ref{t.fact}, $s_1\cdots s_{k-1}\in W^J$. By assumption,
%$r=s_1 \cdots s_{k-1} s_k\in W^J$. If $s_1\cdots s_{k-1}s\in W^J$
%then
% by Corollary~\ref{t.cor-lattice}, $rs=s_1\cdots s_{k-1}s_k s\in W^J$.
%
% We conclude that if $rs\not\in W^J$ then $s_1\cdots
% s_{k-1}s\not\in W^J$.
%Otherwise, by
%By the induction hypothesis together with Corollary~\ref{t.fact}, there
%exists $p\in S$ such that
%$$
%rs=s_1\cdots s_k s=s_1\cdots s_{k-1} s s_k=p s_1\cdots s_{k-1}
%s_k=pr.
%$$
%
%\item[{\bf Case (b)}] For all reduced expressions of $r$,
%$r=s_1\cdots s_k$ with $s_k s s_k=s s_k s$. If there is no reduced
%expression of $r$ with $s_{k-1}=s$ then $\ell(rs)>\ell(r)$ and
%$\D_T(rs)=\D_T(r)\cup rsr^{-1}$ does not contain a simple
%reflection from $J$. Hence $rs\in W^J$.
%
%Thus we may assume that $s_{k-1}=s$ . Hence
%$$
%rs = s_1\cdots s_{k-2} s_{k-1} s_k s= s_1\cdots s_{k-2} s s_k s=
%s_1\cdots s_{k-2} s_k s s_k.
%$$
%If  $s_1\cdots s_{k-2} s_k s\in W^J$ then, by
%Corollary~\ref{t.cor-lattice} and the assumption $r=s_1\cdots
%s_{k-2} s s_k\in W^J$, $rs=s_1\cdots s_{k-2} s_k s s_k\in W^J$.
%
%If $s_1\cdots s_{k-2} s_k\in W^J$ and $s_1\cdots s_{k-2} s_k
%s\not\in W^J$ we are done (by the induction hypothesis).
%
%At last, assume $s_1\cdots s_{k-2} s_k\not\in W^J$. By
%Corollary~\ref{t.fact}, $r=s_1\cdots s_k\in W^J$ implies $s_1\cdots
%s_{k-2} \in W^J$. By the induction hypothesis there exists $p\in
%S$ such that $s_1\cdots s_{k-2} s_k=p s_1\cdots s_{k-2}$ and thus
%$$
%rs=s_1\cdots s_{k-2} s_k s s_k=p s_1\cdots s_{k-2} s s_k = p
%s_1\cdots s_{k-2} s_{k-1} s_k=pr.
%$$
%
%\end{itemize}
%\qed

\medskip

\noindent{\bf Proof of Theorem~\ref{t.i4}.} Let $V_{\cal
D}=\sn_{\bbc}\{C_m\,|\,m\in {\cal D}\}$ be the representation
space of $\psi$. $V_{\cal D}$ is a right $\bbc[P]$-module. A
representation space for $\rho=\psi\uparrow_P^W$ is the right
$\bbc[W]$-module $V_{\cal D}\otimes_{\bbc[P]} \bbc[W]$, with basis
$B=\{C_m\otimes r\,|\,m\in {\cal D}, r\in W^J\}$. The action of
$\rho$ on basis elements is
$$
\rho_s(C_m\otimes r)=C_m\otimes rs \qquad(\forall s\in S,
w\in{\cal D}, r\in W^J).
$$
There are two cases:
\begin{itemize}
\item[(1)] $rs\in W^J$: Then $\rho_s(C_m\otimes r)=C_m\otimes
rs\in B$. \item[(2)] $rs\not\in W^J$: Then, by Lemma~\ref{t.i5},
$rs=pr$ with $p\in J=P\cap S$. Since $({\cal D},\psi)$ is an AY
pair for $P$, we can write
$$
\psi_p(C_m) = a_p(m) C_m + b_p(m) C_{mp}.
$$
Thus
\begin{eqnarray*}
\rho_s(C_m \otimes r) &=& C_m \otimes rs = C_m \otimes pr =\cr &=&
\psi_p(C_m) \otimes r = a_p(m) C_m \otimes r + b_p(m) C_{mp}
\otimes r.
\end{eqnarray*}
\end{itemize}
Using the natural bijection $\phi: B\to \{C_{mr}\,|\,m\in {\cal
D}, r\in W^J\}$ given by $\phi(C_m\otimes r) := C_{mr}$ we now
have:
%
\begin{equation}\label{e.rho}
\rho_s(C_{mr}) = \cases{%
C_{mrs}, &if $rs\in W^J$;\cr a_p(m)C_{mr} + b_p(m)C_{mrs},
&otherwise.}
\end{equation}
%
We conclude that the induced representation $\rho$ on $V_{{\cal
D}W^J}=\sn\{C_{mr} |\ m\in {\cal D}, r\in W^J\}$ is AY. Thus
${\cal D}W^J$ is an AY cell in $W$.

%Verifying minimality (i.e., strong connectivity) of this cell
%is easy and is left to the reader.
Regarding minimality: it is enough to show that for any $m,
m'\in{\cal D}$ and $r, r'\in W^J$ there is a path in $\G(W,S)$
from $mr$ to $m'r'$ along which $\rho$ has nonzero
$b$-coefficients. This path will consist of three parts:
$$
mr \to m \to m' \to m'r'.
$$
The middle part is actually within $\G(P,J)$, since
$$
\rho_p(C_m \otimes id) = C_m \otimes p = \psi_p(C_m) \otimes id
\qquad(\forall p\in J,\,m\in{\cal D}),
$$
and the minimality of $(\psi,{\cal D})$ implies the required
property %(by \cite[Corollary 4.4]{U-I}).
(by Proposition~\ref{t.main.convex}).

The first part has the form $mr = mr_k \to mr_{k-1} \to \ldots \to
mr_0 = m$, where, if $r = s_{j_1} \cdots s_{j_k} \in W^J$ (a
reduced expression), then $r_i := s_{j_1} \cdots s_{j_i}$ $(0\le i
\le k)$. By Corollary~\ref{t.fact}, $r_i\in W^J$ $(0\le i\le k)$,
and the first case in equation (\ref{e.rho}) shows that the
$b$-coefficients along this path are nonzero.

The third part is similar. \qed

\medskip

\noindent{\bf Historical Note:} Our first proof of
Theorem~\ref{t.i4} relied on the fact that, for finite $W$, $W^J$
is a lattice under weak Bruhat order. This was proved by Bj\"orner
and Wachs~\cite[Theorem 4.1]{BB}.

%Proof (missing) is similar to the proof of the following closely related result
%(which is also not complete). ??

%%\medskip

%\begin{thm}\label{t.i2}
%%Thm 4:
%If $T_{\partial \C}$ generates a proper parabolic subgroup $P$ of $W$
%then the corresponding AY representation is induced from $P$.
%\end{thm}

%%\smallskip

%\noindent{\bf Proof.}
%Let $J\subset S$ be the generating set of $P$.
%Let $f$ be a fixed  $\C$-generic vector.
%Now choose $0\ne g\in V$ such that:
%$$
%\langle g, \al_t\rangle=0 \qquad (\forall t\in T_{\partial\C})
%$$
%$$
%\langle g, \al_t\rangle\ne 0 \qquad (\forall t\in T \hbox{ s.t. } \al_t\in
%\hbox{span}\{\al_r|r\in T_{\partial\C}\}).
%$$
%This is possible since $\{\al_r|r\in T_{\partial\C}\}$ span a proper subspace of $V$,
%and countable number of linear hyperplanes $\langle g,\al_t\rangle=0$ cannot cover its complement.
%Clearly, $f+cg$ is $\C$-generic for any $c\in \bbr$ and $\rho^{f+cg}$ is equivalent
%to $\rho^f$ (by Theorem~\ref{b5}).

%Let $w\in\C$ and $s\in S\setminus J$, then $wsw^{-1}\not\in \hbox{ span }\{\al_r| r\in T_{\partial\C}$
%(why ??). It follows that
%%
%%
%%As $T_{\partial \C}$ generates a proper parabolic subgroup $P=\langle J
%%\rangle$ of $W$,
%%for every positive integer $n$ there exists a $\C$-generic vector
%%$g_n$ with
%$$
%a_s^{(cg)}(w)={1\over \langle cg,\al_{wsw^{-1}}\rangle}=
%{1\over \langle f,\al_{wsw^{-1}}\rangle}
%%%=\pm 1
%%\qquad (\forall s\in J, w\in {\C}))
%$$
%for all $wsw^{-1}\in T_{\partial \C}$,
%%and consequently $b_s^{(g_n)}(w)=0$,
%and
%$$
%a_s^{(cg)}(w)={1\over \langle cg,\al_{wsw^{-1}}\rangle}\to 0
%\qquad (\forall s\in S\setminus J, w\in \C))
%$$
%when $c\to \infty$
%and consequently $b_s^{(cg)}(w)\to 1$
%$\ (\forall s\in S\setminus J, w\in \C)$.
%%%By Theorem~\ref{b5},
%%%$\rho^{\mu f}$ and $\rho^f$ are equivalent.
%%%On the other hand, when $\mu\to \pm \i
%Thus the representation
%matrices of the generators $s\in S\setminus J$
%%of $\rho^{(g_n)}(s)$ $\ (\forall s\in S\setminus J)$,
%%%and  thus also
%%%of $\rho^{(\mu f)}(w)$ $\ (\forall w\in W)$
%tend to those of a representation induced  from $P$.
%%By Theorem~\ref{b5}, for all $n$
%%the representations $\rho^f$ and $\rho^{g_n}$
%%are equivalent; thus $\rho^f$ is equivalent to $\lim_{n\to \infty} \rho^{g_n}$, which is induced %from $P$.
%%%the character of $\rho^f$ is thus the character of the regular %representation.

%What about the repressentation matrices of $s\in J$ ????


%\qed

%\medskip

%In particular,

%\begin{cor}\label{t.i3}
%Let $W$ be a finite Weyl (Coxeter??) group,
%and let $f\in V$ be $W$-generic (i.e. $\langle f,\al_t\rangle \ne 0, \forall t\in T$). Then the corresponding representation $\rho^f$
%on $W$ is isomorphic to the regular representation of $W$.
%\end{cor}


=====================================

A {\em Coxeter system} is a pair $(W,S)$ consisting of a group $W$
and a set $S$ of generators for $W$, subject only to relations of
the form
$$
(st)^{m(s,t)}=1,
$$
where $m(s,s)=1$ and $m(s,t)=m(t,s)\ge 2$ for $s\ne t$ in $S$. In
case no relation occurs for a pair $(s,t)$, we make the convention
that $m(s,t)=\infty$. $W$ is called a {\em Coxeter group}. If
$m(s,t)\le 3$ for all $s\ne t$ then $(W,S)$ is called {\em simply
laced}. Throughout this paper we assume that the set $S$ of
generators is finite; the group $W$ itself may be infinite.

%The {\em Iwahori-Hecke algebra} (sometimes called the {\em generic algebra})
%${\cal H}_q(W)$ of a Coxeter system $(W,S)$
%is the algebra generated by $\{\hat{s}\,|\,s\in S\}$
%with the involution relation on generators replaced by
%\begin{equation}\label{e.deformed_inv}
%(\hat{s}-1)(\hat{s}+q_s)=0 \qquad (\forall s\in S),
%\end{equation}
%in addition to the usual braid relations: for any two distinct generators
%$s,t\in S$
%%$$
%%(\hat{s} \hat{t})^{\lfloor {m(s,t)\over 2}\rfloor}
%%\hat{s}^{\{{m(s,t)\over 2}\}} =
%%(\hat{t} \hat{s})^{\lfloor {m(s,t)\over 2}\rfloor}
%%\hat{t}^{\{{m(s,t)\over 2}\}};
%%$$
%$$
%\hat{s} \hat{t} \hat{s} \cdots=
%\hat{t} \hat{s} \hat{t} \cdots \qquad
%(m(s,t) \hbox{ factors on each side}).
%$$
%Here $q_s$ is an indeterminate depending only on the conjugacy class (in $W$)
%of the simple reflection $s$.
%%{\bf THIS IS THE GENERIC ALGEBRA, SEE HUMPHREYS, CHAP. 7}
%For convenience, we shall use the notation $q_t:=q_s$ for any reflection $t\in T$;
%here $s\in S$ is any generator (simple reflection) conjugate to $t$ in $W$.
%For example, if $W$ is an irreducible simply laced
%Coxeter group then all reflections are conjugate, and there is only one
%indeterminate $q$. If $W$ is an irreducible finite Weyl group
%then there are at most two values of $q$, corresponding to
%the classification of the roots into long and short.

%Note that our conventions are slightly non-standard;
%for the standard version, replace in (\ref{e.deformed_inv}) above
%each generator $\hat{s}$ by $-\hat{s}$.

Let $(W,S)$ be a Coxeter system, and let $\G=\G(W,S)$ be the
corresponding Cayley graph (with generators acting on the right):
its vertices are the elements of $W$, and $x, y\in W$ are
connected by an edge if and only if $x^{-1}y\in S$. $\G$ is a
connected undirected graph. A subset $\C \subseteq W$ is called
{\em convex} if, for any $x, y\in \C$, all the geodesics (paths of
shortest length) connecting $x$ to $y$ in $\G$ have all their
vertices in $\C$.

Let $P$ be a poset, and let $\G$ be its undirected Hasse diagram.
Thus $\G$ is an undirected graph which has $P$ as a vertex set,
with an edge $\{x,y\}$ whenever $x$ either covers or is covered by
$y$. A subset $\C$ of $P$ is called {\em convex} if, for any
$x,y\in\C$, all geodesics (shortest paths) connecting $x$ to $y$
in $\G$ have all their vertices in $\C$.

%In this paper,
Let $P$ be a Coxeter group $W$ with the right weak Bruhat order,
namely the transitive closure of the relation
$$
w<ws \iff w\in W, s\in S \hbox{\ and\ } \ell(w)<\ell(ws).
$$
Clearly, $\C\subseteq W$ is convex in the right Cayley graph
$\G(W,S)$ if and only if it is convex in the right weak Bruhat
poset $P$.

\bigskip

%A {\em convex set} $\C$ in a poset $P$ is a subset $\C\subseteq P$ such that:
%if $x,y\in \C$ and $(x=x_0,\dots,x_k=y)$ is a path on the Hasse diagram of $P$
%(so $x_i$ either covers or is covered by $x_{i+1}$, for all $0\le i \le k-1$)
%of smallest possible length from $x$ to $y$
%then $x_i\in \C$ ($\forall i$).

Let $T$ be the set of all reflections in $W$, and let $A\subseteq
T$ be any subset. The (left) {\em $A$-descent set} of an element
$w\in W$ is defined by
$$
\D_A(w):=\{t\in A\,|\,\ell(tw)<\ell(w)\}.
$$
For $D\subseteq A\subseteq T$, the corresponding {\em generalized
descent class} is
$$
W_A^D := \{w\in W\,|\,\D_A(w)=D\}.
$$
These sets were studied by Tits \cite[Ch. 2]{T} and
Bj\"orner-Wachs \cite{BW, BW2}. Our notation follows \cite{BW}.


The following theorem is a consequence of \cite[Theorem 2.19 ]{T}.
See \cite[Theorem 5.3]{BW} and \cite[Proposition 6.2]{BW2}.

\begin{thm}\label{t.tits}{\bf (Tits)}
A subset $\C$ of $W$ is convex under right weak Bruhat order if
and only if $\C=W_A^D$ for suitable subsets $D\subseteq A\subseteq
T$.
\end{thm}


\begin{df}\label{d.A_equiv}
Let $A\subseteq T$. Define a symmetric relation
$\leftrightarrow_A$ on $W$ by
$$
w \leftrightarrow_A ws \ \ \iff \ \ wsw^{-1}\not\in A,
$$
and let $\sim_A$ be the transitive closure of $\leftrightarrow_A$.
The {\em $A$-cell} $\C_A(w)$ of an element $w\in W$ is the
equivalence class of $w$ under $\sim_A$.
\end{df}

In geometric terms, these equivalence classes are the connected
components of the Cayley graph $\G(W,S)$ after deleting all the
edges $\{w,ws\}$ with $wsw^{-1}\in A$.

\begin{thm}\label{t.thm3}{\rm\cite[Theorem 4.10]{U-I}}
Let $u,v\in W$. Then
$$
u\sim_A v \ \ \iff \ \ \D_A(u)=\D_A(v).
$$
\end{thm}

\bigskip

Let $V$ be the root space of a Coxeter system $(W,S)$.
%see, e.g., \cite{Deo} or \cite{Hum}.
Thus $V$ is a vector space over $\bbr$ with a basis
$\{\al_s\,|\,s\in S\}$ indexed by the group generators. A
symmetric bilinear form $B$ is defined on $V$ by
$$
B(\al_s,\al_t) := -\cos{\pi\over m(s,t)}\qquad(\forall s,t\in S)
$$
(interpreted to be $-1$ in case $m(s,t)=\infty$). For each
generator $s\in S$ define a linear map $\sigma_s:V \to V$ by
$$
\sigma_s(v) := v - 2B(v,\al_s)\al_s\qquad(\forall v\in V).
$$
This yields a faithful $B$-preserving action $\sigma$ of $W$ on
$V$ (see, e.g.,~\cite{Hum}), and defines the corresponding {\em
root system}
$$
\Phi := \{\sigma_w(\al_s)\,|\,w\in W, s\in S\} \subseteq V.
$$
Let $T$ be the set of all conjugates of generators; its elements
are called {\em reflections} of $W$, and elements of $S$ are
called {\em simple reflections}. There is a bijection between
reflections in $T$ and {\em positive roots} in $\Phi$, given by
$t=wsw^{-1} \longleftrightarrow \al_t=\sigma_w(\al_s)$ (provided
that $\ell(w)<\ell(ws)$).

Throughout the paper $\langle \ ,\ \rangle$ is an arbitrary
positive definite bilinear form on $V$.

%In the general theory of Coxeter groups (as opposed to Lie Theory)
%there is no notion of short and long roots (See e.g. \cite[\S 5.6]{Hum}).
%However,  the set of roots is invariant under the group
%action. Since
%$w(\al_t)=\al_{wtw^{-1}}$,
%the length {\bf WHICH LENGTH? THE ONE GIVEN BY (|) OR THE ONE GIVEN
%BY $\langle , \rangle$  ?} is constant on each conjugacy class of %reflections.
%In a simply laced Coxeter group all reflections lie in one conjugacy class
%(see, e.g., \cite{Hum}); so it may be assumed that all roots in this
%group are unit vectors.

%%Under natural assumptions on type $B$,
%%there emerges the length distinction in our representation theory
%%(see ?? below). For this reason we will distinguish between short
%%and long roots ???

%The {\em height} of a positive root $\al_t=\sum\limits_{s\in S}c_s \al_s$ is
%the positive integer
%$$
%\hgt(\al_t) := \sum\limits_{s\in S} c_s.
%$$

\bigskip

Let $\la$ be a partition of $n$, and let $\T^\la$ be the
corresponding irreducible representation of $S_n$ (on the Specht
module $S^\la$). Let $\{v_Q\,|\,Q$ standard Young tableau of shape
$\la\}$ be the basis of $S^\la$ obtained from the basis of
polytabloids by the Gram-Schmidt process (see~\cite[\S 25]{Ja}).


%\begin{thm}\label{t.yof}{(\bf Classical Young Orthogonal Form)}
%{\rm\cite[\S 25.4]{Ja}}
%$$
%\T^\la(s_i)(v_Q)=
%\cases{%
%\frac{1}{\hk(i)}\ v_Q + \sqrt{1-\frac{1}{\hk(i)^2}}\ v_{s_i Q},
%&if $\ell(w)<\ell(ws_i)$;\cr
%-\frac{1}{\hk(i)}\ v_Q + \sqrt{1-{1\over\hk(i)^2}}\ v_{s_i Q},
%&if $\ell(w)>\ell(ws_i)$,}
%$$
%where  $s_i Q$ is the tableau obtained from $Q$ by
%interchanging $i$ and $i+1$.
%\end{thm}


\begin{thm}\label{t.yof}{\bf (Classical Young Orthogonal Form)}
{\rm\cite[\S 25.4]{Ja}} In the above notations,
$$
\T^\la(s_i)(v_Q)= \frac{1}{\hk(i)}\,v_Q +
\sqrt{1-\frac{1}{\hk(i)^2}}\,v_{Q^{s_i}}.
$$
\end{thm}

This setting is generalized naturally to skew shapes $\la/\mu$.
Standard Young tableaux of shape $\la/\mu$, hook distances on
these tableaux and skew Specht modules $S^{\la/\mu}$ are defined
analogously. In particular,

\section{Abstract Young Cells and Representations}\label{s.survey}

This section surveys
%construction and main
results from~\cite{U-I} which will be used in this paper. Recall
the definition of AY cells and representations from the
introduction.

%\bigskip

%\begin{prb}\label{p.rep-cell1}{\rm (Kazhdan~\cite{Ka})}
%Given a subset $\C\subseteq W$, how many nonequivalent
%abstract Young representations may be defined on $V_\C$?
%\end{prb}
%In particular,
%\begin{prb}\label{p.rep-cell2}
%Which subsets of $W$ are (minimal) AY cells?
%\end{prb}

%%The general Problem~\ref{p.rep-cell1} will be addressed in~\cite{U-II}.
%In this paper we give a partial solution to Problem~\ref{p.rep-cell2};
%see Sections~\ref{s.mincells}, \ref{s.des_rep} and~\ref{s.cells_Sn}.
%In particular, it will be shown that
%A minimal AY cell must be convex.

\begin{obs}\label{t.main_unitcell}{\rm\cite[Observation 3.3]{U-I}}
Every nonempty AY cell is a left translate of an AY cell
containing the identity element of $W$.
\end{obs}

\begin{pro}\label{t.main.convex}{\rm\cite[Corollary 4.4]{U-I}}
Every minimal AY cell is convex (in the right Cayley graph
$\G(W,S)$ or, equivalently, under right weak Bruhat order). In
particular, $b_s(w)\ne 0$ whenever $s\in S$ and $w, ws\in\C$.
\end{pro}

Important examples of AY cells are (standard) descent classes.
%(Section~\ref{s.des_rep}).

\bigskip

%%\subsubsection{Representations}\label{s.main_reps}
%\subsection{Main Results: Representations}\label{s.main_reps}

Surprisingly, Axiom $(A)$ leads to very concrete matrices, whose
entries are essentially inverse linear.

In~\cite{U-I}
%Section~\ref{s.reflect} and the Appendix
it is shown that, under mild conditions, Axiom $(A)$ is equivalent
to the following more specific version. Here $T$ is the set of all
reflections in $W$.

\begin{itemize}
\item[$(B)$] {\it For any reflection $t\in T$ there exist scalars
$\ua_t, \ub_t, \da_t, \db_t \in\bbf$ such that, for all $s\in S$
and $w\in \C$:
$$
\T_s(C_w) =\cases{%
\ua_{wsw^{-1}}C_w+\ub_{wsw^{-1}}C_{ws}, &if $\ell(w)<\ell(ws)$;\cr
\da_{wsw^{-1}}C_w+\db_{wsw^{-1}}C_{ws}, &if
$\ell(w)>\ell(ws)$.\cr}
$$
If $w\in\C$ and $ws\not\in\C$ we assume that $\ub_{wsw^{-1}}=0$
(if $\ell(w)<\ell(ws)$) or
$\db_{wsw^{-1}}=0$ (if $\ell(w)>\ell(ws)$).%
}
\end{itemize}

\begin{thm}\label{t.main.a1}{\rm\cite[Theorem 5.2]{U-I}}
Let $(\T,\C)$ be a minimal AY pair for the Iwahori-Hecke algebra
of $(W,S)$.
If %$\C$ contains the identity element of $W$ and also
$a_s(w)=a_{s'}(w')\then b_s(w)=b_{s'}(w')$ $(\forall s,s'\in S,
w,w'\in\C)$, then $\rho$ satisfies Axiom $(B)$.
%then Axioms $(A)$ and $(B)$ are equivalent.
\end{thm}


\begin{thm}\label{t.main.c1}{\rm\cite[Theorem 11.1]{U-I}}
The coefficients $\ua_t$ $(t\in T)$ determine all the character
values $\tr\T_w$ $(w\in W)$.

\end{thm}


The assumption regarding the coefficients $b_s(w)$ in
Theorem~\ref{t.main.a1} is merely a normalization condition.
Theorem~\ref{t.main.a1} shows that the coefficients $a_s(w)$ and
$b_s(w)$ in Axiom $(A)$ depend only on the reflection $wsw^{-1}\in
T$ and on the relation between $w$ and $ws$ in the right weak
Bruhat order. It turns out that for simply laced Coxeter groups
the coefficients $\ua_t$ are given by a linear functional.

%\medskip

Various normalizations for $\ub_t$ and $\db_t$ are possible:
symmetric ($\db_t = \ub_t$), seminormal ($\db_t = 1$), row
stochastic ($\ua_t + \ub_t = \da_t + \db_t = 1$), etc.\
\cite[Subsection 5.2]{U-I}. By Theorem~\ref{t.main.c1}, all these
normalizations give isomorphic representations.

Replacing $\langle f,\al_t\rangle$ by its $q$-analogue $[\langle
f,\al_t\rangle]_q$ gives representations of the Iwahori-Hecke
algebra ${\cal H}_q(W)$~\cite[Theorem 8.4]{U-I}.

\smallskip

The following theorem is complementary.

math0412506.extracted_bib
\begin{thebibliography}{ABR}

\bibitem{U-I}
R.\ M.\ Adin, F.\ Brenti and Y.\ Roichman,
{\em A unified construction of Coxeter group representations (I)},
Adv.\ Appl.\ Math., to appear, arXiv:math.RT/0309364.
%preprint, 2003,\\
%{\tt <http://arXiv.org/abs/math.RT/0309364>}.


%\bibitem{U-III}
%R.\ M.\ Adin, F.\ Brenti and Y.\ Roichman, {\em A unified
%construction of Coxeter group representations (III)}, in
%preparation.

%\bibitem{ABR}
%R.\ M.\ Adin, F.\ Brenti and Y.\ Roichman,
%{\em Descent representations and multivariate statistics},
%Trans.\ Amer.\ Math.\ Soc., to appear.

%{\em Descent numbers and major indices for the hyperoctahedral group},
%Adv.\ Appl.\ Math.~27 (2001), 210--224.

%\bibitem{APR}
%R.\ M.\ Adin, A.\ Postnikov and Y.\ Roichman,
%{\em On characters of Weyl groups},
%Discrete Math.~226 (2001), 355--358.

%\bibitem{BR}
%H.\ Barcelo and A.\ Ram,
%{\em Combinatorial representation theory},
%in: New Perspectives in Geometric Combinatorics,
%MSRI Publications Vol. 38, 1999, 23--90.

%\bibitem{BGG}
%I.\ N.\ Bernstein, I.\ M.\ Gelfand and S.\ I.\ Gelfand,
%{\em Schubert cells and cohomology of Schubert spaces $G/P$},
%Usp.\ Mat.\ Nauk.~28 (1973), 3--26.

%\bibitem{BB}
%A.\ Bj\"{o}rner and F.\ Brenti,
%{\em Combinatorics of Coxeter Groups},
%Springer Verlag, to appear.

\bibitem{BV2}
D.\ Barbasch and D.\ Vogan, \ {\em Primitive ideals and orbital
integrals in complex exceptional groups}, J.\ Algebra~80 (1983),
350--382.

\bibitem{BW}
A.\ Bj\"{o}rner and M.\ Wachs,
{\em Generalized quotients in Coxeter groups},
Trans.\ Amer.\ Math.\ Soc.~308 (1988), 1--37.

%\bibitem{BW2}
%A.\ Bj\"{o}rner and M.\ Wachs,
%{\em Permutation statistics and linear extensions of posets},
%J. Combin. Theory Ser. A~58 (1991), 85--114.

%\bibitem{B}
%N.\ Bourbaki,
%{\em Elements of Mathematics, Lie Groups and Lie Algebras},
%Springer-Verlag, Berlin, 2002.

%\bibitem{BH}
%B.\ Brink and R.\ Howlett,
%??.

%\bibitem{Deo}
%Deodhar,
%??.

\bibitem{DJ} R.\ Dipper and G.\ D.\ James, {\em Representations of Hecke
algebras of general linear groups}, Proc. London Math. Soc. 52
(1986), 20--52.

%\bibitem{GR} A.\ M.\ Garsia and J.\ Remmel, {\em Shuffles of permutations
%and the Kronecker product}, Graphs and Combinatorics 1 (1985),
%217--263.

\bibitem{Geck} M.\ Geck,
%Geck, Meinolf(F-LYON-GD)
{\em On the induction of Kazhdan-Lusztig cells}, Bull.\ London\
Math.\ Soc.~35 (2003), 608--614.

%\bibitem{Le}
%J.\ J.\ Graham and G.\ I.\ Lehrer,
%{\em Cellular algebras},
%Invent.\ Math.~123 (1996), 1--34.

%\bibitem{Hi}
%H.\ L.\ Hiller,
%{\em Geometry of Coxeter Groups},
%Res.\ Notes in Math.~54, Pitman, Boston, 1982.

%\bibitem{Ho}
%P.\ N.\ Hoefsmit,
%{\em Representations of Hecke algebras of finite groups with $BN$-pairs of
%classical type},
%PhD Thesis, Univ.\ of British Columbia, 1974.

%\bibitem{Hum2}
%J.\ E.\ Humphreys,
%{\em Introduction to Lie Algebras and Representation Theory},
%Springer-Verlag, New-York, 1972.

\bibitem{Greene} C.\ Greene,
{\em A rational-function identity related to the
Murnaghan-Nakayama formula for the characters of $S_n$}, J.\ Alg.
Combin. (1992), 235--255.

\bibitem{Hum}
J.\ E.\ Humphreys,
{\em Reflection Groups and Coxeter Groups},
Cambridge Studies in Adv.\ Math.~29,
Cambridge Univ.\ Press, Cambridge, 1990.

\bibitem{Ja}
G.\ D.\ James,
{\em The Representation Theory of the Symmetric Groups},
Lecture Notes in Math.~682, Springer-Verlag, 1978.

\bibitem{JK}
G.\ D.\ James and A.\ Kerber,
{\em The Representation Theory of the Symmetric Group},
Encyclopedia of Math. and its Appl.~16,
Addison-Wesley, 1981.

%\bibitem{Jo}
%A.\ Joseph, ??

%\bibitem{Ka}
%D.\ Kazhdan,
%personal communication, 2003.

\bibitem{KL}
D.\ Kazhdan and G.\ Lusztig,
{\em Representations of Coxeter groups and Hecke algebras},
Invent.\ Math.~53 (1979), 165--184.

\bibitem{KR}
C.\ Kriloff and A.\ Ram, {\em Representations of graded Hecke
algebras}, Rep. Theory~6 (2002), 31--69.

\bibitem{Lo} J.\ Loszoncy,
{\em Standard Young tableaux in the Weyl group setting}, J.
Algebra~220 (1999), 255--260.

%\bibitem{Md}
%I.\ G.\ Macdonald,
%{\em Symmetric Functions and Hall Polynomials},
%second edition, Oxford Math.\ Monographs,
%Oxford Univ.\ Press, Oxford, 1995.

\bibitem{OV}
A.\ Okounkov and A.\ M.\ Vershik,
{\em A new approach to representation theory of symmetric groups},
Selecta Math.\ (N.~S.) 2 (1996), 581--605.

\bibitem{P}
I.\ A.\ Pushkarev, {\em On the theory of representations of the
wreath products of finite groups and symmetric groups}, Zap.\
Nauchn.\ Sem.\ S.-Peterburg.\ Otdel.\ Mat.\ Inst.\ Steklov (POMI)
240 (1997), Teor.\ Predst.\ Din.\ Sist.\ Komb.\ i Algoritm.\
Metody.~2, 229--244, 294--295; translation in J.\ Math.\ Sci. (New
York) 96 (1999), 3590--3599.

%\bibitem{Ra}
%A.\ Ram,
%{\em Seminormal representations of Weyl groups and Iwahori-Hecke algebras},
%Proc.\ London Math.\ Soc.~75 (1997), 99--133.

\bibitem{Ram03}
A.\ Ram,
{\em Affine Hecke algebras and generalized standard Young tableaux},
J.\ Algebra~230 (2003), 367--415.


\bibitem{Ram03b}
A.\ Ram,
{\em Skew representations are irreducible},
Contemp.\ Math.~325 (2003), 161--189.

%\bibitem{Re}
%C.\ Reutenauer,
%{\em Free Lie Algebras},
%London Math.\ Soc.\ Monographs, New Series 7, Oxford Univ.\ Press, 1993.

%\bibitem{Ro}
%Y.\ Roichman,
%{\em Induction and restriction of Kazhdan-Lusztig cells},
%Adv.\ Math.~134 (1998), 384--398.

\bibitem{Sa}
B.\ E.\ Sagan,
{\em The Symmetric Group: Representations, Combinatorial Algorithms \&
Symmetric Functions},
Wadsworth and Brooks/Cole, Monterey, CA, 1991.

%\bibitem{Sc} M.-P.\ Sch\"utzenberger,
%{\em La correspondence de Robinson},
%in: Combinatoire du Groupe Symmetrique,
%Lecture Notes in Math. 579, pp. 59--113, Springer-Verlag, 1977.

%\bibitem{So}
%L.\ Solomon,
%{\em The orders of the finite Chevalley groups},
%J. Algebra~3 (1966), 376--393.

%\bibitem{Sta76}
%R.\ P.\ Stanley,
%{\em Binomial posets, M\"{o}bius inversion, and permutation enumeration},
%J. Combin.\ Theory Ser.~A 20 (1976), 336--356.

%\bibitem{St1}
%R.\ P.\ Stanley,
%{\em Enumerative Combinatorics}, Vol.~1,
%Wadsworth and Brooks/Cole, Monterey, CA, 1986.

\bibitem{St2}
R.\ P.\ Stanley,
{\em Enumerative Combinatorics}, Vol.~2,
Cambridge Studies in Adv.\ Math.~62,
Cambridge Univ.\ Press, Cambridge, 1999.

\bibitem{St_sign}
R.\ P.\ Stanley,
{\em Some remarks on sign-balanced and maj-balanced posets},
Adv.\ Appl.\ Math.~34 (2005), 880--902.

\bibitem{Ste}
J.\ Stembridge,
{\em personal communication}, 2004.

%\bibitem{T}
%J.\ Tits,
%{\em Buildings of Spherical Type and Finite BN-Pairs},
%Lecture Notes in Math.~386, Springer-Verlag, Berlin and New-York, 1974.

%\bibitem{V}
%A.\ Vershik,
%{\em Local algebras and a new version of Young's orthogonal form},
%in: Topics in Algebra, Banach Center Publications, Vol.~26 Part~2,
%PWN-Polish Scientific Publications, Warsaw 1990, 467--473.

\end{thebibliography}