%%
%%
%%  This article has been submitted and accepted for publication in
%%  THE FOATA FESTSCHRIFT,
%%  a special issue of THE ELECTRONIC JOURNAL OF COMBINATORICS
%%  dedicated to DOMINIQUE FOATA at the occasion of his 60th birthday.
%%
%%  Author(s):		ALAIN LASCOUX and MARCEL-PAUL SCHUETZENBERGER
%%  Title:		TREILLIS ET BASES DES GROUPES DE COXETER
%%  Date of submission:	15 May 1995
%%  TeX version:	plain
%%  File size (approx):	102 kB
%%  Number of pages:	33
%%  Author's email:	al@litp.ibp.fr
%%
%%  Note: there are two separate PostScript files with figures
%%  permutoedre1.88 (333 kB) and permutoedre2.88 (282 kB)
%%
%%
% article  Treillis et Bases des Groupes de Coxeter
% suivi de Polynomes de KL pour les Varietes de Schubert vexillaires
% format a4new au debut       Juin 95

%%%%%%%%%%%%%%%%%   DEBUT   %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\magnification 1200

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   format
\hsize=11.25cm    
\vsize=18cm       
\parindent=12pt   \parskip=0pt     
\pageno=1 

% deux jeux d'offsets. Le premier concerne la \magnification=1000
% (si l'image n'est pas agrandie)

\hoffset=0cm    % offset horizontal en \magnification=1000
\voffset=1cm    % offset vertical en \magnification=1000
 
% Le deuxieme concerne  la \magnification=1200
% (lorsque l'image est agrandie de 20%)

\ifnum\mag=\magstep1
\hoffset=9mm   % offset horizontal en \magnification=1200
\voffset=10mm   % offset horizontal en \magnification=1200
\fi

\pretolerance=500 \tolerance=1000  \brokenpenalty=5000
\catcode`\@=11
\font\eightrm=cmr8         \font\eighti=cmmi8
\font\eightsy=cmsy8        \font\eightbf=cmbx8
\font\eighttt=cmtt8        \font\eightit=cmti8
\font\eightsl=cmsl8        \font\sixrm=cmr6
\font\sixi=cmmi6           \font\sixsy=cmsy6
\font\sixbf=cmbx6

% Fontes AMS

\font\tengoth=eufm10       \font\tenbboard=msbm10
\font\eightgoth=eufm8      \font\eightbboard=msbm8
\font\sevengoth=eufm7      \font\sevenbboard=msbm7
\font\sixgoth=eufm6        \font\fivegoth=eufm5

% Pour que les accents se placent correctement en mode math en corps 8 et 6

\skewchar\eighti='177 \skewchar\sixi='177
\skewchar\eightsy='60 \skewchar\sixsy='60

% Nouvelles familles pour les maths

\newfam\gothfam           \newfam\bboardfam

\def\tenpoint{%
  \textfont0=\tenrm \scriptfont0=\sevenrm \scriptscriptfont0=\fiverm
  \def\rm{\fam\z@\tenrm}%
  \textfont1=\teni  \scriptfont1=\seveni  \scriptscriptfont1=\fivei
  \def\oldstyle{\fam\@ne\teni}\let\old=\oldstyle
  \textfont2=\tensy \scriptfont2=\sevensy \scriptscriptfont2=\fivesy
  \textfont\gothfam=\tengoth \scriptfont\gothfam=\sevengoth
  \scriptscriptfont\gothfam=\fivegoth
  \def\goth{\fam\gothfam\tengoth}%
  \textfont\bboardfam=\tenbboard \scriptfont\bboardfam=\sevenbboard
  \scriptscriptfont\bboardfam=\sevenbboard
  \def\bb{\fam\bboardfam\tenbboard}%
  \textfont\itfam=\tenit
  \def\it{\fam\itfam\tenit}%
  \textfont\slfam=\tensl
  \def\sl{\fam\slfam\tensl}%
  \textfont\bffam=\tenbf \scriptfont\bffam=\sevenbf
  \scriptscriptfont\bffam=\fivebf
  \def\bf{\fam\bffam\tenbf}%
  \textfont\ttfam=\tentt
  \def\tt{\fam\ttfam\tentt}%
  \abovedisplayskip=12pt plus 3pt minus 9pt
  \belowdisplayskip=\abovedisplayskip
  \abovedisplayshortskip=0pt plus 3pt
  \belowdisplayshortskip=4pt plus 3pt 
  \smallskipamount=3pt plus 1pt minus 1pt
  \medskipamount=6pt plus 2pt minus 2pt
  \bigskipamount=12pt plus 4pt minus 4pt
  \normalbaselineskip=12pt
  \setbox\strutbox=\hbox{\vrule height8.5pt depth3.5pt width0pt}%
  \let\bigf@nt=\tenrm       \let\smallf@nt=\sevenrm
  \normalbaselines\rm}

\def\eightpoint{%
  \textfont0=\eightrm \scriptfont0=\sixrm \scriptscriptfont0=\fiverm
  \def\rm{\fam\z@\eightrm}%
  \textfont1=\eighti  \scriptfont1=\sixi  \scriptscriptfont1=\fivei
  \def\oldstyle{\fam\@ne\eighti}\let\old=\oldstyle
  \textfont2=\eightsy \scriptfont2=\sixsy \scriptscriptfont2=\fivesy
  \textfont\gothfam=\eightgoth \scriptfont\gothfam=\sixgoth
  \scriptscriptfont\gothfam=\fivegoth
  \def\goth{\fam\gothfam\eightgoth}%
  \textfont\bboardfam=\eightbboard \scriptfont\bboardfam=\sevenbboard
  \scriptscriptfont\bboardfam=\sevenbboard
  \def\bb{\fam\bboardfam}%
  \textfont\itfam=\eightit
  \def\it{\fam\itfam\eightit}%
  \textfont\slfam=\eightsl
  \def\sl{\fam\slfam\eightsl}%
  \textfont\bffam=\eightbf \scriptfont\bffam=\sixbf
  \scriptscriptfont\bffam=\fivebf
  \def\bf{\fam\bffam\eightbf}%
  \textfont\ttfam=\eighttt
  \def\tt{\fam\ttfam\eighttt}%
  \abovedisplayskip=9pt plus 3pt minus 9pt
  \belowdisplayskip=\abovedisplayskip
  \abovedisplayshortskip=0pt plus 3pt
  \belowdisplayshortskip=3pt plus 3pt 
  \smallskipamount=2pt plus 1pt minus 1pt
  \medskipamount=4pt plus 2pt minus 1pt
  \bigskipamount=9pt plus 3pt minus 3pt
  \normalbaselineskip=9pt
  \setbox\strutbox=\hbox{\vrule height7pt depth2pt width0pt}%
  \let\bigf@nt=\eightrm     \let\smallf@nt=\sixrm
  \normalbaselines\rm}

\tenpoint

\def\pc#1{\bigf@nt#1\smallf@nt}         \def\pd#1 {{\pc#1} }
% Conflit avec fplain (redefinition ?)
%\catcode`\;=\active
%\def;{\relax\ifhmode\ifdim\lastskip>\z@\unskip\fi
%\kern\fontdimen2 \font\kern -1.2 \fontdimen3 \font\fi\string;}

%\catcode`\:=\active
%\def:{\relax\ifhmode\ifdim\lastskip>\z@\unskip\fi\penalty\@M\
%\fi\string:}

%\catcode`\!=\active
%\def!{\relax\ifhmode\ifdim\lastskip>\z@
%\unskip\fi\kern\fontdimen2 \font \kern -1.1 \fontdimen3 \font\fi\string!}

%\catcode`\?=\active
%\def?{\relax\ifhmode\ifdim\lastskip>\z@
%\unskip\fi\kern\fontdimen2 \font \kern -1.1 \fontdimen3 \font\fi\string?}

\def\^#1{\if#1i{\accent"5E\i}\else{\accent"5E #1}\fi}
\def\"#1{\if#1i{\accent"7F\i}\else{\accent"7F #1}\fi}

\frenchspacing

% QQQQQQQQQQQQQQQQ Le format de sortie QQQQQQQQQQQQQQQQQQQQQQQQQQQQ
% Haut et bas de page 

\newtoks\auteurcourant      \auteurcourant={\hfil}
\newtoks\titrecourant       \titrecourant={\hfil}

\newtoks\hautpagetitre      \hautpagetitre={\hfil}
\newtoks\baspagetitre       \baspagetitre={\hfil}

\newtoks\hautpagegauche     
\hautpagegauche={\eightpoint\rlap{\folio}\hfil\the\auteurcourant\hfil}
\newtoks\hautpagedroite     
\hautpagedroite={\eightpoint\hfil\the\titrecourant\hfil\llap{\folio}}

\newtoks\baspagegauche      \baspagegauche={\hfil} 
\newtoks\baspagedroite      \baspagedroite={\hfil}

\newif\ifpagetitre          \pagetitretrue  

\def\nopagenumbers{\def\folio{\hfil}}  

\headline={\ifpagetitre\the\hautpagetitre
\else\ifodd\pageno\the\hautpagedroite\else\the\hautpagegauche\fi\fi}

\footline={\ifpagetitre\the\baspagetitre\else
\ifodd\pageno\the\baspagedroite\else\the\baspagegauche\fi\fi
\global\pagetitrefalse}

\def\raggedbottom{\topskip 10pt plus 36pt\r@ggedbottomtrue}


\def\pointir{\unskip . --- \ignorespaces}

\def\Bigbreak{\ifdim\lastskip<12pt\vskip-\lastskip\bigbreak\fi}
\def\Medbreak{\ifdim\lastskip<6pt\vskip-\lastskip\bigbreak\fi}

% Texte centre dans une boite : le resultat est le plus petit rectangle
% qui contient le texte. Ce resultat est
% place dans une boite centree.
% La syntaxe est celle d'un tableau \`a une colonne

\def\ctexte#1\endctexte{%
  \hbox{$\vcenter{\halign{\hfill##\hfill\crcr#1\crcr}}$}}

% Titres centres (en gras)

\long\def\ctitre#1\endctitre{%
    \ifdim\lastskip<24pt\vskip-\lastskip\bigbreak\bigbreak\fi
  		\vbox{\parindent=0pt\leftskip=0pt plus 1fill
          \rightskip=\leftskip
          \parfillskip=0pt\bf#1\par}
    \bigskip\nobreak}

\long\def\section#1\endsection{%
\vskip 0pt plus 3\normalbaselineskip
\penalty-250
\vskip 0pt plus -3\normalbaselineskip
\Bigbreak
\message{[section \string: #1]}{\bf#1\unskip}\pointir}

\long\def\sectiona#1\endsection{%
\vskip 0pt plus 3\normalbaselineskip
\penalty-250
\vskip 0pt plus -3\normalbaselineskip
\Bigbreak
\message{[sectiona \string: #1]}{\bf#1}\nobreak\par}

\long\def\subsection#1\endsubsection{%
\Medbreak
{\it#1\unskip}\pointir}

\long\def\subsectiona#1\endsubsection{%
\Medbreak
{\it#1}\par\nobreak}

\def\rem#1\endrem{%
\Medbreak
{\it#1\unskip} : }

\def\rema#1\endrem{%
\Medbreak
{\it#1}\par\nobreak}

%QQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQ
% enonces de theoremes avec numerotation apres 
% #1 = THEOREME, COROLLAIRE, etc.
% #2 = numero (par exemple 3, 3.1, etc.)
% #3 = l'enonce du th proprememnt dit.

\long\def\th#1 #2\enonce#3\endth{%
   \Bigbreak
   {\pc#1} {#2\unskip}\pointir{\it #3}\medskip}

\long\def\tha#1 #2\enonce#3\endth{%
   \Bigbreak
   {\pc#1} {#2\unskip}\par\nobreak{\it #3}\medskip}

%QQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQ
% enonces de theoremes avec numerotation d'abord
% #1 = numero (par exemple 3, 3.1, etc.)
% #2 = THEOREME, COROLLAIRE, etc.
% #3 = l'enonce du th proprememnt dit.

\long\def\Th#1 #2 #3\enonce#4\endth{%
   \Bigbreak
   #1 {\pc#2} {#3\unskip}\pointir{\it #4}\medskip}

\long\def\Tha#1 #2 #3\enonce#4\endth{%
   \Bigbreak
   #1 {\pc#2} #3\par\nobreak{\it #4}\medskip}
%QQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQ

% les differents retraits, voir aussi \item

\def\decale#1{\smallbreak\hskip 28pt\llap{#1}\kern 5pt}
\def\decaledecale#1{\smallbreak\hskip 34pt\llap{#1}\kern 5pt}

\def\puce{\smallbreak\hskip 6pt{$\scriptstyle\bullet$}\kern 5pt}

% QQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQ
% QQQQQQQQQQQQQQ ce que Knuth n'a pas fait QQQQQQQQQQQQQQQQQQQQQQQQ
% QQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQ

% Un \displaylines qui numerote a droite.    	
% La syntaxe est la meme que celle de \eqalignno

\def\displaylinesno#1{\displ@y\halign{
\hbox to\displaywidth{$\@lign\hfil\displaystyle##\hfil$}&
\llap{$##$}\crcr#1\crcr}}

% Un \displaylines qui numerote a gauche.
% La syntaxe est la meme que celle de \leqalignno

\def\ldisplaylinesno#1{\displ@y\halign{ 
\hbox to\displaywidth{$\@lign\hfil\displaystyle##\hfil$}&
\kern-\displaywidth\rlap{$##$}\tabskip\displaywidth\crcr#1\crcr}}

% Un \eqalign qui accepte plusieurs alignements verticaux
% Motif : \hfil ** & ** \hfil & \hfil ** & ** \hfill, etc.

\def\eqalign#1{\null\,\vcenter{\openup\jot\m@th\ialign{
\strut\hfil$\displaystyle{##}$&$\displaystyle{{}##}$\hfil
&&\quad\strut\hfil$\displaystyle{##}$&$\displaystyle{{}##}$\hfil
\crcr#1\crcr}}\,}

% Systeme d'equations precede d'une accolade.
% Copi\'e sur \eqalign, on s'en sert comme une matrice
% syntaxe : signe & coef & inconnue
% les coef sont justifi\'es \`a droite (\hfil coef)
% et les inconnues \`a gauche (inconnue\hfil)
% attention : un seul & ou deux && avant le signe =
% selon la justification choisie !
% Exemple : $$\system{
%             &2 &x &- &3 & y & = &&  -5 \cr
%            -&  &x &+ &  & y & = &&   6 \cr
%           }$$

\def\system#1{\left\{\null\,\vcenter{\openup1\jot\m@th
\ialign{\strut$##$&\hfil$##$&$##$\hfil&&
        \enskip$##$\enskip&\hfil$##$&$##$\hfil\crcr#1\crcr}}\right.}

% pour avoir des messages raisonnables avec les lettres accentu\'ees

\let\@ldmessage=\message

\def\message#1{{\def\pc{\string\pc\space}%
                \def\'{\string'}\def\`{\string`}%
                \def\^{\string^}\def\"{\string"}%
                \@ldmessage{#1}}}


% QQQQQQQQQQQQQQQQQ Divers gadgets QQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQ

% Pour se rendre la vie facile : \up{er}, \up{i\`eme}, n\up{0}, etc.

\def\up#1{\raise 1ex\hbox{\smallf@nt#1}}

% Utilisation : \cf. \etc.

\def\cf{{\it cf}} \def\etc{{\it etc}}

\def\qed{\raise -2pt\hbox{\vrule\vbox to 10pt{\hrule width 4pt
                 \vfill\hrule}\vrule}}

\def\cqfd{\unskip\penalty 500\quad\qed\medbreak}

\def\virg{\raise .4ex\hbox{,}}   % virgule aprs une fraction

\def\pv{\ ;\enspace} % point-virgule de ponctuation en maths


% Entoure #2 d'un filet. Le filet est ecarte tout autour de #1
% Syntaxe \boxit{5pt}{...}. La ligne de base n'est pas perdue.

\def\boxit#1#2{%
\setbox1=\hbox{\kern#1{#2}\kern#1}%
\dimen1=\ht1 \advance\dimen1 by #1 \dimen2=\dp1 \advance\dimen2 by #1 
\setbox1=\hbox{\vrule height\dimen1 depth\dimen2\box1\vrule}%  
\setbox1=\vbox{\hrule\box1\hrule}%
\advance\dimen1 by .4pt \ht1=\dimen1 
\advance\dimen2 by .4pt \dp1=\dimen2  \box1\relax}
\catcode`\@=12

% pour qu'il la ferme
\showboxbreadth=-1  \showboxdepth=-1




\def\carrel#1#2#3{{\vcenter{\hrule height .#2pt
                       \hbox{\vrule height #1pt width .#2pt \kern #3pt
                             \vrule width .#2pt}
                       \hrule height .#2pt}}}                
\def\carre{\mathchoice\carrel54{5.4}\carrel54{5.4}
                      \carrel33{3.3}\carrel23{2.3}}


\def\hfl#1{{\buildrel{#1}\over
             {\hbox to 12mm{\rightarrowfill}}}}
\def\vfl#1{\llap{$\scriptstyle{#1}$}
\left\downarrow{\vbox to 6mm{}}\right.}

\def\tab#1|#2|{ {}_{#2}^{#1} }   % petits tableaux Young 2 lignes

\def\ttab#1|#2|#3|#4|{%                        % petits tableaux Young 4 lignes
\vbox{\hbox{$\tab#1|#2|$} \hbox{$\tab#3|#4|$} } }

\def\preuve{\noindent {\it Preuve} \pointir }
%%%%%%%%%%%%%%%%%%%%%%  fin du format  
\overfullrule 0 mm

\def\Def{\noindent{\it D\'efinition}\pointir }
\def\Rem{\noindent{\it Remarque}\pointir }
\def\Preuve{\noindent{\it Preuve}\pointir }
\def\Ex{\noindent{\it Exemple}\pointir }



\def\s{\scriptstyle }
\catcode`@=11
\def\smatrix#1{\,\baselineskip=2ex\vcenter{\m@th\ialign{\hfil
$\s\kern 2pt ##$\hfil&&\hfil$\s\kern 2pt
##$\hfil\crcr\mathstrut\crcr\noalign{\kern
1ex}#1\crcr\mathstrut\crcr\noalign{\kern 1ex}}}\,}

\font\smcpp=cmcsc8 
\headline={\ifnum\pageno>1 {\smcpp the electronic journal of combinatorics 3 (1996),
   \#R27\hfill\folio} \fi}  

\ctitre Treillis et bases des groupes de Coxeter
\endctitre

\smallskip
\centerline{Alain Lascoux\footnote{(*)}{Soutenu par le
PRC Math-Info et la bourse CEE n$^0$ ERBCHRXCT930400} et Marcel-Paul Sch\"utzenberger}


\vskip 3mm
\hfill{\it A Dominique Foata, }

\hfill{\it pionnier de la combinatoire}

\hfill{\it \`a qui elle doit tant}

\vskip 4mm 
\section 1. Introduction 
\endsection
Le pr\'esent travail est une contribution \`a l'\'etude de l'ordre fort
( dit aussi de Bruhat) dans un groupe de Coxeter fini $W$.

Les d\'efinitions et propri\'et\'es relatives aux treillis, aux 
ensembles ordonn\'es, aux {\it bases} et aux {\it treillis enveloppants}, \&c. 
sont rassembl\'ees de mani\`ere minimale dans la section 2, 
les preuves et quelques exemples \'etant pr\'esent\'es en annexe, \'egalement de 
fa\c{c}on minimale.

La {\it base} $B$ d'un ensemble ordonn\'e fini $(X,\, \leq)$ est le plus petit
sous-ensemble tel que la comparaison de deux \'el\'ements pour l'ordre
$\leq$ soit donn\'e par l'ordre d'inclusion des projections 
(dans $2^B$) de ces \'el\'ements sur la base.
La section 3 d\'ecrit les rapports entre les ordres faibles et fort sur les 
groupes de Coxeter, en les reliant \`a diverses alg\`ebres de Hecke d\'eg\'en\'er\'ees.
La base (pour l'ordre fort)  est contenue dans l'ensemble de ce que nous
appelons les {\it bigrassmanniennes} ( \'el\'ements $w\in W$ tels qu'il existe une 
seule paire de g\'en\'erateurs $\sigma$, $\sigma'$ tels que  
$\ell(\sigma\mu) < \ell(\mu)$,
$\ell(\mu\sigma')<\ell(\mu)$).

La section 4 d\'etaille le cas du groupe sym\'etrique, pour lequel l'ordre fort
a \'et\'e d\'ecrit par Ehresmann en termes d'objets combinatoires que
nous appelons {\it clefs}. La base est exactement l'ensemble des 
bigrassmanniennes. Ces derni\`eres d\'ependent de 4 param\`etres (en incluant
l'ordre $n$ du groupe), et leur nombre est ${n+1 \choose 3}$. 
Nous montrons que le treillis enveloppant est distributif, en
application d'un \'enonc\'e plus g\'en\'eral sur les propri\'et\'es de clivage des 
treillis enveloppants.

Dans la section suivante, nous identifions les \'el\'ements du treillis 
enveloppant \`a des objets combinatoires tr\`es int\'eressants, les 
{\it triangles}, qui ont d\'ej\`a \'et\'e rencontr\'es dans un autre 
contexte, celui des matrices alternantes.
Nous montrons que les permutations vexillaires se caract\'erisent de 
fa\c{c}on simple en terme de leur projection sur la base.

La section 6 utilise la m\^eme notion de clivage pour d\'ecouper de 
fa\c{c}on it\'er\'ee le groupe sym\'etrique en intervalles remarquables, 
isomorphes aux intervalles inf\'erieurs des bigrassmanniennes. 
Nous donnons les polyn\^omes de Poincar\'e de ces intervalles.

La section 7 \'etend les r\'esultats des sections 4 et 5 aux groupes de 
type $B_n$. Cette fois-ci, la base ne contient pas toutes les 
bigrassmanniennes, mais le treillis enveloppant reste distributif. Le
treillis de $B_n$ est en fait un sous-treillis du treillis enveloppant
de ${\goth{S}}(2n)$.

Les bases de tous les groupes de Coxeter 
finis viennent d'\^etre obtenues dans un article 
r\'ecent de M. Geck et S. Kim [G-Ki].

\vskip 4mm
\section 2. Treillis enveloppant \endsection
Renvoyant les preuves \`a une annexe, nous nous limitons ici \`a
\'enoncer les propri\'et\'es des treillis dont nous aurons besoin.
La plupart de celles ci sont bien connues et nous faisons r\'ef\'erence 
au grand trait\'e de G.Birkhoff [Bi]
( et sp\'ecialement aux chapitres III et IX )
pour une th\'eorie plus compl\`ete ainsi que pour les attributions de 
priorit\'e.

 Si  $(X,\leq)$ est un ensemble ordonn\'e et $x\in X $, nous notons $[x\leq]$
l'intervalle sup\'erieur $\{y\in X : x\leq y \}$ et sym\'etriquement,
$[\leq x] := \{ y\in X : y\leq x] \}$.
 L'{\it infimum} $\wedge Y = Inf(Y) $ d'une partie 
$Y$ de $X$ est l'unique \'el\'ement $x\in X$ tel que 
$$  [\leq x] =  \cap \{ [\leq y] : y\in Y \}  $$ 
s'il en existe un, et $\wedge Y = \emptyset$ 
sinon. Sym\'etriquement, le {\it supremum} $\vee Y = Sup(Y) $ 
est l'unique $x'\in X$ tel 
que $$ [x'\leq] =  \cap \{ [y\leq] : y\in Y \} $$ 
s'il en existe un, $\emptyset$ sinon.

\smallskip  Un ensemble ordonn\'e  $(X,\, \leq)$ est un 
treillis (sous-entendu {\it complet}) 
ssi toute partie $Y$ non vide admet un {\it Inf} ( 
et donc ausi un {\it Sup}, 
ainsi qu'on le voit facilement,  
en prenant le {\it Inf} de l'ensemble des $z$ tels que\hfill\break 
 $Y \subset [\leq z]$ ).

C'est un th\'eor\`eme classique d\^u \`a  Mac 
Neille  qu'il existe  un treillis minimal 
unique $(T,\, \leq)$ et un isomorphisme d'ordre $X\rightarrow T$  commutant 
avec les op\'erations $\wedge$ et $\vee$ quand leur valeur est un \'el\'ement 
de $X$. 

Ce treillis ($T,\, \subset$) est la plus petite famille de parties de
$X$ qui contienne $X$, tous les intervalles sup\'erieurs
$[x\leq]$, $x\in X$, et qui soit ferm\'ee par l'intersection ensembliste
$\cap$. L'injection naturelle $x\longrightarrow [x\leq]$ de ($X,\, \leq$) dans
($T,\, \subset$) fait donc correspondre \`a l'op\'eration 
{\it Sup} de ($X,\, \leq$) l'op\'eration $\cap$ de 
($2^X,\, \subset$) qui est l'op\'eration {\it Inf} de ($T,\, \subset$);
l'op\'eration {\it Inf } de ($X,\, \leq$) correspond quant \`a elle au
{\it Sup} de  ($T,\, \subset$), o\`u cette derni\`ere op\'eration est 
d\'efinie de fa\c{c}on indirecte, ainsi que nous l'avons indiqu\'e plus haut.

\smallskip
Nous appelerons $T$ le {\it treillis enveloppant de $(X, \leq) $} 
bien que l'usage soit d'appeler $T$ la  \lq\lq compl\'etion de $(X,\leq)$)", 
parce que cette construction,
qui ne fait appel \`a aucune hypoth\`ese de finitude,
constitue une g\'en\'eralisation naturelle de la 
construction de Dedekind  (correspondant elle-m\^eme au cas o\`u l'ordre sur 
$X$ est un ordre total). 

On sait que de fa\c con \'equivalente dans le cas 
fini, un treillis fini est un monoide 
{\it commutatif idempotent finiment engendr\'e }
(pour l'une quelconque des deux op\'erations),
la relation d'ordre et la seconde op\'eration \'etant alors canoniquement 
construites en terme de 
la premi\`ere op\'eration.

\smallskip  L'apport de la th\'eorie des treillis au pr\'esent travail
consiste essentiellement en les deux d\'efinitions suivantes 
et la proposition 2.5 :

\smallskip  \noindent{\it D\'efinition }2.1 \pointir   
Une  {\it relation basique } 
 est un relation ${\cal{R}}$ entre deux ensembles $\bar B$ et $B$ telle 
que, en consid\'erant ${\cal{R}}  \in \bar B \times B$ comme une matrice  
bool\'eenne, aucune ligne de ${\cal{R}}$ ne soit l'intersection de 
lignes, que la ligne compos\'ee enti\`erement de ${\bf 1}$ n'appartienne
pas \`a ${\cal{R}}$, et que les conditions sym\'etriques soient
 satisfaites par les colonnes de ${\cal{R}}$.

\setbox2=\hbox{( resp. }
\smallskip  \noindent{\it D\'efinition} 2.2 \pointir 
La {\it base} $B $ (resp. la {\it cobase} $\bar B$ ) de $(X, \leq)$ 
est l'ensemble des $x \in X\setminus\wedge X $ (resp. $x\in 
X\setminus \vee X$)  tels que  $x$ ne puisse \^etre obtenu comme le
$Sup$ (resp. le $Inf$) d'autres \'el\'ements, c'est-\`a-dire 
$x\in B$ (resp. $x\in\bar B$) si pour toute partie $Y$,
$$ x\notin Y \, \Rightarrow \, x\neq  Sup(Y) \ \box2 x\neq Inf(Y)\, )\ .$$

\smallskip   
Nous supposerons d\'esormais que tous les ensembles consid\'er\'es 
 sont finis.

\smallskip   Nous utiliserons la 
caract\'erisation suivante de la base, qui permet le calcul de cette 
derni\`ere par simple inspection des triples d'\'el\'ements de $X$, 
puisque l'assertion que $x$ est minimal  dans $X\setminus [\leq z]$ pour un 
$z \notin [x\leq]$ \'equivaut \`a  
 $[<x]\setminus [\leq z] = \emptyset$.

\th LEMME 2.3 
\enonce Un \'el\'ement $x \not = \wedge X$ appartient \`a la 
base $B$ ssi il est un \'el\'ement minimal de $X\setminus [\leq z]$ pour au 
moins un $z\in X$.

Dans le cas particulier o\`u  ($X, \leq$) est un treillis, on a 
que $x\in B$ ssi $x$ couvre un et un seul \'el\'ement de $X$,
c'est-\`a-dire ssi $x$ est un $\vee$-g\'en\'erateur.
\endth

\smallskip  
La base satisfait de plus une propri\'et\'e de minimalit\'e :

\th PROPOSITION 2.4 
\enonce  La projection  $\beta \, 
 : X\ni x\rightarrow B \cap [\leq x]\in \, (2^B, \subset) $ est un 
isomorphisme d'ordre et l'on a $B \subset C$ pour  toute partie $C$ de $X$ 
ayant la m\^eme propri\'et\'e.
\endth
Ceci permet de coder chaque \'el\'ement  $x$ 
 par l'ensemble des \'elements maximaux de $x\, \beta$, c'est 
\`a dire par ce que nous appelerons ses {\it rectrices}. 

On a de m\^eme la projection $\bar \beta$ de chaque \'el\'ement de 
$X$ sur la cobase.

\smallskip
Soit ${\cal{R}}'\subset \bar B \times B$  la relation d\'efinie par 
$(\bar b,b) \in {\cal{R}}'$
ssi $\bar b \geq b$, c'est-\`a-dire, de fa\c{c}on \'equivalente, ssi
$b\in\bar b\beta$ ou $\bar b \in b\bar \beta$.

\th PROPOSITION 2.5
\enonce  La relation ${\cal{R}}'$ est une relation basique.
\endth

Nous appelerons d\'esormais la relation ${\cal{R}}'$ pr\'ec\'edente
la {\it relation basique} de l'ensemble ordonn\'e ($X,\, \leq$).


\smallskip
\th TH\'EOR\`EME 2.6
\enonce  
 Chaque ensemble ordonn\'e a m\^eme relation basique que son treillis 
enveloppant.
\endth

\smallskip
Nous introduisons encore la 
\smallskip  \noindent{\it D\'efinition} 2.7 \pointir La paire 
d'\'el\'ements $(\bar x,\, x)$ de 
l'ensemble ordonn\'e $(X, \leq)$ {\it clive }$X$ 
ssi $X$ est l'union disjointe de $[\leq \bar x]$ et $[x\leq]$. 

\smallskip  Les clivages de $X$ sont en bijection avec ceux de son 
treilis enveloppant, et les paires clivantes  $(\bar x,\, x)$sont 
n\'ecessairement des \'el\'ements de $\bar  B\times B$, ce qui permet 
d'\'enoncer   un r\'esultat classique de Birkhoff 
sous la forme modifi\'ee suivante:

\th TH\'EOR\`EME 2.8 
\enonce Une condition n\'ecessaire et 
suffisante pour que le treillis enveloppant d'un ensemble ordonn\'e 
$(X,\, \leq)$ soit distributif est qu'il existe un
isomorphisme d'ordre bijectif entre  sa base 
et sa cobase tel  que chaque paire d'\'el\'ements associ\'es 
donne un clivage.
\endth

\smallskip
Comme il est bien connu, il y a bijection, pour un treillis 
distributif, entre les anticha\^\i nes de la restriction de la relation d'ordre 
\`a la base et les \'el\'ements du treillis: c'est un cas particulier de  la 
correspondance  entre les \'el\'ements et leurs rectrices.





\vskip 5mm
\vskip 5mm
\section 3. Ordres sur les groupes de Coxeter et alg\`ebres 
de Iwahori-Hecke d\'eg\'en\'er\'ees\endsection
Soit $(W,S)$ un groupe de Coxeter fini, 
$S$ un syst\`eme de g\'en\'erateurs. L'alg\`ebre d' Iwahori-Hecke 
${\cal{H}}(W,\, p,\, q)$ est 
l'alg\`ebre engendr\'ee par des \'el\'ements $T_s$ v\'erifiant 
les relations de Coxeter, plus les relations de Hecke (homog\'en\'eis\'ees)
$$T^2_s = (p+q) T_s -pq \ ,$$
o\`u $p,q$ sont deux constantes commutant avec les $T_s$. 
Pour le  groupe sym\'etrique, nous nous sommes attach\'es \`a 
d\'evelopper les cas $T^2_s = 0$ (diff\'erences divis\'ees), 
$T^2_s = T_s$ (diff\'erences divis\'ees isobares), 
$T^2_s = -T_s$, sans oublier l'alg\`ebre du groupe
( $T_s^2 = 1$) , cf. [L-S 1], [L-S 2], et 
aussi [Ch] pour ce qui concerne les alg\`ebres de Hecke affines.

\smallskip
Employons des notations diff\'erentes pour distinguer les quatre cas
sp\'eciaux ci-dessus (pour les valeurs des param\`etres $p,q $ respectivement
\'egales \`a  $(0,0) $, $(0,1) $, $(0,-1) $ et $(1,-1) $ ): 
$$ \partial_s \, , \ \pi_s \, ,\ \bar \pi_s \, , \ s $$
v\'erifiant respectivement
$$ \partial_s^2 = 0 \, , \ \pi_s^2 = \pi_s \, ,\ \bar \pi_s^2 
= -\bar \pi_s \, , \ s^2 = 1 \ . $$

Pour chacune de ces alg\`ebres, nous consid\'ererons aussi le monoide
engendr\'e par les g\'en\'erateurs $T_i$.

L'alg\`ebre d' Iwahori-Hecke admet une base lin\'eaire 
$\{T_w \}_{w\in W}$, 
en bijection avec les \'el\'ements du groupe, 
 que nous noterons respectivement 
$\{\partial_w \}$, $\{\pi_w \}$, $\{\bar \pi_w \}$ et $\{w \}$ 
dans les cas sp\'eciaux, l'alg\`ebre \'etant elle-m\^eme
${\cal{H}}^\partial$, ${\cal{H}}^\pi$, ${\cal{H}}^{\bar \pi}$ et 
${\cal{H}}^s$ respectivement.

Les $\partial_w$ permettent de d\'efinir 
la  {\it longueur} des \'el\'ements de $W$, 
les {\it d\'ecompositions r\'eduites} et 
l'ordre {\it faible} droit 
ou gauche sur $W$.


\smallskip\noindent{\it D\'efinitions}\pointir 
Etant donn\'e $w\in W $, la longueur maximum d'une factorisation dans 
le monoide des $\partial_i$: 
$\partial_w = \partial^1 \partial^2 \cdots \partial^k$ 
(en facteurs $\neq1$) 
 est dite {\it longueur} de $w$
et not\'ee $\ell(w)$. Une factorisation de longueur maximum
est telle que les facteurs $\partial^1, \ldots, \partial^k$ sont des g\'en\'erateurs.
La factorisation correspondante dans $W$ : 
$w = s^1\cdots s^k$ est une {\it d\'ecomposition r\'eduite} 
de $w$.

Deux \'el\'ements sont comparables pour l'ordre {\it faible} droit :
$v \leq_R w $ ssi $\partial_v$ est facteur gauche de $\partial_w$,
i.e. s'il existe  $u\in W$  tel que
$$ \partial_v \, \partial_u  = \partial_w \ .$$
Sym\'etriquement, 
$v \leq_L w $ ssi $\partial_v$ est facteur droit de $\partial_w$.



Etant donn\'es deux \'el\'ements $w,w'$ de $W$, il existe 
un plus petit $v\in W$ (pour l'ordre droit) tel que $\partial_v$ ait pour facteur
gauche $\partial_w$ et $\partial_{w'}$.  En d'autres termes,
l'intersection des id\'eaux $\partial_w {\cal{H}}^\partial$ et 
$\partial_{w'} {\cal{H}}^\partial$ 
est un id\'eal principal ( = $\partial_v {\cal{H}}^\partial$ ). 

Similairement, il existe un plus grand facteur gauche $\partial_v $ 
de $\partial_w$ et $\partial_{w'}$. 

L'existence d'un plus grand facteur gauche et d'un plus petit 
commun multiple signifie que $W$, muni de l'ordre 
$<_R$, est un treillis. 
Cette propri\'et\'e a \'et\'e montr\'e par Guilbaud \& Rosensthiel [G-R]
pour le groupe sym\'etrique, et est due \`a Bj\"orner pour 
les autres groupes de Coxeter finis [Bj].

Sym\'etriquement, l'ordre faible gauche donne une deuxi\`eme structure de
treillis, image de la pr\'ec\'edente par inversion des permutations.

A chacune des deux structures de treillis correspond une base.

\smallskip\noindent{\it D\'efinitions}\pointir 
Pour $w\in W$, l'ensemble des {\it descentes} (resp {\it reculs}) 
de $w$ est 
le sous-ensemble des g\'en\'erateurs de $W$ tels que 
$\partial_w \partial_s = 0$ (resp. $\partial_s \partial_w = 0$). 
Un \'el\'ement est dit {\it grassmannien} s'il n'a qu'une 
descente.
Une {\it bigrassmannienne} est  un \'el\'ement de $W$ ayant
une seule descente et un seul recul.

La base de $W$, muni de l'ordre $<_R$, est constitu\'ee des 
\'el\'ements grassmanniens, puisque ceux-ci sont exactement les
$w\in W$ ayant un et un seul successeur.

Soit $s$ un g\'en\'erateur du groupe de Coxeter $(W, {\cal{S}})$. 
Le sous-ensemble des \'el\'ements grassmanniens ayant $s$ pour descente,
auquel on adjoint l'identit\'e, est un treillis pour 
l'ordre $<_L$ (cf. [B-W]). Cet ensemble est usuellement not\'e 
$W^s$; ses \'el\'ements sont les repr\'esentants de longueur minimum
des classes $W\, /\,  W({\cal{S}}\backslash s)$, o\`u $W({\cal{S}}\backslash s)$ est le
parabolique engendr\'e par tous les g\'en\'erateurs sauf $s$.

Le morphisme $p_s : W \rightarrow W^s$ qui \`a chaque \'el\'ement de $W$
associe l'\'el\'ement de longueur minimum de sa classe modulo
$W({\cal{S}}\setminus s)$ est d\'efini par 
\setbox2=\hbox{ est le plus grand facteur gauche de }
$$p_s(w)=g \ \Leftrightarrow\ \partial_g\box2 w,\,  g\in W^s $$

Il est \'equivalent de rechercher les d\'ecompositions 
$\partial_w = \partial_g\, \partial_v$, $v\in W({\cal{S}}\setminus s)$, telles que 
$\partial_v$ soit de longueur maximale parmi les facteurs droits 
de $\partial_w$ appartenant \`a $W({\cal{S}}\setminus s)$.


\smallskip
On peut aussi munir $W$ du plus petit ordre ( {\it ordre bifaible} ) 
 contenant $<_L$ et $<_R$ et \'etudier les propri\'et\'es des 
{\it facteurs} des $\partial_w$.

\smallskip La consid\'eration des {\it sous-mots} conduit, quant \`a elle,  \`a 
d\'efinir un ordre dit {\it fort} ou {\it de Bruhat} que nous noterons
d\'esormais $\leq $ .

\smallskip\noindent{\it D\'efinitions}\pointir 
 On a a $v\leq w$ ssi $\partial_v$ est un sous-mot de $\partial_w$,
i.e. s'il existe deux factorisations 
$$\partial_v= \partial_{v_1} \, \partial_{v_2} \cdots \partial_{v_k}
\quad\hbox{\rm et}\quad
\partial_w = \partial_{w'} \, \partial_{v_1}\, \partial_{w''}\, 
\partial_{v_2}\,\partial_{w'''} \cdots \partial_{v_k}\, 
\partial_{w''''}   .$$

\smallskip
Il suffit en fait de ne consid\'erer que les sous-mots
d'une seule d\'ecomposi\-tion r\'eduite arbitraire de $w$
pour obtenir tous les \'el\'ements $v\leq w$ (cf. [Bo]).

\smallskip  Les id\'eaux d'ordre pour l'ordre fort se d\'ecrivent
ais\'ement dans l'alg\`ebre ${\cal{H}}^{\bar \pi}$. On a en effet la 
r\'ecurrence suivante ([Vr]):

\th LEMME 3.1 
\enonce Soient $w\in W$, $s\in{\cal{S}}$, tels que $\ell(w)<\ell(ws)$.
Alors l'intervalle inf\'erieur $[\leq w]$ se d\'ecompose en deux sous-ensembles 
$\{v : v<w, vs<w \}$ et $\{u: u\leq w, us\not <w \}$,
et l'intervalle $[\leq ws]$ est \'egal \`a 
$$[\leq w] \cup \{us: u\leq w, us \not < w \}\quad .$$
\endth

\th COROLLAIRE 3.2 
\enonce Pour tout $w$, 
$$\pi_w = \sum_{v\leq w}\, \bar \pi_v$$
et 
$$\bar\pi_w = \sum_{v\leq w}\,  (-1)^{\ell(w)-\ell(v)}  \,  \pi_v \quad .$$
\endth

En effet, soient $v$ et $s$ tels que $\ell(v)<\ell(vs)$.
Alors $(\bar \pi_v + \bar \pi_{vs}) \pi_s = \bar \pi_v + \bar \pi_{vs}$,
$\bar \pi_v \pi_s = \bar \pi_v + \bar \pi_{vs}$;
$(\pi_{vs} - \pi_v) \bar \pi_s = -\pi_{vs} + \pi_v$, 
$\pi_v \bar \pi_s = \pi_{vs} - \pi_v$  \quad \qed

\smallskip
Ce corollaire est utilis\'e de mani\`ere essentielle 
par Fokko du Cloux [Fo] pour impl\'ementer l'ordre fort sur les 
groupes de Coxeter.


\smallskip L'ordre fort peut s'obtenir \`a partir de la restriction
de l'ordre aux sous-ensembles $W^s,\,  s\in{\cal{S}}$, ainsi que l'\'etablit
le lemme suivant d\^u \`a Deodhar [De], qui g\'en\'eralise la d\'efinition
g\'eom\'etrique de l'ordre fort donn\'ee par Ehresmann [Eh] pour le groupe
sym\'etrique.

\th LEMME 3.3 
\enonce Soient $v,w \in W$. Alors $w\geq v$ ssi pour tout
$s\in{\cal{S}}$, $p_s(w) \geq p_s(v)$.
\endth

Comme les morphismes $p_s$ sont des morphismes d'ordre,
on peut \'ecrire la propri\'et\'e pr\'ec\'edente 
$$  w\geq v \ \Leftrightarrow \ \forall s\in{\cal{S}}, \ w\geq p_s(v) \leqno (3.4)$$

Plus sym\'etriquement en la droite et la gauche, soient 
deux g\'en\'erateurs $r,s \in{\cal{S}}$ et ${}^rW^s$ l'ensemble
des bigrassmanniennes ayant recul $r$, descente $s$,
ensemble auquel on adjoint l'identit\'e.  Cet ensemble est 
form\'e des \'el\'ements minimaux des classes 
$W({\cal{S}}\backslash  r) \setminus  W \, /\, W({\cal{S}}\backslash  s)$.

On dispose d'une projection $p_{r,s} : W \rightarrow {}^rW^s$ 
telle que 
$$p_{r,s}(w) = g \, 
\Leftrightarrow \, \partial_w= \partial_{w'}\partial_g\partial_{w''}\ ,$$
o\`u $\partial_g$ est un facteur de $\partial_w$ de plus grande longueur parmi
les $g \in {}^rW^s$.

L'unicit\'e d'un tel facteur provient de ce que les deux projections
$W\rightarrow W\, /\, ({\cal{S}}\backslash  s)$ et 
$W\rightarrow W({\cal{S}}\backslash  r)\setminus  W$ commutent.

La propri\'et\'e (3.4) implique
$$w\geq v \, \Leftrightarrow\, 
\forall r, \forall s\in{\cal{S}},\  w\geq p_{r,s}(v) \ . \leqno (3.5)$$

A tout \'el\'ement $w\in W$, on associe l'\'el\'ement 
$$p_{\cal{G}}(w) := \{g\in{\cal{G}},\,  g\leq w \} \subseteq 2^{\cal{G}} \ ,$$ 
o\`u ${\cal{G}}$ est l'ensemble des bigrassmanniennes.

\smallskip
\th TH\'EOR\'EME 3.6 
\enonce  Soit $(W,\, {\cal{S}})$ un groupe de Coxeter fini. Alors la base
$B$ de $W$, en tant qu'ensemble muni de l'ordre fort, est contenue
dans l'ensemble ${\cal{G}}$ des bigrassmanniennes.

Une bigrassmannienne $b$ ayant recul $r\,$ et descente $s$ 
appartient \`a la base ssi elle n'est pas le supremum d'un sous-ensemble
de bigrassamnniennes ($\neq b$) de m\^emes descente et recul.
\endth

\Preuve 
La propri\'et\'e (3.5) implique que $p_{\cal{G}}$ soit un morphisme d'ordre.
En outre $p_{\cal{G}}$ est injectif, car chaque \'el\'ement $w$ est 
d\'etermin\'e par l'ensemble des $p_{r,s}(w)\, , r,s\in{\cal{S}} $, qui est un 
sous-ensemble
de $p_{\cal{G}}(w)$. La caract\'erisation par minimalit\'e de la base 
donn\'ee en (2.4) implique que ${\cal{G}}$ contienne la base.

\smallskip
Les \'el\'ements de l'ensemble $W\setminus B$ sont les
\'el\'ements de $W$ dont l'ensemble des rectrices est de cardinal $\neq1$.
Soit $g$ une bigrassmanienne de descente $s$ et recul $r$, et
soit $\{b_1,\ldots, b_k \}$ l'ensemble de ses rectrices.
Supposons que $k>1$. Alors tous les $b_i$, $i=1\ldots k$, 
ont m\^emes descente et recul que $g $ . En effet, s'il existe
$i$ tel que $b_i$ ait descente $s'\neq s$, alors
$b_i>b_i s'$ et $w<ws'$. Soient $b_{k+1}, \ldots, b_h$ les rectrices
de $b_i s'$. La condition $w\geq b_i$ est \'equivalente \`a 
$w\geq b_i s'$, elle m\^eme \'equivalente \`a 
$w\geq b_{k+1}, \ldots , w\geq b_h$. L'\'el\'ement $w$ est donc
le supremum de l'ensemble
$\{b_1,\ldots, b_{i-1}, b_{i+1}, \ldots, b_h \}$, ce
qui est impossible puisque cet ensemble ne contient pas
la rectrice $b_i$.

R\'eciproquement, si une bigrassmannienne dans ${}^rW^s$ est
le supremum de $\{g_1, \ldots, g_k \} \subseteq {}^rW^s $, $k>1$, 
alors elle est le supremum de leurs rectrices qui appartiennent
toutes \`a ${}^rW^s$.
Ainsi donc une bigrassmannienne de descente $s$ et recul $r$
n'appartient pas \`a la base ssi elle est le
supremum d'un ensemble de cardinal $>1$ de bigrassmanniennes
dans ${}^rW^s$ deux \`a deux incomparables  \quad \qed

\smallskip 
Nous d\'etaillons par la suite les bases des groupes classiques
de type $A_n$ et $B_n$.



\vskip 5mm
\vskip 5mm
\section 4. Ehresmannoedre \endsection
L'ordre fort, dit aussi de Bruhat, sur le groupe sym\'etrique est 
usuellement d\'efini comme la cl\^oture transitive des relations de 
cons\'ecutivit\'e 
$$ \{\nu \rightarrow \mu\}  \ 
\Leftrightarrow \ \{\exists \tau : \mu=\nu\tau \ ,\ \ell(\mu)=\ell(\nu)+1\} \ , $$
o\`u $\nu,\mu$ sont deux permutations et $\tau$ une transposition, 
plut\^ot que par sous-mots des d\'ecompositions r\'eduites comme au
paragraphe 2.

Le groupe sym\'etrique, muni de cet ordre, est dit
{\it Ehresmannoedre}. Nous allons voir que sa base consiste en l'ensemble
des bigrassmanniennes.
La base est donc exactement l'intersection des
bases pour les ordres faibles droit et gauche.

La d\'efinition originelle d'Ehresmann [Eh] de l'ordre sur le groupe sym\'etrique 
repose quant \`a elle sur la comparaison des ensembles.


Deux sous-ensembles $A$ et $B$ d'un ensemble totalement ordonn\'e 
sont {\it comparables} : 
$A \leq B$\  ssi il existe un morphisme injectif de $A$ dans $B$.  
Une suite d'ensembles  se repr\'esente 
planairement par une suite de colonnes d\'ecroissantes 
justifi\'ee par le haut, ces colonnes  \'etant 
les ensembles r\'eordonn\'es composant la suite. 
La suite d'ensembles est une {\it  cha\^\i ne} (i.e. est croissante) si l'objet 
planaire est un {\it contretableau}, i.e. si les colonnes sont de longueurs
croissantes, et si toutes les lignes sont croissantes de gauche \`a droite.

Etant donn\'es deux contretableaux $t$ et $t'$ 
de m\^eme forme, on dit que 
$t \leq t'$ ssi chaque composante de $t$ est inf\'erieure \`a la composante de
$t'$ situ\'eee au m\^eme endroit. On notera que la restriction de l'ordre au 
sous-ensemble des colonnes co\"\i ncide bien avec l'ordre sur les ensembles 
sous-jacents.

Les  facteurs gauches successifs d'une permutation  $\mu $ sont 
une suite d' ensembles embo\^\i t\'es (un {\it drapeau} ).
Le contretableau  associ\'e  est dit  $ clef(\mu)$.

Ainsi $\mu = 2413$ a pour clef 
$$\matrix{ 
2 &4 &4 &4 \cr & 2 &2 &3\cr && 1 &2\cr &&&1\cr }$$

Le lemme suivant montre que l'ordre fort co\"\i ncide avec la
comparaison des clefs, qui est la d\'efinition choisie par Ehresmann.

\th LEMME 4.1 
\enonce $\mu\leq\nu$ \ ssi\ $clef(\mu) \leq clef(\nu)$  \endth

\smallskip
Chaque colonne de la clef d'une permutation d\'etermine une permutation
grassmannienne. Ansi la clef de $\mu=2413$ correspond-elle \`a la
suite des grassmanniennes $2\, 143$, $24 \, 13$, $124\, 3$, $1234$.
La comparaison de deux clefs correspond donc \`a la comparaison 
de grassmanniennes ayant m\^eme descentes. C'est aussi la 
comparaison des partitions obtenues en soustrayant $1,2\ldots$ aux
colonnes de la clef.

De mani\`ere sym\'etrique, la comparaison des inverses des permutations peut se 
d\'ecrire en coupant l'alphabet $\{1,\ldots, n \} $ en deux intervalles.
Soit en effet $\{x <y \}$ un alphabet \`a deux lettres, et
$p_h$ la projection de ${\goth{S}}(n)$ 
(consid\'er\'e comme un ensemble de mots en $1,\ldots,n$) 
 sur le mono\"\i de $\{x,y \}^*$ induite par le morphisme 
$$ i\rightarrow x \ {\rm si}\ i\leq h\ ,\ i\rightarrow y \ {\rm si}\ i>h \ .$$

L'ordre sur les mots en $\{x,y \}$ se d\'efinit en comparant les  
degr\'es en $y$ des facteurs gauches respectifs de m\^eme longueur des
deux mots :
$$ v\leq w \ {\rm si}\ \{v=v'v'',\, w=w'w'',\, |v'|=|w'| \}
\Rightarrow |v'|_y = |w'|_y   \ . $$

On a alors
\th LEMME 4.2 
\enonce $\mu\leq\nu$ ssi pour tout $h$, tout $k$,
$$|\,  p_h(\mu_1\cdots \mu_k)\, |_y 
\leq |\, p_h( \nu_1\cdots \nu_k\, |_y  \ .$$  \endth

Ainsi $2143 \leq4132$, car, \'ecrivant $\{1\ldots i | i+1\ldots n \} $
pour la projection $1,\ldots, i \, \rightarrow x$, 
$i+1,\ldots , n\, \rightarrow y$, on a :\hfill\break 
pour $\{1\, |\, 234 \}$,\  $yxyy\leq yxyy$;
pour $\{12\, |\, 34 \}$,\ $xxyy \leq yxyx$;
pour $\{123\, |\, 4 \}$,\ $xxyx \leq yxxx$.

Le lemme 4.2 n'est autre que l'explicitation des projections
$p_{hk}$ (vues en 3.5) de ${\goth{S}}(n)$ sur l'ensemble des \'el\'ements de 
longueur minimum des classes 
${\goth{S}}(h)\times{\goth{S}}(n-h)
\setminus {\goth{S}}(n) \, /\, {\goth{S}}(k)\times{\goth{S}}(n-k)$.

On peut maintenant r\'etablir la sym\'etrie (pour l'inversion des
permutations) de l'Ehresmannoedre, qu'avait mise \`a mal 
la comparaison des clefs de $\mu$ et $\nu$.

Voyons tout d'abord la comparaison d'une permutation et d'une 
bigrassmannienne. Comme une bigrassmannienne $b $ de 
${\goth{S}}(n)$ est une permutation qui a pour code un rectangle
$0^{r_0} r_2^{r_1} 0^{r_3}$, avec $r_0 +r_1 +r_2+r_3 =n$,
$r_1\geq1$, $r_2 \geq1$, on la d\'esignera plut\^ot par le symbole 
$b = [r_0,r_1,r_2,r_3]$. Alors

\th LEMME 4.3 
\enonce  Une permutation $\mu$ est sup\'erieure \`a une bigrassmannienne
$b=[r_0,r_1,r_2,r_3]$ 
ssi il y a au moins $r_1$ valeurs $>r_0+r_2$ dans le facteur gauche 
de longueur $r_0+r_1$ de $\mu$.
\endth

\noindent
{\it Preuve}\pointir On utilise le crit\`ere 4.2. Pour la coupure de 
l'alphabet $\{1\cdots r_0+r_2 \, |\, r_0+r_2+1\cdots n  \}$, le mot
$x^{r_0} y^{r_1} x^{r_2}y^{r_3} =p_{r_0+r_2}(b)$ 
est clairement le minimum 
des $p_{r_0+r_2}(\mu)$, pour $\mu \geq b$.   \cqfd

\smallskip 

On peut tout autant optimiser la n\'egation $NEG$ de la condition 
$\mu\geq b$ ( nous prions le lecteur de se reporter \`a la derni\`ere partie
de l'annexe o\`u est trait\'ee la notion de clivage).
En effet, le mot $y^{r_1-1}  x^{r_0+1} y^{r_3+1} x^{r_2-1}$ est le maximum 
des $p_{r_0+r_2} (\zeta)$, $\zeta \not\geq b$, et a pour maximum dans sa fibre
la permutation

\noindent
$c_{[r_0 r_1 r_2 r_3]} =\hfill\break
\hfill  n\cdots (n-r_1+2) 
(r_0+r_2)\cdots r_2 (r_0+r_2+r_3+1)\cdots (r_0+r_2+1) (r_2-1) \cdots 1    
$.

\smallskip
Ainsi donc les bigrasmanniennes constituent la
base de l'Ehresmann\-oe\-dre, car \`a chaque bigrassmannienne $b$
correspond bijectivement une cobigrassmannienne qui est le {\it Sup} 
du compl\'ementaire  de l'intervalle sup\'erieur $[b\, \leq]$.
 En d'autres termes, on a le th\'eor\`eme suivant.

\vskip 3mm
\th TH\'EOR\`EME 4.4 
\enonce  
Le treillis enveloppant du groupe sym\'etrique est 
distributif et a pour g\'en\'erateur les bigrassmanniennes.

Plus pr\'ecis\'ement, 
soit $[r_0, r_1,r_2,r_3] \in {\bb{N}}^4$, $r_1,r_2\geq1$,
$r_0+r_1+r_2+r_3 =n$.  Alors le groupe sym\'etrique 
${\goth{S}}(n)$ clive en les deux intervalles $[b\, \leq]$ et $[\leq c]$, 
o\`u $b$ et $c$ sont les bigrassmannienne et cobigrassmannienne
cod\'ees par $[r_0, r_1,r_2,r_3]$.

Une permutation $\mu$ appartient \`a l'un ou l'autre de ces deux intervalles 
selon que la composante de sa clef  de coordonn\'ees 
 $r_0+r_1, r_1$  ( pour les axes 
${\downarrow}^{\rightarrow}$) 
est strictement sup\'erieure \`a $r_0+r_2$ ou non.
\endth

\smallskip
Pour ${\goth{S}}(4)$, l'ensemble $B$ des bigrassmanniennes est :
$$\{ 2134, 1324, 1243, 1342, 1423, 2314, 3124, 2341, 4123, 3412 \}$$
La restriction de la relation d'incidence \`a
${\goth{S}}(4) \times B$, dont les lignes sont les projections par $\beta$ des \'el\'ements
sur la base $B$ est repr\'esent\'ee par la matrice:

$$\smatrix
{ 4321  &:\    &1 &1 &1 &1 &1 &1 &1 &1 &1 &1 \cr 
4312  &:\    &1 &1 &1 &0 &1 &1 &1 &1 &1 &1 \cr 
4231  &:\    &1 &0 &1 &1 &1 &1 &1 &1 &1 &1 \cr 
4213  &:\    &1 &0 &1 &0 &1 &1 &1 &0 &1 &1 \cr 
4132  &:\    &1 &0 &1 &0 &0 &1 &1 &1 &1 &1 \cr 
4123  &:\    &1 &0 &1 &0 &0 &1 &1 &0 &1 &1 \cr 
3421  &:\    &0 &1 &1 &1 &1 &1 &1 &1 &1 &1 \cr 
3412  &:\    &0 &1 &1 &0 &1 &1 &1 &1 &1 &1 \cr 
3241  &:\    &0 &0 &1 &1 &1 &1 &0 &1 &1 &1 \cr 
3214  &:\    &0 &0 &1 &0 &1 &1 &0 &0 &1 &0 \cr 
3142  &:\    &0 &0 &1 &0 &0 &1 &0 &1 &1 &1 \cr 
3124  &:\    &0 &0 &1 &0 &0 &1 &0 &0 &1 &0 \cr 
2431  &:\   &0 &0 &0 &1 &1 &1 &1 &1 &1 &1 \cr 
2413  &:\    &0 &0 &0 &0 &1 &1 &1 &0 &1 &1 \cr 
2341  &:\    &0 &0 &0 &1 &1 &1 &0 &1 &1 &1 \cr 
2314  &:\    &0 &0 &0 &0 &1 &1 &0 &0 &1 &0 \cr 
2143  &:\    &0 &0 &0 &0 &0 &1 &0 &0 &0 &1 \cr 
2134  &:\    &0 &0 &0 &0 &0 &1 &0 &0 &0 &0 \cr 
1432  &:\    &0 &0 &0 &0 &0 &0 &1 &1 &1 &1 \cr 
1423  &:\    &0 &0 &0 &0 &0 &0 &1 &0 &1 &1 \cr 
1342  &:\    &0 &0 &0 &0 &0 &0 &0 &1 &1 &1 \cr 
1324  &:\    &0 &0 &0 &0 &0 &0 &0 &0 &1 &0 \cr 
1243  &:\    &0 &0 &0 &0 &0 &0 &0 &0 &0 &1 \cr 
1234  &:\    &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 \cr }$$


Enfin, les dix clivages correspondant aux bigrassmanniennes sont :


$$\eqalign{
{\goth{S}}(4) &=\    [2134\leq]\, \cup\, [\leq1432] &=\ [1324\leq]\, \cup\, [\leq2143] 
     &=\ [1243\leq]\, \cup\, [\leq3214] \cr
&=\    [1342\leq]\, \cup\, [\leq4213] &=\ [1423\leq]\, \cup\, [\leq3241] 
     &=\ [2314\leq]\, \cup\, [\leq4132] \cr
&=\    [3124\leq]\, \cup\, [\leq2431] &=\ [2341\leq]\, \cup\, [\leq4312] 
     &=\ [4123\leq]\, \cup\, [\leq3421] \cr
& &=\ [3412\leq]\, \cup\, [\leq4231]      & \cr
}$$

Par ailleurs, les bigrassmanniennes \'etant cod\'ees bijectivement
par les vecteurs $[r_0,r_1,r_2,r_3] \in {\bb{N}}^4$, $r_1,r_2\geq1$, 
la fonction g\'en\'eratrice du nombre de bigrassmanniennes, pour
$n$ variable, est
$$\sum_{n\geq2}z^{n-2} card\bigl( Base({\goth{S}}(n))\bigr) \ =\, (1-z)^{-4}$$

\smallskip
L'image d'une permutation par la projection $p_{ij}$ vue en 3.5
est soit l'identit\'e, soit une bigrassmannienne $b$ ayant 
recul $i$ et descente $j$ (i.e. $b$ a le sous-mot 
$i$+1$\ldots i$ et $b_j> b_{j+1}$). En outre, si
$b$ est une bigrassmannienne de recul $i$ et descente $j$, 
alors $b\leq\mu\, \Rightarrow\, b\leq p_{ij}(\mu)$.  
Les rectrices d'une permutation
$\mu$ sont donc les \'el\'ements maximaux de l'ensemble 
$\{p_{ij}(\mu) \}_{1\leq i,j\leq n-1}$. Il existe un algorithme pour d\'eterminer 
ces rectrices, sans calculer l'ensemble pr\'ec\'edent, qui repose sur
le lemme suivant:

\th LEMME 4.5
\enonce Il y a bijection entre les rectrices d'une permutation
$\mu$ et les triples d'entiers $i\leq j<j+1\leq k$ tels que
$$\mu_{j+1} \leq\mu_k <\mu_i= 1+\mu_k \leq\mu_j\ .$$
A un tel triple correspond la rectrice 
$b=[r_0,r_1,r_2,r_3]$, o\`u \hfill\break 
$r_0 = card \{h<j\, : \mu_h<\mu_k \}$, $r_1=j-r_0$, $r_2=\mu_k-r_0$.
\endth

Nous laissons au lecteur le soin de v\'erifier que la bigrassmannienne
associ\'ee au couple : descente $(\mu_j>\mu_{j+1})$, recul $(\mu_k+1\ldots \mu_k)$
est bien maximale sous les hypoth\`eses du lemme 4.5.

\setbox2=\hbox{\sevenrm places}
\setbox3=\hbox{\sevenrm nord}
\setbox4=\hbox{\sevenrm ouest}
\setbox5=\hbox{\sevenrm est}
Graphiquement, une rectrice $b$ correspond \`a une configuration

$$\matrix{
&         &       &      &     &\box3 &     &       &     \cr
&\vdots    & \vdots &\vdots &\vdots  &\vdots &\vdots &\vdots  &\vdots \cr
&\cdot    & \cdot &\cdot &\mu_j  &\cdot &\cdot &\cdot  &\cdot \cr
&\vdots    & \vdots &\vdots &\vdots  &\vdots &\vdots &\vdots  &\vdots \cr
&\cdot   &\mu_i &\cdot &\cdot  &\cdot &\cdot &\cdot  &\cdot \cr
\box4 &\cdot    & \cdot &\cdot &b  &\cdot &\cdot &\mu_k  &\cdot &\box5 \cr
&\vdots    & \vdots &\vdots &\vdots  &\vdots &\vdots &\vdots  &\vdots \cr
&\cdot   & \cdot &\cdot &\cdot  &\mu_{j+1} &\cdot &\cdot  &\cdot \cr
&\vdots    & \vdots &\vdots &\vdots  &\vdots &\vdots &\vdots  &\vdots \cr\cr
\box2 &\cdot & i &\cdot &j  &j+1 &\cdot &k  &\cdot \cr
}$$
pour les axes de coordonn\'ees cart\'esiens $\uparrow_{\rightarrow}$,
le couple ($\mu_k,j$) \'etant dit les {\it coordonn\'ees} de la rectrice.

Outre l'ordre de Bruhat, on peut lire certaines propri\'et\'es des permutations
sur l'ensemble de leurs rectrices. Par exemple, la proposition suivante
d\'ecrit l'appartenance \`a un sous-groupe de Young, sous des conditions que
l'on peut qualifier de {\it g\'eographiques} car elles ne font intervenir
que les coordonn\'ees $r_0+r_1$, $r_0+r_2$ des rectrices.

\th PROPOSITION 4.6
\enonce Soit $\mu$ une permutation, $R= R'\uplus R''$ une d\'ecomposition
de l'ensemble de ses rectrices ( $R',R''\neq\emptyset$). 

Soient $n_1,n_2$ deux entiers tels que

\setbox2=\hbox{ si }
\setbox3=\hbox{ sinon }
$$\eqalign{
r_0 +r_1 &\leq n_1 &\ \&\    &\ r_0+r_2 &\leq n_2  &\ \box2\ [r_0,r_1,r_2,r_3]\in R'  
\cr
&>n_1 &        &        &>n_2  &\ \box3  \cr
}$$

Alors il existe un entier $\, n_3$ tel que l'on ait les m\^emes relations
en rempla\c{c}ant  ($n_1,n_2$) par ($n_3,n_3$), et
$\mu$ appartient au sous-groupe  ${\goth{S}}(n_3) \times {\goth{S}}(n-n_3)$.
\endth

\Preuve Soient $n_4$ et $n_5$ les deux entiers :
$n_4 = Max\bigl( \{ \mu_j $ : il existe une rectrice de $\mu$ dans $R'$
avec $r_0+r_1=j\} \bigr)$  ; 
$n_5 = Max\bigl( \{ kj$:  il existe une rectrice de $\mu$ dans $R'$
avec $r_0+r_2=\mu_k\}\bigr)$ . 

Par maximalit\'e de $n_4=\mu_j$, on a $\mu_j>\mu_{j+1}$. D'apr\`es le lemme 4.5
et l'hypoth\`ese 4.6, on a $\mu_{j+1}<n_2$. Pour les m\^emes raisons, 
on a aussi $\mu_k>n_4$ pour tout $h>n_1$, ce qui entraine 
que les zones $\star$ ne contiennent pas de point ($i,\mu_i$):



$$\smatrix{
    &\star  &\star  &\star &\star  &\cdot&\cdot  &\cdot &\cdot   &\cdot \cr
    &\star  &\star  &\star &\star  &\cdot&\cdot  &\cdot &\cdot   &\cdot \cr
    &\star  &\star  &\star &\star  &\cdot&\cdot  &\cdot &\cdot   &\cdot \cr
n_4 &\cdot  &\cdot&\cdot &\cdot&\star &\star &\star &\star &\star \cr
n_2 &\cdot  &\cdot&\cdot &\cdot&\star &\star &\star &\star &\star \cr
    &\cdot &\cdot &\cdot&\cdot     &\cdot &\cdot&\cdot &\cdot &\cdot  \cr
    &\cdot &\cdot &\cdot&\cdot     &\cdot &\cdot&\cdot &\cdot &\cdot  \cr
    &\cdot &\cdot &\cdot&\cdot     &\cdot &\cdot&\cdot &\cdot &\cdot  \cr
    &\cdot &\cdot &\cdot&\cdot     &\cdot &\cdot&\cdot &\cdot &\cdot  \cr
    &      &      & j   &n_1&      &      &&&     \cr
}$$



Le m\^eme argument s'applique \`a $n_5$ gr\^ace \`a la sym\'etrie
$\mu \rightarrow\mu^{-1}$. Le domaine permis pour les points $(i,\mu_i)$
 est donc finalement (zone \lq\lq $\cdot$") :


$$\smatrix{
    &\star  &\star  &\star &\star  &\star&\star  &\star &\cdot   &\cdot \cr
    &\star  &\star  &\star &\star  &\star&\star  &\star &\cdot   &\cdot \cr
    &\star  &\star  &\star &\star  &\star&\star  &\star &\cdot   &\cdot \cr
n_4 &\cdot  &\cdot&\cdot &\cdot&\star &\star &\star &\star &\star \cr
n_2 &\cdot  &\cdot&\cdot &\cdot&\star &\star &\star &\star &\star \cr
    &\cdot &\cdot &\cdot&\cdot     &\cdot &\cdot&\cdot &\star &\star  \cr
    &\cdot &\cdot &\cdot&\cdot     &\cdot &\cdot&\cdot &\star &\star  \cr
    &\cdot &\cdot &\cdot&\cdot     &\cdot &\cdot&\cdot &\star &\star  \cr
    &\cdot &\cdot &\cdot&\cdot     &\cdot &\cdot&\cdot &\star &\star  \cr
    &      &      & j   &n_1&      &      &n_5&&     \cr
}$$


Ceci montre que $n_3 = Max(n_4,n_5)$ satisfait l'\'enonc\'e 4.6, et que
$i\leq n_3 \ \Rightarrow\ \mu_i\leq n_3$  \quad\qed







\vskip 5mm
\def\s{\scriptstyle } 
\catcode`@=11
\def\smatrix#1{\,\baselineskip=2ex\vcenter{\m@th\ialign{\hfil
$\s\kern 2pt ##$\hfil&&\hfil$\s\kern 2pt 
##$\hfil\crcr\mathstrut\crcr\noalign{\kern 
1ex}#1\crcr\mathstrut\crcr\noalign{\kern 1ex}}}\,}


\setbox2=\hbox{ssi}
\section 5. Triangles \endsection
On peut identifier chaque permutation $\mu$ \`a sa  clef $K(\mu) $. 
La comparaison d'une permutation $\mu$ et d'une bigrassmannienne
$b=[r0,r_1,r_2,r_3]$ se r\'eduit \`a tester une seule composante de 
$K(\mu)$, d'apr\`es le th\'eor\`eme 4.4 :
$$\mu\geq b \ \box2 \ K(\mu)_{r0+r1,r_1} \, > r_0+r_2 \ . \leqno (5.1) $$

Le {\it Sup} ou l' {\it Inf}, dans le treillis enveloppant,  
 d'une famille $\{\mu \}$ de permutations se calcule ais\'ement, \'etant le {\it 
Sup} ou l'{\it Inf} composante \`a composante des  $\{K(\mu) \}$.

Plus pr\'ecis\'ement, un contretableau $t$ de forme $12\cdots n$ est le
sup de la famille $\{\mu \}$ ssi
$$\forall i,j:\, 1\leq i\leq j\leq n,\ t_{ij} = Sup_\mu\{K(\mu)_{ij} \}\ .$$

Il est ais\'e de contr\^oler qu'un tel contre-tableau v\'erifie,
pour chaque sous-triangle \'el\'ementaire $\bigl($ i.e. triple de composantes
adjacentes de coordonn\'ees respectives $(i,j)$, $(i,j+1)$ et
$(i+1,j+1)$ pour les axes ${\downarrow}^{\rightarrow} \bigr)$
les in\'egalit\'es suivantes 

$$  {}^{yz}_{\ x} \ \Rightarrow \{x<z \ 
\&\ x\leq y \ \& \ y\leq z \}  \ . \leqno (5.2) $$

R\'eciproquement, tout contre-tableau de forme $12\cdots n$
v\'erifiant les conditions 5.2 ( que l'on appelera {\it triangle}) 
est le {\it Sup} de la famille de bigrassmanniennes d\'etermin\'ee 
par chacune de ses composantes :
$$ t_{ij}\ \rightarrow\ b=[ j-i,\,  i,\,  t_{ij}+i-j-1,\,  n-t_{ij}-i+1]\leqno (5.3)$$

On a donc

\th LEMME 5.4
\enonce Le treillis enveloppant du groupe sym\'etrique ${\goth{S}}(n)$ est isomorphe
au treillis des triangles de forme $12\cdots n$, remplis avec des lettres
dans $\{1,2,\ldots , n \}$.
\endth

\smallskip
D'apr\`es les travaux de Mills, Robbins \& Rumsey [MRR] les triangles
(qu'ils appellent  {\it triangles monotones})  sont
en bijection avec les {\it matrices alternantes}, dont le cardinal, 
pour l'ordre $n$, est 
$$\prod_0^{n-1}  (3k+1)!\, /\, (n+k)! $$

Cette formule, qu'ils conjecturaient, a depuis \'et\'e prouv\'ee.

\smallskip
Pour ${\goth{S}}(3)$, le treillis enveloppant comprend un seul \'el\'ement qui n'est pas 
une permutation : c'est le {\it Sup}
 de $213 \leftrightarrow {}^{22}_{\  1}$
 et $132 \leftrightarrow {}^{13}_{\  1}$, ainsi que l'{\it Inf}
de $231 \leftrightarrow {}^{23}_{\  2}$ et 
$312 \leftrightarrow {}^{33}_{\  1}$. 
C'est donc $ {}^{23}_{\  1}$ qui correspond \`a la seule matrice alternante
d'ordre trois qui ne soit pas une permutation :
$\smatrix{0&1&0\cr  1&-1&1 \cr  0&1&0\cr }$.

\smallskip
Le treillis enveloppant de ${\goth{S}}(4)$ est constitu\'e de 42 triangles, dont nous
\'enum\'erons les 18 qui ne sont pas des clefs:

\vskip 3mm
\qquad $\smatrix{& 2& 3& 3\cr& & 1& 2\cr& & & 1\cr }$\ 
$\smatrix{& 1& 3& 4\cr& & 1& 2\cr& & & 1\cr }$\ 
$\smatrix{& 2& 3& 4\cr& & 1& 2\cr& & & 1\cr }$\ 
$\smatrix{& 2& 3& 4\cr& & 2& 2\cr& & & 1\cr }$\ 
$\smatrix{& 3& 3& 4\cr& & 1& 2\cr& & & 1\cr }$\ 
$\smatrix{& 2& 3& 4\cr& & 1& 3\cr& & & 1\cr }$\ 
$\smatrix{& 3& 3& 4\cr& & 2& 2\cr& & & 1\cr }$\ 
$\smatrix{& 2& 3& 4\cr& & 2& 3\cr& & & 1\cr }$\ 
$\smatrix{& 3& 3& 4\cr& & 2& 3\cr& & & 1\cr }$\ 

\qquad $\smatrix{& 2& 4& 4\cr& & 1& 2\cr& & & 1\cr }$\ 
$\smatrix{& 3& 4& 4\cr& & 1& 2\cr& & & 1\cr }$\ 
$\smatrix{& 2& 4& 4\cr& & 1& 3\cr& & & 1\cr }$\ 
$\smatrix{& 3& 4& 4\cr& & 2& 2\cr& & & 1\cr }$\ 
$\smatrix{& 2& 4& 4\cr& & 2& 3\cr& & & 1\cr }$\ 
$\smatrix{& 3& 4& 4\cr& & 1& 3\cr& & & 1\cr }$\ 
$\smatrix{& 3& 4& 4\cr& & 2& 3\cr& & & 1\cr }$\ 
$\smatrix{& 3& 4& 4\cr& & 2& 3\cr& & & 2\cr }$\ 
$\smatrix{& 4& 4& 4\cr& & 2& 3\cr& & & 1\cr }$\ 


\smallskip

L'application 5.3 d\'ecrit, pour un contre-tableau $t$, 
 une famille de bigrassmanniennes dont $t$ est le {\it Sup}. Les \'el\'ements
maximaux de cet ensemble de bigrassmanniennes, c'est-\`a-dire les 
{\it rectrices} du triangle, correspondent bijectivement 
aux composantes $t_{ij}$ telles que l'image de $t$ par 
$t_{ij} \rightarrow t_{ij}-1$ soit encore un triangle.

Ces composantes seront appel\'ees 
 {\it points essentiels} du triangle;
un triangle est donc le {\it Sup} des bigrassmanniennes correspondant
\`a ses points essentiels et tout ensemble de composantes dont le triangle
est le {\it Sup} contient les points essentiels. 
Dans le cas o\`u $t$ est la clef d'une 
permutation $\mu$, les points essentiels ont 
\'et\'e d\'efinis par Fulton [Fu] ( en terme de la fonction de rang de la matrice
repr\'esentant la permutation). 

Un triangle sera dit {\it vexillaire} ssi l'ensemble de ses points essentiels
${\cal{E}}$ v\'erifie la condition suivante 
(qui est g\'eographique au sens donn\'e plus haut \`a ce terme):

$$\forall (i,j)\in {\cal{E}} \ 
\Rightarrow\ \{(i',j'):\, i'\leq i,\, j'>j \} \cap {\cal{E}} = \emptyset \ . \leqno 
(5.5) $$
En d'autres termes, il n'y a pas de point essentiel dans le cadran nord-est
d'un point essentiel (le domaine d'exclusion comprend le demi axe-est).

Dans le cas d'une permutation vexillaire $\mu$,
 cette d\'efinition, appliqu\'ee \`a la clef de $\mu$,
correspond \`a l'une des nombreuses caract\'erisations des permutations
vexillaires (cf. [Fu]).



\vskip 5mm
\section 6. Pav\'es \endsection
On a remarqu\'e que le clivage associ\'e \`a une transposition simple 
$\sigma$ induit le clivage de tout intervalle $[\leq \mu]$. 
Cet id\'eal se d\'ecompose en un id\'eal $[\leq\nu]$ (o\`u $\nu$ est la 
permutation maximum $\nu\leq\mu$ dont aucune d\'ecomposition r\'eduite 
ne contient $\sigma$) et son compl\'ementaire $[\leq\mu] \cap [\sigma\leq]$.

Nous donnons dans ce paragraphe une d\'ecomposition du groupe sym\'etrique 
transversale au clivage pr\'ec\'edent.

Pour ce faire, consid\'erons l'alg\`ebre des diff\'erences divis\'ees isobares.

A tout ensemble ${\cal{J}} \subset \{1,\ldots , n-1 \}$ correspond 
le groupe parabolique ${\cal{P}}_{\cal{J}}$ engendr\'e par les transpositions 
simples $\{\sigma_i | i\in\{1\ldots n-1 \} \setminus {\cal{J}} \}$, 
ainsi que la projection $p_{\cal{J}}$ 
du monoide engendr\'e par les 
$ \pi_i \, , i\in\{1\ldots n-1 \}$ sur le monoide engendr\'e par les  
$ \pi_i\, , i \notin {\cal{J}} $
d\'etermin\'ee par $\pi_j \rightarrow 1$ pour tous les $j\in{\cal{J}}$.

Cette projection est clairement compatible aux relations de Coxeter,
ainsi qu'aux relations $\pi_i^2=\pi_i$ et donc l'image des 
$\pi_\mu$ est bien d\'efinie.

\smallskip 
\Def  Soit $k$ un entier, $1\leq k\leq n-1$. Un $k$-{\it pav\'e} est une 
classe d'\'equivalence pour la relation 
$$ \mu \sim_k \nu \ \Leftrightarrow \ p_k(\pi_\mu) = p_k(\pi_\nu) \ .$$

Deux permutations $\mu,\nu$ appartiennent au m\^eme $k$-pav\'e ssi, 
pour deux d\'ecompositions r\'eduites quelconques
$\mu= \sigma_i \sigma_j \cdots \sigma_h$ et $\nu= \sigma_l\cdots \sigma_m$, on a
$$p_k( \pi_i \pi_j \cdots \mu_h) =  p_k( \pi_l \cdots \pi_m)\ .$$

Par exemple, le groupe ${\goth{S}}(4)$ se d\'ecompose en six 1-pav\'es :

\noindent
$[1432,4321], [1342,3241], [1423,4213], [1324,3214] ,
[1243,2143], [1234,2134]$, 
qui sont des intervalles bool\'eens
de cardinaux respectifs 8,4,4,4,2,2 .

\smallskip
Des pav\'es plus g\'en\'eraux apparaissent pour $k \neq1, n-1$.

\smallskip
\Def  Soit $\mu$ une permutation et $k\leq n-1$. Les places 
$k$-{\it saillantes gauches } de $\mu$ sont les indices 
$1\leq i\leq k $ pour lesquels $\mu_i = max(\{\mu_i,\ldots , \mu_k \} )$; les 
places 
$k$-{\it saillantes droites } de $\mu$ sont les indices 
$k<j\leq n$ pour lesquels $ \mu_j = min(\{\mu_{k+1},\ldots , \mu_j \} )$.

\th PROPOSITION 6.1 
\enonce  Soit $k$ un entier $\leq n-1$, $\nu$ une permutation dans
${\cal{P}}_k = {\goth{S}}(k)\times {\goth{S}}(n-k)$. 
Soit $\zeta$ la permutation obtenue \`a partir de 
$\nu$ en permutant circulairement les points saillants de $\nu$ de sorte
\`a en faire une suite d\'ecroissante.  

Alors le $k$-pav\'e contenant $\nu$ 
est \'egal \`a l'intervalle $[\nu,\zeta]$ et est isomorphe \`a l'id\'eal de la 
bigrassmannienne $[0,r,p,0]$ de ${\goth{S}}(p+r)$, o\`u $p$ est le nombre de points 
saillants gauches de $\nu$, $r$ le nombre de points saillants droits.

Une permutation $\mu$ appartient au pav\'e de $\nu$ ssi 
$ \zeta_i = \nu_i \Rightarrow \mu_i = \nu_i  $ et l'image de $\mu$ par la projection 
de ${\goth{S}}(n)$ sur ${\goth{S}}(p+r)$ qui consiste en l'effacement des valeurs 
communes \`a $\nu$ et $\zeta$, est sup\'erieure (pour l'ordre de Bruhat) \`a
l'image de $\nu$.
\endth

Ainsi, pour $k=5$ et $$\matrix{
\nu & = &{\bf 5 } &3 &{\bf 4 } &1 &{\bf 2 } &{\bf 11 }
&{\bf 9 } &12 &{\bf 7 } &8 &{\bf 6 } &10 \cr
places & & 1 &2 &3 &4 &5 &6 &7 &8 &9 &10 &11 &12 \cr
}$$
( les point saillants sont en gras) , le maximum du pav\'e est 
$$\matrix{ \quad\zeta &= &{\bf 11 } &3 &{\bf 9 } &1 &{\bf 7} &{\bf 6 }&{\bf 5 }
&12 &{\bf 4 } &8 &{\bf 2 } &10 \cr} \ . $$
Une permutation $\mu $ appartient au pav\'e ssi 
$ \mu_2=3$, $\mu_4=1$, $\mu_8=12$, $\mu_{12}=10$ et 
$(\mu_1, \mu_3, \mu_5, \mu_6, \mu_7, \mu_9, \mu_{11}) 
\geq(5,4,2,11,9,7,6)  $.

\smallskip
\Preuve    La permutation $\nu$ est le produit direct des deux 
permutations $\nu' = \nu_1\ldots \nu_k\, k+1\ldots n$ et
$\nu''= 1\ldots k\, \nu_{k+1}\ldots \nu_n$.  Une permutation 
$\mu$ est dans la fibre de $\nu$ ssi 
$p_{k\ldots n-1}(\mu) = \nu'$ et $p_{1\ldots k}(\mu) = \nu''$.
Or le code de $p_{k\ldots n-1}(\mu)$ est l'inf du code 
de $\mu$ et du vecteur $[k-1,\ldots , 1,0,\ldots, 0]$, ainsi 
qu'on le voit en consid\'erant le d\'ecomposition r\'eduite 
de $\mu$ associ\'ee au code 
(i.e. le code consid\'er\'e est le vecteur 
$[ inf(c_1,k-1), \ldots, inf(c_k,0), \ldots, 0]$, 
o\`u $[c_1,\ldots , c_n]$ est le code de $\mu$ ).

Il s'ensuit que la condition n\'ecessaire et suffisante que 
$\mu$ soit dans la fibre de $\nu$ est que 

\puce l'inf du code de $\mu$ et $[k-1\ldots 0\ldots 0]$ est \'egal au code
de $\nu'$
\puce l'inf du code de $\omega\mu\omega$ et $[n-k-1\ldots 0\ldots 0]$ 
est \'egal au code de $\omega\nu'' \omega$.
\smallskip
Il n'est pas difficile de v\'erifier que $\zeta$ satisfait \`a ces deux conditions.

Comme les morphismes de sp\'ecialisation $p_{\cal{J}}$ sont des morphismes d'ordre
(i.e. $\mu\leq\eta \Rightarrow p_{\cal{J}}(\mu) \leq p_{\cal{J}}(\eta) )$,  
on en d\'eduit que l'intervalle 
$[\nu,\zeta]$ est contenu tout entier dans une seule fibre.

Nous \'epargnerons au lecteur la v\'erification que toute permutation 
appartient \`a un et un seul de ces intervalles.

Par ailleurs, l'intervalle $[\nu,\zeta]$ a pour image dans ${\goth{S}}(p+r)$, apr\`es 
effacement des points fixes et retour \`a l'alphabet $\{1,2,\ldots , p+r \}$
l'intervalle $[(p\ldots 1)\, , \, (p+r\ldots p+1)]$. 
L'image de cet intervalle, par 
 multiplication \`a gauche par $\omega$, est l'intervalle
$[(1\ldots p)\, , \, (p+1\ldots p+r) ]$ qui n'est autre que 
l'intervalle inf\'erieur de la bigrassmannienne $[0,r,p,0]$ \quad \qed


\vskip 3mm
L'\'enum\'eration des pav\'es isomorphes \`a l'id\'eal de la bigrassmannienne
$[0,r,p,0]$ ( disons de {\it type} $[0,r,p,0]$ ) 
est donn\'e par le lemme suivant, en d\'esignant par 
$\Lambda^i(k)$ le nombre de Stirling \'egal \`a la $i-$\`eme fonction \'el\'ementaire 
des entiers $0,1,\ldots , k-1$.

\th LEMME 6.2 
\enonce Le nombre de $k-$pav\'es de type $[0,r,p,0]$ est 
\'egal au produit des nombres de Stirling 
$\Lambda^{k-p}(k) \, \Lambda^{n-k-r}(n-k)$
\endth

\Preuve Soit $n(k,r,p)$ le nombre de pav\'es de type $[0,r,p,0]$. 
La projection "effacement de la lettre 1" :
$${\goth{S}}(n) \ni \mu \rightarrow \mu\backslash 1 \in {\goth{S}}(n-1)$$
donne une r\'ecurrence sur le nombre de pav\'es.

En effet, soit $\nu$ le minimum d'un $k-$pav\'e. Si $\nu_k=1$, alors 
le pav\'e est de type $[0,r,p,0]$ ssi le pav\'e contenant 
$\nu\backslash 1$ est de type $[0,r,p-1,0]$. 

Si $\nu_k \neq1$, l'effacement de 1 donne un pav\'e isomorphe. Comme il y a 
$k-1$ permutations $\mu$ qui se projettent sur $\nu\backslash 1$, et telles 
que $\nu_k \neq1$, on a  la r\'ecurrence 
$n(k,r,p) = (k-1) n(k-1,r,p) + n(k-1,r,p-1) $ \qed 

\smallskip 
\Ex  Les fibres de la projection 
$p_3 :{\goth{S}}(7)\rightarrow {\goth{S}}(3)\times {\goth{S}}(4)$ 
sont les bigrassmanniennes suivantes. On regroupe 
les pav\'es de type 
$[0,r,p,0]$ et $[0,p,r,0]$ qui sont isomorphes, et on \'ecrit 
$\Lambda^{ij}$ pour $\Lambda^i(3) \Lambda^j(4)$ :

\smallskip

\setbox2=\hbox{
$\matrix{
[p,r] & [11] & [12] & [13] &[14] &[22] & [23] & [24] & [33] &[34]  \cr
card & 12 &40 &18 &2 &33  & 29 & 3 &6 &1 \cr
= & \Lambda^{23}& \Lambda^{22}+ \Lambda^{13} 
& \Lambda^{21}+ \Lambda^{03} & \Lambda^{20} & \Lambda^{12}
& \Lambda^{02}+ \Lambda^{11} & \Lambda^{10} & \Lambda^{01} & \Lambda^{00} \cr  
}$}
\hskip -8mm\box2

\smallskip Molev [Mo] a utilis\'e une d\'ecomposition du groupe sym\'etrique
en intervalles bool\'eens pour d\'evelopper le d\'eterminant de
Sklyanin et d\'ecrire le centre de l'alg\`ebre enveloppante dans le
cas des groupes orthogonaux et symplectiques. Quoique le nombre des 
pav\'es soit encore un nombre de Stirling, cette d\'ecomposition 
est diff\'erente de celle que nous venons d'exposer.

\smallskip
Ayant d\'ecompos\'e le groupe sym\'etrique en pav\'es, il nous reste \`a d\'ecrire 
ceux-ci en tant qu'intervalles pour l'ordre de Bruhat. Nous nous contenterons
de donner la fonction g\'en\'eratrice du nombre d'\'el\'ements dans l'intervalle,
class\'es par nombre d'inversions, autrement dit 
le {\it Polyn\^ome de Poincar\'e} de l'intervalle.

Soit une bigrassmannienne $b= [0,r,p,0]$. Notons $G(r,p)$ le polyn\^ome de
Poincar\'e $:= \sum_{\mu\leq b} z^{\ell(\mu)}$ de $b$.


Nous voulons  d\'ecrire l'intervalle inf\'erieur de $b$.
 Celle derni\`ere a une d\'ecomposition r\'eduite canonique
que l'on peut \'ecrire planairement dans un rectangle
(lisant par colonnes, de gauche \`a droite):
$$\matrix{
\sigma_p & \sigma_{p+1} & \cdots & \sigma_{p+r-1} \cr
\vdots &\vdots &  &\vdots \cr
\sigma_1 & \sigma_2 &\cdots &\sigma_r \cr
}$$

Comme l'intervalle se calcule \`a l'aide de (3.2), c'est-\`a-dire de 
la d\'ecomposition des produits de $\pi_i$ dans la base des
$\bar \pi_\mu$, le 
polyn\^ome de Poincar\'e $G(r,p)$ est obtenu par r\'ecurrence \`a partir 
du lemme suivant.

\smallskip
\th LEMME 6.3
\enonce  Soient $p$ et $r$ deux entiers. Alors on a l'identit\'e

$$\matrix{
\pi_p & \pi_{p+1} & \cdots & \pi_{p+r-1}  &\cdot  \cr
\pi_{p-1 }& \pi_{p} & \cdots & \pi_{p+r-2}  & \bar \pi_{p+r-1}  \cr
\vdots &\vdots &  &\vdots &\vdots \cr
\pi_1 & \pi_2 &\cdots &\pi_r & \bar \pi_{r+1} \cr } 
= 
\matrix{
\bar \pi_{p-1} & \bar \pi_p & \cdots & \bar \pi_{p+r-1}   \cr
\vdots &\vdots &  &\vdots  \cr
\bar \pi_1 & \bar \pi_2 & \cdots & \bar \pi_{r+1} \cr
\cdot & \pi_1  &\cdots &\pi_r  \cr }
$$
\endth

\Preuve Ecrivons $i$ pour $\pi_i$, $i'$ pour $\bar \pi_i$. 
On a, pour deux entiers cons\'ecutifs quelconques,
$$434' = 43'4' = 3'4'3 \ , $$
et donc, pour deux lignes,
$$\matrix{2&3 &4 &\cdot \cr  
          1&2 &3 &4' \cr  \cr }
=\matrix{2 &3 \cr
1&2&3'&4'\cr &&& 3\cr   }
=\matrix{2\cr  1& 2' &3' &4'\cr  && 2 &3 \cr   }
=\matrix{\cr 1' &2' &3' &4'\cr   &1 &2 &3 \cr }
$$
Finalement, pour un nombre quelconque de lignes,
$$\matrix{ 3 &4 &5 &\cdot \cr 2 &3 &4 &5' \cr 1 &2 &3 &4' \cr }
= \matrix{ 2' &3' &4' &5' &\cdot \cr 
        \cdot &2 &3 &4  &\cdot \cr
       \cdot &1 &2 &3 &4' \cr  }    =
\matrix{ 2' &3' &4' &5' \cr
         1' &2' &3' &4' \cr
    \cdot  &1 &2 &3 \cr }    \ ,$$
ce qui est bien le lemme  \quad \qed

\smallskip
On intialise la r\'ecurrence sur les polyn\^omes de Poincar\'e 
en \'ecrivant que la derni\`ere colonne 
de l'expression planaire de $\pi_b$, disons 
$\pi_6 \pi_5 \pi_4 \pi_3$ est \'egale \`a 

$$\pi_6 \pi_5 \pi_4 \pi_3=  (1+ \overline{\pi_6})(1+ \overline{\pi_5})
(1+ \overline{\pi_4})(1+ \overline{\pi_3}) $$

Par application r\'ep\'et\'ee de 6.3, en regroupant les termes
et en 
 employant les notations des $\lambda$-anneaux ( les fonctions
$S^i(r+x)$ sont les coefficients de la s\'erie en $z$ 
$1/(1-zx)(1-z)^r$, i.e. \hfill\break
$1/(1-zx)(1-z)^r = S^0(r+x) + z S^1(r+x) + z^2 S^2(r+x) + \ldots $),
\hfill\break on obtient 

\smallskip
\th PROPOSITION 6.4 
\enonce Soient $r,p$ des entiers $\geq1$ et $Z=z^{r+1}$.  Alors

$G(r+1,p) = (S^{p-1}(1+z) +z^p) G(r,p) + Z S^{p-2}(2+z) G(r,p-1)
+ Z^2 S^{p-3}((3+z) G(r,p-2) + \cdots +
Z^{p-2} S^1(p-1+z) G(r,2) + Z^{p-1} S^0(r,1)   $
\endth

Le cas initial $G(r,1)$, c'est \`a dire de l'id\'eal d'un cycle $b=
(2,\ldots, r+1,1) $ est donn\'e par la sp\'ecialisation $\pi_i = 1+ z \, \forall i$.
En effet, $\pi_b = (1 + \overline{\pi_1}) \cdots
(1+\overline{\pi_r}) = \sum_{\mu\leq b} \overline{\pi_\mu}   $
est une expression dont le d\'eveloppement ne fait appara\^\i tre aucun carr\'e 
$\overline{\pi_i}^2$. 
Les \'el\'ements de l'intervalle $[\leq b]$ sont en correspondance bijective 
avec les sous-mots de la d\'ecomposition r\'eduite 
$ b= \sigma_1 \sigma_2\cdots \sigma_r$. Cet intervalle est bool\'een et l'on 
a  $G(r,1) = (1+z)^r$, ce qui r\'esulte aussi
du fait bien connu que l'id\'eal d'un cycle $b$ est un intervalle
bool\'een.

Comme exemple de la proposition, on a \hfill\break
$G(7,4) =  (1+z+z^2+z^3+z^4) G(6,4) +
z^7 (3+2z+z^2) G(6,3) +z^{14}(3+z) G(6,2) + z^{21}G(6,1)  
= 1 +10z+ 54 z^2 + 209z^3 + \ldots +
252 z^{26}  + 28z^{27} + z^{28} $ \hfill\break
est le polyn\^ome de Poincar\'e d'un pav\'e de cardinal 1315666 
de ${\goth{S}}(11)$ que nous nous dispenserons d'\'enum\'erer.

\smallskip 
Table des coefficients des $G(r,p)$, pour $4\geq r\geq p\geq2$

\setbox3=\hbox{
$\matrix{ &&&&&&&&&&&&&  &card \cr
G(2,2) & 1 &3 &5 &4 &1 &&&&&&&& & 14  \cr
G(3,2)& 1 &4 &9 &13 &12 &6 &1 &&&&&& &46 \cr
G(3,3) &1 &5 &14 &29 &45 &53 &46 &27 &9 &1  &&& &230 \cr
G(4,2) &1 &5 &14 &26 &35 &34 &22 &8 &1  &&&& &146    \cr
G(4,3) &1 &6 &20 &49 &95 &150 &195 &206 &173 &110 &48 &12 &1  &1066\cr
G(4,4) &1 &7 &27 &76 & 174 &337 &562 & 815 &1029 &1125 & 1052 &823 &521 \cr
       &  &  &   &   &     &    &    &     &   
                                                 &252  &84    &16  &1 &6902 
\cr }$}

\smallskip

\hskip -18mm \box3 



\vskip 5mm
\section 7. Groupe $B_n$  \endsection
Le goupe $B_n$ est engendr\'e par $n$ g\'en\'erateurs $s_1,\ldots, s_n$ qui 
satisfont aux m\^emes relations que les g\'en\'erateurs du groupe sym\'etrique,
mis \`a part le remplacement de $(s_1s_2)^3=1$ par 
$$ (s_1 s_2)^4 = 1$$

Chaque \'el\'ement peut \^etre d\'ecrit par sa d\'ecomposition r\'eduite 
lexicographiquement minimale (  $drlm$ ). Ecrivant $i$ pour $s_i$, celle-ci
est un sous-mot de la d\'ecomposition de l'\'el\'ement maximal :
$$(1)\, (212)\, (32123)\, \cdots (n  \ldots 212 \ldots n)$$
qui est form\'e de facteurs gauches de chacun des blocs indiqu\'es entre 
parenth\`eses.

On peut donc coder bijectivement un \'el\'ement de $B_n$ par la suite des 
longueurs des facteurs successifs de sa  $drlm$ ; les \'el\'ements de $B_n$ sont 
en bijection avec les vecteurs $c$ dans ${\bb{N}}^n$, $c \leq [1,3,5,\ldots , 2n+1]$
que nous appelerons {\it codes}.

Les \'el\'ements de $B_n$ peuvent aussi \^etre repr\'esent\'es par les permutations 
sign\'ees de $\{1,\ldots, n \}$, en interpr\'etant $s_1$ comme le morphisme
de ${\bb{Z}}^n$ : 
$$u = [u_1,\ldots, u_n] \rightarrow us_1 = [-u_1, u_2,\ldots , u_n]$$
et $s_i$, $i=2, \ldots , n$, comme la transposition simple
\'echangeant  les composantes  $u_{i-1}$ et $u_i$.

Une deuxi\`eme repr\'esentation est le plongement dans ${\goth{S}}(2n)$ d\'efini par
$$s_1 \rightarrow \sigma_n,\, s_2 \rightarrow \sigma_{n-1} \sigma_{n+1}, \, 
\ldots , s_n \rightarrow \sigma_1 \sigma_{2n-1}  \ , $$
o\`u les $\sigma_i$ sont les transpositions simples de ${\goth{S}}(2n)$.
L'image de $B_n$ est alors l'ensemble des permutations $\mu$ 
{\it palindromes}, i.e. telles que $\mu_i + \mu_{2n-i}= 2n+1$,
$i=1,\ldots ,n$.

Le passage du code \`a chacune de ces deux repr\'esentations est imm\'ediat
et correspond \`a compter les inversions. Ainsi le code
$[1,0,5,2]$ correspond \`a la d\'ecomposition r\'eduite
$(1)()(32123)(43)$, \`a 
 la permutation sign\'ee $[-1,4,2,-3]$ 
et au palindrome $73154862$. En effet, $c_4 =2$ indique la place de 4
(\`a partir de la droite) 
dans la permutation sign\'ee et la place de 8 dans le palindrome;
$c_3 =5$ donne la place de  -3 dans $[-1,2,-3]$, le signe - impliquant 
que l'on compte la place \`a partir de la gauche en ajoutant l'ordre (=3), 
ainsi que la place de 7 dans le palindrome $735462$.

On passe de la permutation sign\'eee au palindrome par duplication
et retour \`a l'alphabet $\{1,2,\ldots, 2n \}$ par translation de $n $:
$$[-1,4,2,-3] \rightarrow [3,-2,-4,1]\ , \quad [-1,4,2,-3] \sim \, 73154862 $$


\vskip 1cm
Le g\'en\'erateur $s_1$ joue un r\^ole particulier, ce qui conduit \`a distinguer  
deux types de facteurs $v$ d'une  $drlm$  :

\puce {\it colonne} si $s_1 \notin v$ (i.e. $v=s_k\cdots s_{k-i}$, $i<k-1 )$
\puce {\it \'equerre} sinon.
\smallskip

Le produit d'une colonne ou d'une \'equerre par un g\'en\'erateur $s_i$ est 
instantan\'e et permet ainsi de d'expliciter l'action, \`a gauche ou \`a droite, de 
$B_n$ sur les codes.

Soit un \'el\'ement de $B_n$ dont le code n'a que deux composantes non nulles.
Cet \'el\'ement n'est une bigrassmannienne que dans les seuls cas suivants:

(cc) $c_1=0 = c_{k-1}; c_k=c_{k+1}<k ; c_{k+2}=0 =\cdots =c_n$

(ee) $c_1=0 = c_{k-1}; =c_{k+1}= c_k +1\geq k+1 <k ; c_{k+2}=0 =\cdots =c_n$

(ec) $c_1=0 = c_{k-1}; c_k \geq k, c_{k+1}=2k+1-c_k ; c_{k+2}=0 =\cdots =c_n$

Les facteurs correspondants de la  $drlm$  sont respectivement
(colonne, colonne); (\'equerre, \'equerre); (\'equerre, colonne).

Par exemple, pour $k=5$, avec $i$ au lieu de $s_i$, les  $drlm$  suivantes
illustrent ces trois types :

(cc)  \ $ (543) \, (654)$

(ee) \ $(5432123)\, (65432123)$

(ec) \ $(5432123)\, (654)$

Par r\'ecurrence sur le nombre de facteurs, on en d\'eduit la caract\'erisation des 
codes des bigrassmanniennes de $B_n$ :

\th LEMME 7.1 
\enonce 
Un vecteur $c$ dans ${\bb{N}}^n$ est le code d'une bigrassmannienne 
de $B_n $ ssi

i) $c \leq[1,3,\ldots, 2n+1]$; ses composantes non nulles sont cons\'ecutives
et constituent une suite d'\'equerres suivie par une suite de colonnes
(l'une de ces deux suites peut \^etre vide)

ii) chaque paire de composantes adjacentes non nulles v\'erifie la condition
cc), ee) ou ec) indiqu\'ee par son type.
\endth

Par exemple, l'ensemble des codes des bigrassmanniennes de $B_3$ est

\smallskip\noindent
$\{  [0,3,4]; [1,2,3]; [0,0,5], [0,2,3], [1,2,2];
[0,0,4], [0,3,1], [0,2,2]; \break
[0,0,3], [0,3,0], [1,2,0], [1,1,1];
[0,0,2], [0,1,1], [0,2,0] , [1,1,0]; \break
[0,0,1], [0,1,0], [1,0,0]  \}$

\smallskip
Du lemme pr\'ec\'edent, on d\'eduit la fonction g\'en\'eratrice du nombre des 
bigrassmanniennes :

\th LEMME 7.2 
\enonce  La fonction $\sum^\infty_{n=1} z^{n-1} card(\{bigr(B_n) \})$
est \'egale \`a 
$$(1-z)^{-5} + z(1-z)^{-4} = 1+6z+19z^2 +45z^3 +90z^4+\ldots$$ 
\endth

Nous allons voir que l'ensemble des bigrassmanniennes contient strictement 
la base de $B_n$, pour $n\geq4$.

Comme l'ordre de Bruhat sur $B_n$ co\"\i ncide avec la restriction de l'ordre de 
Bruhat sur ${\goth{S}}(2n)$ au sous-ensemble des permutations palindromes
[Lak], [Pr], on peut 
d\'ecrire l'ordre de $B_n$ en utilisant les bigrassamnniennes de ${\goth{S}}(2n)$.

Tout d'abord, on remarque que pour les permutations palindromes

$$\mu \geq bigr[r_0, r_1, r_2, r_3] 
\Leftrightarrow \mu\geq bigr[r_3,r_2,r_1,r_0]   \ .$$

Appelons {\it couple miroir} un tel couple de bigrassmanniennes, invariant 
par le retournement $[r_0, r_1, r_2, r_3] \rightarrow [r_3,r_2,r_1,r_0]   $. 

En particulier, l'ensemble des rectrices d'une permutation palindrome est 
form\'e de couples miroirs dont il suffit de se donner un seul des deux 
\'el\'ements. 

\Def Les {\it} rectrices d'un \'el\'ement de $B_n$ sont les rectrices
$[r_0,r_1,r_2,r_3]$ de son image palindrome qui sont telles que
\hfill\break
$\{r_0 <r_3\}$ ou $\{r_0=r_3 \, \&\, r_1\leq r_2\}$.

Les \'el\'ements de $B_n$ sont d\'etermin\'es par leurs rectrices, puisque les 
\'el\'ements de ${\goth{S}}(2n)$ le sont. 
L'ordre de Bruhat sur les \'el\'ements de 
$B_n$ est induit par l'ordre sur les bigrassmanniennes de ${\goth{S}}(2n)$. 
Plus explicitement, tenant compte de ce que l'on n'a pris que la moiti\'e des 
rectrices des palindromes par raison de sym\'etrie, on a 

$$ [r_0, r_1,r_2,r_3] \leq_{B_n} [p_0,p_1,p_2,p_3]  $$
ssi
$$ [r_0, r_1,r_2,r_3] \leq_{{\goth{S}}(2n)} [p_0,p_1,p_2,p_3]
\ {\rm ou}\ 
 [r_0, r_1,r_2,r_3] \leq_{{\goth{S}}(2n)} [p_3,p_2,p_1,p_0]  $$

\smallskip 
\th LEMME 7.3 
\enonce   Soit $b=[r_0,r_1,r_2,r_3]$ une bigrassmannienne de
${\goth{S}}(2n)$.  Alors l'ensemble des permutations palindromes $\geq b$ 
admet un \'el\'ement inf\'erieur, not\'e $b_+$. Sym\'etriquement, l'ensemble des 
permutations palindromes inf\'erieures \`a une cobigrassmannienne $c$ de
${\goth{S}}(2n)$ a un supremum, not\'e $c_-$.

De plus l'\'el\'ement correspondant \`a $b_+$ (resp $c_-$) dans $B_n$
est une bigrassmannienne (resp. cobigrassmannienne).
\endth

\Preuve   On peut supposer que $b=[r_0,r_1,r_2,r_3]$ avec 
$r_0 <r_3$ ou $r_0=r_3\ \& \ r_1\leq r_2$. On a quatre cas possibles,
suivant que $r_0+r_1\leq n$ ou non, et $r_0+r_2\leq n$ ou non.

Prenons par exemple $r_0+r_1>n$ et $r_0+r_2 \leq n$. On cherche les palindromes 
tels que le facteur gauche de longueur $r_0+r_1$ contienne au moins 
$r_1$ valeurs $>r_0+r_2$. L'ensemble des valeurs $\{1,\ldots, 2n \}$ est 
coup\'e en trois intervalles $X=\{1,\ldots, r_0+r_2 \}$, 
$Y'= \{ r_0+r_2+1,\ldots , r_1+r_3\}$, 
$Y''=\{r_1+r_3+1,\ldots ,2n \}$.

De m\^eme, les permutations, consid\'er\'ees comme mots, 
sont coup\'ees en trois segments de longueurs 
respectives $r_2+r_3$, $r_0+r_1-r_2-r_3$, $r_2+r_3$. 
Pour la projection $p:\,  X\rightarrow x$, $Y'\rightarrow y'$, $Y''$ sur l'alphabet
$\{x<y'<y'' \}$, on a que $\mu\geq b$ implique que le facteur gauche de 
longueur $r_0+r_1$ contient au moins $r_1$ valeurs dans 
$Y' \cup Y''$. Tenant compte de ce que $\mu$ est palindrome, cela implique que
$$\mu \geq[r_0,r_1,r_2,r_3] \, \Leftrightarrow\, p(\mu)\geq v := 
x^{r_0} {y'}^{\alpha} {y''}^{r_2} {y'}^{2\beta} x^{r_2} {y'}^{\alpha} {y''}^{r_0} \ , $$
avec $\alpha=r_3 -r_0$, $\beta = r_0+r_1-n$.

Ce mot est l'inf des palindromes d'\'evaluation 
$x^{r_0 +r_2} {y'}^{r_1+r_3-r_0-r_2}  {y''}^{r_0+r_2}$
qui soient plus grands que $p(b)$. Le palindrome minimum qui se projette
sur $v$ est, en marquant les m\^emes coupures que $v$,

\noindent
$b_+ := 1\ldots r_0 \, |\,  r_0+r_2+1\ldots, r_2+r_3 \, |\, 
r_1+r_3+1 \ldots  r_1+r_2+r_3 \, |\, $ \hfill \break
\hfill $ 
r_2+r_3+1 \ldots r_0+r_1 \, |\, r_0\ldots r_0+r_2 \, |\,  r_0+r_1+1\ldots 
r_1+r_3 \, |\, 2n-r_0+1\ldots 2n $.

\smallskip
Comme dans le cas du groupe sym\'etrique, on termine l'analyse en v\'erifiant que
 $p(b_+)$ reste bien minimum lorsque l'on fait varier la projection
d'alphabet $p : \{1 \ldots 2n \}\rightarrow\{x,y \} $.

Les trois autres cas se traitent explicitement de la m\^eme mani\`ere.

Etant donn\'ee une bigrassmannienne  $b=[r_0,r_1,r_2,r_3] $ de  ${\goth{S}}(2n)$, 
la cobigrassmannienne qui clive avec elle est 
$c= \omega b'$, avec $b' = [r_1-1,r_0+1,r_3+1,r_2-1]$. De l'existence de
${b'}_+$, on d\'eduit donc par multiplication par $\omega$
l'existence d'une permutation palindrome maximale dans l'id\'eal 
$[\leq c] $ compl\'ementaire de $[b\leq]$, qui n'est autre que $\omega {b'}_+$.

Enfin, on voit, sur son expression explicite, que $b_+$ a deux descentes, 
lesquelles sont \`a des places sym\'etriques, de m\^eme que son inverse.
En d'autres termes, l'\'el\'ement correspondant de $B_n$ est une 
bigrassmannienne   \qed


\vskip 3mm
\th TH\'EOR\`EME 7.4 
\enonce L'image de la base de $B_n$ dans ${\goth{S}}(2n)$
est l'ensemble des palindromes 
$\{b_+ \}$ qui sont les Sup  respectifs  des couples
miroirs de bigrassmanniennes de ${\goth{S}}(2n)$, et en correspondance bijective 
avec ces derniers.

Le treillis enveloppant de $B_n$ est distributif, i.e. chaque \'el\'ement de la
base clive $B_n$ en une union disjointe de deux intervalles.

La base est un sous-ensemble  strict 
de l'ensemble des bigrassmanniennes de $B_n$.
\endth

\Rem   Le cardinal de la base de $B_n$ est $n(2n^2+1)/3$, et donc 
la fonction g\'en\'eratrice des cardinaux est 
$$(1+z)^2 /(1-z)^4 = 1+z+ 19z^2 +44z^3 +85z^4 +\cdots \ .$$
Le rapport $ card( base(B_n)) / card(Bigr(B_n))$
tend vers 0 comme $1/n$  lorsque $n$ tend vers l'infini.


La seule bigrassmannienne de $B_4$ qui n'appartient pas
\`a la base a pour code
$[0042]$ et  $drlm$  $s_3 s_2 s_1 s_2 s_4 s_3$; elle est le sup des 
deux \'el\'ements de la base $[0050] = s_3 s_2 s_1 s_2 s_3$ et
$[0022] = s_3 s_2 s_4 s_3$.
Les cinq bigrassmanniennes de $B_5$ exclues de la base ont 
pour codes respectifs
$$[00053],\  [00420],\ [00062],\ [00422],\ [00453] $$


\vskip 5mm

\section 8. Annexe  
\endsection
Commen\c{c}ons par rappeler bri\`evement la preuve classique du th\'eor\`eme de Mac 
 Neille fournie par la m\'ethode de O.Ore.

\smallskip
Soit donn\'ee une relation ${\cal{R}} \subset \bar X \times X$ entre deux ensembles 
$\bar X$ et $X$. Pour chaque $x \in X$, nous posons 
$x\bar \rho  =\{\bar x \in \bar X: (\bar x,x)\in{\cal{R}} \}$ et 
$Y\bar \rho  = \cap \{y\bar \rho  : y\in Y \}$ pour chaque partie 
$Y \neq\emptyset , X$ de $X$.  On convient de plus que
$\emptyset \bar \rho  = \bar X$ et $X\bar \rho  = \emptyset $. 

On d\'efinit de m\^eme $\rho $ en \'echangeant le r\^ole de $X$ et de $\bar X$, 
et tous les \'enonc\'es qui suivent restent valides par 
cet \'echange,  un ph\'enom\`ene que nous nous dispenserons souvent de
mentionner.

\smallskip 
Il est clair que $\bar \rho  : 2^{X} \rightarrow 2^{\bar X}$ est d\'ecroissante
$$ ( Y'\subset Y\in2^X \ \Rightarrow\ Y\bar \rho  \subset Y'\bar \rho   ) $$
 et que $\bar \rho \rho  : 2^X\rightarrow 2^X$ est croissante
( $Y\in2^X \ \Rightarrow\ Y\subset Y\bar \rho \rho $).

On a donc $\bar \rho \rho  \bar \rho  = \bar \rho $ ( et $ \rho  \bar \rho  \rho  = \rho $) 
puisque
$$ Y\bar \rho  \subset (Y\bar \rho )\rho  \bar \rho  
= Y \bar \rho \rho  \bar \rho  = (Y\bar \rho \rho )\bar \rho  
\subset Y\bar \rho $$
identiquement.

\smallskip
Soit maintenant $\bar T = \{Y\bar \rho  : Y\in2^X \} \in 2^{2^{\overline{ X}} }$.
D'apr\`es la d\'efinition de $\bar \rho : 2^X \rightarrow 2^{\overline{X} }$, 
la famille $(\bar T,\subset)$ de parties de $\bar X$ munie de l'ordre d'inclusion,
est un treillis dans lequel l'op\'eration {\it Inf} 
est l'intersection ensembliste $\cap$. Plus pr\'ecis\'ement,
$(\bar T, \subset) $ est le plus petit treillis contenant tous les
$x\bar \rho $ ($x\in X$).

Sym\'etriquement, $T=\{\bar Y \rho  : \bar Y \in2^{\bar X} \}
\in2^{2^X}  $ est le treillis engendr\'e par les 
$\bar x\rho $ ($\bar x \in\bar X$). Si $Y\in T$, on a, par d\'efinition,
$Y\bar \rho \in\bar T$ et $Y=\bar Y'\rho $ pour une certaine partie $\bar Y'$
de $\bar X$. On a donc 
$$Y\bar \rho \rho  = \bar Y'\rho  \bar \rho  \rho  = \bar Y'\rho  = Y \ ,$$
ce qui montre que les restrictions $\bar \rho : T\rightarrow\bar T$ et
$\rho :\bar T \rightarrow T$ sont deux antiisomorphismes
(de la relation d'ordre $\subset$) inverses l'un de l'autre.

Autrement dit, si $\{Y_i : i\in{\cal{J}} \}$ est une famille d'\'el\'ements
de $T$, on a 
$Inf\{Y_i : i\in{\cal{J}} \}= \cap\{Y_i:i\in{\cal{J}} \}  \in T$, 
cependant que 
$Sup \{Y_i :i\in{\cal{J}} \} = \bar Z\rho $, avec 
$\bar Z = \cap \{Y_i\bar \rho  : i\in{\cal{J}} \}\in\bar T$.

\smallskip
Nous appelerons $T$ et $\bar T$ le $X$-treillis et le 
$\bar X$-treillis engendr\'es par ${\cal{R}}$ et 
nous utiliserons l'abr\'eviation 
$$Diag({\cal{R}})= \{(\bar Y,Y) \in 2^{\bar X}\times 2^X\,  :\, \bar Y\rho  = Y;
Y\bar \rho  = \bar Y \} \subset\bar T \times T \ .$$

En consid\'erant, comme ci-dessus,  ${\cal{R}}$ comme une matrice bool\'eenne, 
une paire de parties $(\bar Y, Y) $ sera appel\'e un rectangle
(de {\bf 1} ) 
ssi  $\bar Y \times Y$  est contenu dans ${\cal{R}}$.
Par construction, les paires $(\bar Y \times Y) \in Diag({\cal{R}})$ 
sont les rectangles maximaux de ${\cal{R}}$, en ce sens que, \'etant donn\'e
$Y\subset X$, $\bar Y$ est la plus grande partie de $\bar X$ telle
que  $\bar Y \times Y$ soit un rectangle, et que l'on ait la condition
sym\'etrique sur $Y$ par rapport \`a $\bar Y$. Par d\'efinition, les \'el\'ements de
$\bar T$ et $T$ sont les projections de 
$Diag({\cal{R}})$ sur $2^{\overline{X}  }$ et $2^X$.



\vskip 8mm
Consid\'erons deux parties $\bar X_1$ de $\bar X$
et $X_2$ de $X$.

Elles d\'efinissent par restriction trois autres relations
$${\cal{R}}_1 = {\cal{R}}\cap(\bar X_1\times X)\ ; \ 
{\cal{R}}_2 = {\cal{R}}\cap(\bar X \times X_2)\ ; \ 
{\cal{R}}_3 = {\cal{R}}\cap(\bar X_1\times X_2)  $$
engendrant les paires de treillis
$(\bar T_1, T_1)$, $(\bar T_2, T_2)$, $(\bar T_3, T_3)$.

Par d\'efinition $T_1$ (resp. $\bar T_2$) est une famille
de parties de $X$ (resp. $\bar X$) contenue dans $T$
(resp. dans $\bar T$)
et l'injection naturelle $T_1 \rightarrow T$
(resp. $\bar T_2 \rightarrow\bar T$) est un morphisme pour l'op\'eration
{\it Inf} puisque cette derni\`ere n'est autre que l'op\'eration
ensembliste $\cap$.

On a de m\^eme des morphismes canoniques $\bar T_3 \rightarrow\bar T_1$
et $T_3 \rightarrow T_2$.

\setbox2=\hbox{et}
\th LEMME 8.1 
\enonce Si $\bar X_1$ et $X_2$ sont tels que 
$T_1=T$ et $\bar T_2 = \bar T$, on a 
$$ T_3 = T \quad \box2 \quad \bar T_3 = \bar T \ .$$
\endth

\noindent {\it Preuve}\pointir 
En posant $X_1=X$, $\bar X_2= \bar X$, $\bar X_3 =\bar X_1$ et 
$X_3=X_2$, 
les hypoth\`eses et la conclusion peuvent s'\'ecrire 
$$   Diag({\cal{R}}) = Diag({\cal{R}}) \cap \{ 2^{\overline{X_i}} \times 2^{X_i}\} 
\ (= Diag({\cal{R}}_i)) \ ,$$
respectivement pour $i=1,2$ et pour $i=3$.

Supposons que $(\bar Y,Y)$ soit un rectangle maximal dans
$\bar X_2 \times X_1$. On a d'une part $\bar Y \times Y \subset {\cal{R}}_3$,
donc $\subset{\cal{R}}$, et d'autre part que pour chaque $z\in X_1\setminus Y$,
il y au moins un $\bar y \in \bar Y$ pour lequel $(y,z) \notin {\cal{R}}_3$,
donc $\notin {\cal{R}}$, et sym\'etriquement pour chaque 
$z\in \bar X_2\setminus \bar Y$.  Ceci implique que $(\bar Y,Y)$ est la
restriction \`a $X_2 \times Y$ du rectangle maximal 
$(Y\bar \rho , \bar Y \rho ) \in Diag({\cal{R}})$ et \'etablit que
$$Diag({\cal{R}}_3) \subset Diag({\cal{R}}) \cap ( 2^{\overline{X_1}} \times 2^{X_2} ) \ .$$
R\'eciproquement, soit maintenant $\bar Y \times Y \in Diag({\cal{R}})$. Sa restriction
\`a $\bar X_1 \times X_2$ est encore un rectangle dont il suffit de prouver 
qu'il est maximal pour chaque $z\in X\setminus Y$. Or  la maximalit\'e
de $\bar Y \times Y$ implique l'existence d'au moins un 
$\bar y \in \bar Y$ tel que $(\bar y,z) \notin {\cal{R}}$
et l'hypoth\`ese $Diag({\cal{R}}_1) = Diag({\cal{R}})$ implique que l'on puisse
prendre un tel $\bar y$ dans $\bar Y \cap \bar X_1$. 

Un argument sym\'etrique s'applique aux $\bar z \in\bar X\setminus \bar Y$,
ce qui ach\`eve la preuve  \quad \qed

\smallskip 
Nous en venons maintenant \`a la preuve des r\'esultats \'enonc\'es 
au paragraphe 2.



\smallskip 
\th LEMME 2.3 
\enonce  Soit ($X,\, \leq$) un ensemble ordonn\'e. 
Un \'el\'ement $x\neq\wedge X$ appartient \`a la base $B$ 
ssi il est un \'el\'ement minimal de 
$X\setminus [\leq z]$ pour au moins un $z\in X$.

Quand ($X,\, \leq$) est un treillis, cette condition est remplie ssi
$x$ couvre exactement un autre \'el\'ement de $X$.
\endth

\noindent {\it Preuve}\pointir 
Soit $x$ un \'el\'ement de $X\setminus \wedge X$. Par d\'efinition, il 
appartient au compl\'ement de $X\setminus B$ de la base ssi il existe une
partie $Y\neq\emptyset$ de $X$ telle que 
$$x \notin Y \quad \& \quad [x\leq]= \cap\{[y\leq]: y\in Y \} \ . \leqno (\star)$$
On observe d'abord que cette relation est vraie pour un $Y\neq\emptyset$
ssi elle est vraie pour le cas particulier de
$Y= [<x] \ (:= [x\leq]\backslash x)$.  En effet, si $Y$ satisfait 
($\star$) on a $y \in[<x]$ pour chaque $y\in Y$, 
et d'autre part $Y\cup\{y \}$ satisfait encore ($\star$) pour
chaque $y\in[<x]$. On a donc $x\in X\setminus B$ ssi

\setbox2=\hbox{ , o\`u }
$$ [x\leq] = Z \box2\quad Z:== \cap\{[y\leq] : y\in[<x] \}\ .$$

Par construction $Z\setminus [\leq x]$ est l'ensemble des 
$z\in X$ tel que $x$ soit un \'el\'ement minimal de 
$X\setminus [\leq z]$. On a donc $x \in X\setminus B$ 
ou $x \in B$ selon que $Z\setminus [\leq x]$ est vide ou non.
Il est clair que $x\in B$ quand $x$ ($\neq \wedge X$) est un
\'el\'ement minimal de $X$, car il suffit de prendre n'importe quel
$z\in X\setminus [\leq x]$. Il en est de m\^eme quand $x$ couvre un seul
\'el\'ement, qui est alors $Sup([<x])$. Le cas particulier o\`u
($X,\, \leq$) est un treillis est trivial puisque l'on a alors
$\wedge X \neq\emptyset$ et pour tout $x\in X\setminus \wedge X$,
$Sup([<x] \neq\emptyset)$  \quad \qed



\smallskip
\th PROPOSITION 2.4 
\enonce  La projection sur la base  
$\beta :\,  X\ni x\rightarrow B \cap [\leq x]\in \, (2^B, \subset) $ 
est un isomorphisme d'ordre 
et l'on a $B \subset C$ pour  toute partie $C$ de $X$ 
ayant la m\^eme propri\'et\'e.
\endth

\noindent {\it Preuve}\pointir 
Soient $y,z \in X$. Si $Y := [\leq y]\setminus [<z]$ est vide, 
c'est-\`a-dire si $y\leq z$ on a $y\beta \subset z\beta$. Pour \'etablir que 
$\beta$ est isomorphisme il suffit donc de montrer que $Y$ contient
au moins un \'el\'ement de la base quand $Y\neq\emptyset$.

Or comme $Y$ est fini, il contient au moins un \'el\'ement minimal $b$.
On a $b \neq\wedge X$ puisque $\wedge X\in[\leq z] $ quand $\wedge X \neq\emptyset$,
et donc $b\in B$ d'apr\`es le lemme 2.3.

Soit maintenant $C$ une partie de $X$ telle que l'application 
$\gamma : X\ni x \longrightarrow x\gamma = C\cap[\leq x]$ soit un isomorphisme. 
Supposons qu'il existe
un $b\in B\setminus C$. D'apr\`es le lemme 2.3 il existe au moins un
$z\in X\setminus [b\leq]$ tel que $[<b] \subset[\leq z]$. On  a alors
$b\gamma = C\cap[<b] \, \subset z\gamma = \, C\cap [\leq z]$, 
contredisant l'hypoth\`ese
que $\gamma$ est un isomorphisme. Donc $C$ contient $B$.
\quad \qed

On d\'efinit de m\^eme l'application 
$\bar \beta : X\in x \longrightarrow \bar B \cap [x\leq]$,
et l'on a pour $\bar \beta$ des \'enonc\'es sym\'etriques de ceux pour $\beta$.
On notera que $x\beta = \emptyset $ ssi $x=\wedge X$, 
et $x\beta=X$ ssi $x=\vee X$.

\smallskip
\noindent {\it Exemples}\pointir 
Soit $X=\{1,2,3,4 \}$ avec la relation d'ordre $\leq$ d\'efinie par
$\{1,2,3 \}= [\leq3]$ et $\{1,2,4 \}= [\leq4]$. Tous les \'el\'ements de 
$X$ appartiennent \`a la base et \`a la cobase. La projection $\gamma$
sur $C= \{1,2,3 \}$ est injective, mais elle n'est pas un 
isomorphisme puisque $4\gamma = \{1,2 \} \subset 3\gamma=\{1,2,3 \} $ bien que
$3$ et $4$ soient incomparables. Le treillis enveloppant 
de $X$ est obtenu en ajoutant \`a $X$ un plus petit et un plus grand
\'el\'ement, et aussi un \'el\'ement $t$ tel que 
$$t = Sup(\{1,2 \}) = Inf (\{3,4 \}) \ .$$
Ce treillis est le treillis enveloppant de ${\goth{S}}(3)$ (muni de l'ordre fort)
vu au  5.

\smallskip
La proposition 2.4 requiert une condition topologique quand $X$ n'est pas
fini. Ainsi elle n'est pas vraie quand ($X,\, \leq$) est un intervalle
de la droite r\'eelle ${\bb{R}}$ puisque dans ce cas la base et la cobase sont
des ensembles vides. Par contre elle est vraie pour 
(${\bb{Z}},\, \leq$) qui est \'egal \`a sa base, puisque la condition des cha\^\i nes
descendantes est v\'erifi\'ee pour toute partie 
$[\leq y]\setminus [\leq z]$ non vide. Le treillis enveloppant
est obtenu en ajoutant \`a ${\bb{Z}}$ un plus petit et un plus grand \'el\'ement.

La proposition 2.4 est aussi v\'erifi\'ee par le treillis distributif 
($2^{\bb{Z}},\, \subset$)  dont les \'el\'ements sont les parties de ${\bb{Z}}$.

Enfin soit $X$ 
l'ensemble union de l'intervalle $[0,1]$ de ${\bb{R}}$, muni de son ordre
naturel et d'un ensemble $B =\{b_x \, : \,  x\in[0,1]\}$, d'\'el\'ements
incomparables. On ajoute les relations crois\'ees 
$0<b_x $ et $b_x < x'$ ssi $x\leq x'\in[0,1]$. 
Alors $B$ est \`a la fois la base et la cobase de $X$.
L'application $\beta: X \longrightarrow B $
est un isomorphisme d'ordre, ce qui n'est pas le cas de 
$\bar \beta : X\longrightarrow B$.

C'est un probl\`eme ouvert de trouver des cat\'egories non triviales 
de treillis pour
lesquelles la proposition 2.4 et sa sym\'etrique sont vraies.



\smallskip

Soit ${\cal{R}}'\subset \bar B \times B$  la relation d\'efinie par 
$(\bar b,b) \in {\cal{R}}'$
ssi $\bar b \geq b$, c'est-\`a-dire, de fa\c{c}on \'equivalente, ssi
$b\in\bar b\beta$ ou $\bar b \in b\bar \beta$.

\th PROPOSITION 2.5
\enonce  La relation ${\cal{R}}'$ est une relation basique.
\endth

\Preuve  Comme $X\setminus [\leq x] \neq \emptyset$, sauf si $x=\wedge X$,
la preuve pr\'ec\'edente montre que $\bar b \beta\neq B$ pour chaque
$\bar b \in\bar B$. Supposons qu'un \'el\'ement $\bar b \in\bar B$ et
une partie $\bar C$ de $\bar B$ soient tels que 
$\bar b \beta = \cap \{\bar c \beta : \bar c\in\bar C \}$. Comme $\beta$ est 
un isomorphisme 
d'apr\`es (2.4), on a $\bar c \in[\bar b \leq]$ pour tout $\bar c \in\bar C$,
et r\'eciproquement $\bar b \beta \subset x\beta$ pour tout $x\in[\bar b\, \leq]$; 
l'hypoth\`ese implique que $\bar b \beta = \cap\{x\beta : x\in[\bar b\leq] \}$ et
enfin $\bar b \in \bar C$ d'apr\`es la d\'efinition de $\bar B$.

Autrement dit, aucune ligne de ${\cal{R}}'$ n'est l'intersection d'autres lignes.
Ceci ach\`eve la preuve par sym\'etrie entre $B$ et $\bar B$ \quad\qed

\smallskip 
Nous appelerons d\'esormais la relation ${\cal{R}}'$ pr\'ec\'edente
la {\it relation basique} de l'ensemble ordonn\'e ($X,\, \leq$).

On voit facilement qu'un \'el\'ement $x\in X$ appartient \`a $\bar B \cap B$
ssi $x\bar \beta \times x\beta$ est un rectangle de {\bf 1} (au sens donn\'e plus
haut \`a ce terme) dans la relation basique.

\smallskip
Donnons  maintenant \`a la preuve du th\'eor\`eme 2.6.

Prenant une copie
$\bar X$ de $X$ et une bijection  $X\ni x \rightarrow \bar x \in \bar X$,
 nous associons \`a  ($X,\, \leq$) sa {\it matrice d'incidence},
c'est-\`a-dire la relation ${\cal{R}}$ dans $\bar X \times X$ telle que 
$(\bar x_1,x_2) \in {\cal{R}}$ ssi $ x_1\geq x_2$.
La relation basique de ($X,\, \leq$) est simplement la restriction
de ${\cal{R}}$ \`a $\bar B \times B$.

Utilisant les conventions du d\'ebut de cette annexe, on voit que pour chaque 
$x\in X$, on peut identifier la colonne $x\bar \rho$ \`a l'intervalle
sup\'erieur $[x\, \leq]$ et la ligne $\bar x \rho$ \`a $[\leq\bar x ]$.
Le treillis $T$ et le treillis antiisomorphe $\bar T$ de la construction
de Ore sont donc respectivement le treillis enveloppant de 
($X,\, \leq$) et celui de l'ensemble antiisomorphe ($\bar X,\, \geq$). 

Comme les applications $\beta$ et $\bar \beta$ sont injectives, 
les relations ${\cal{R}}\cap (\bar X\times B)$ et ${\cal{R}}\cap (\bar B\times X)$ 
engendrent des paires de treillis isomorphes \`a $\bar T \times T$. 
Les hypoth\`eses du lemme 2.8 sont donc satisfaites, ce qui permet
de conclure que la relation basique
${\cal{R}} \cap(\bar B \times B)$ de ($X,\, \leq$) est aussi celle du treillis $T$
\quad\qed 


\smallskip
Nous en venons maintenant au clivage.

\smallskip
Soit ${\cal{R}} \subset \bar B \times B $ la relation basique d'une relation
d'ordre ($X,\, \leq$).

Le lemme 2.2 montre que deux \'el\'ements $\bar x, x\in X$ sont tels 
que $X$ n'est l'union disjointe de $[\leq\bar x]$ et
$[x\leq]$ que si $(\bar x,x) \in\bar B \times B$. En ce cas, $x$ d\'etermine
$\bar x$ et r\'eciproquement.

Il est clair que si $(\bar b_1,b_1)$ et $(\bar b_2,b_2)$
sont deux paires clivantes, on a $b_1 \leq b_2$ 
ssi $\bar b_1 \leq \bar b_2$.
Ceci conduit \`a d\'efinir le morphisme partiel $NEG$ de 
$B$ dans $\bar B$ en posant :

\setbox2=\hbox{ s'il existe $\bar b\in\bar B$ tel que 
$(\bar b,b) $ soit un clivage  } 
\setbox3=\hbox{ sinon}
$$\eqalign{ NEG(b) &= \ \bar b\ \box2   \cr
                  &=  \  \emptyset \ \box3 \cr } $$

Nous supposons d\'esormais que $X$ est le treillis d\'efini par
$R$.

Soient $b\in B$, $Y := X\setminus [b\leq]$ et $s := Sup(Y)$.
L'ensemble $X$ est l'union de $[\leq s]$ et de $[b\leq]$, cette
union \'etant disjointe ssi $b \notin [\leq s]$. Donc
$NEG(b) = s $ ou $\emptyset$ selon que 
$b\notin [\leq s]$ ou non.

Consid\'erons alors l'unique \'el\'ement $b_-$ couvert par $b$.
Comme $b_- \in Y $, on a $Inf(b_- ,s) \in\{b,b_- \}$
et d'autre part 
$Sup({Inf(b,y) \, : y\in Y  }) = b_- $. 

Par cons\'equent la relation de distributivit\'e
$$Inf\bigl( b_- ,\, Sup(Y)  \bigr) = 
Sup\bigl( \{ Inf(b_-,\, y) \, : y\in Y \}\bigr)$$
implique $b\notin [\leq s]$ et enfin 
$NEG(b) = s \neq \emptyset$.

Compte tenu de la sym\'etrie entre $B$ et $\bar B$, cette remarque
\'etablit la partie directe du th\'eor\`eme 2.8.

\smallskip
Revenant au cas g\'en\'eral, nous isolons le 

\th LEMME 8.5
\enonce  Pour chaque $b\in B$, on a $NEG(b) \neq\emptyset$
ssi il existe un $\bar b \in\bar B$ tel que 
$\bar b\, \beta \, =\,  B\setminus [b\leq]$.
\endth

\Preuve  Il suffit d'observer qu'avec les notations introduites plus
haut, on a $b \notin [\leq s]$ ssi $s\beta = Y\cap B $ \quad\qed

\smallskip
Comme $B\cap[b\leq]$ est l'ensemble des $b'\in B$ tels  que 
$b' \bar \beta \subset b\bar \beta$, il en r\'esulte que la fonction
$NEG$ se calcule directement \`a partir de la relation ${\cal{R}}$
et, de plus, que si $NEG(b) \neq\emptyset$ pour chaque $b\in B$,
la restriction de ${\cal{R}}$ \`a $NEG(B) \times B$ est d\'etermin\'ee
par la seule donn\'ee de la restriction de l'ordre $\, \leq\,$
\`a $B$.

Pour achever la preuve, nous supposons d\'esormais ${\cal{R}}$ telle que
$NEG(b)$$\neq\emptyset$ pour chaque $b\in B$.

Soit $T \in 2^{2^B}$ le plus petit treillis pour les op\'erations
$\cup$ et $\cap$ de $(2^B,\, \subset)$ qui contienne tous les sous-ensembles
$b_0 := [b\leq]$ ($b\in B$) de $B$; il est classique que
($T,\, \subset$) est un treillis distributif en tant que sous-treillis
du treillis distributif ($2^B,\, \subset$). En outre 
$b\longrightarrow b_0$ est un isomorphisme (d'ordre) de $B$ sur une partie
$B_0$ de $T$.

Posons aussi $b^0 := B\setminus [b\leq] \subset2^B$ pour chaque $b\in B$.
Cet ensemble appartient \`a $T$ et il est l'union des
$b'_0 \in B_0\setminus [b_0\, \subset]$, ce qui montre
que ($b^0,b_0$) est un clivage de $T$ et que la base et la
cobase de ce treillis sont $B_0$ et $B^0 = \{b^0\, : b\in B \}$.

D'apr\`es le lemme 8.5, la relation basique $R_0 \subset B^0 \times B_0$ de $T$
est isomorphe \`a la restriction ${\cal{R}}'$ de ${\cal{R}}$ \`a $\bar B'\times B$ o\`u
$\bar B' = NEG(B) \subset\bar B$. 

On v\'erifie maintenant que $\bar B' = \bar B$. Soit
$\bar b$ un \'el\'ement de la cobase $\bar B$. Si $b\in\bar b\beta$, on a
$b' \in \bar b \beta$ pour tout $b' \in B\cap[\leq b]$ 
d'apr\`es la d\'efinition de $\leq\, $. 
Par cons\'equent, l'image de $\bar b \beta$ dans $2^B$
par l'isomorphisme $b\longrightarrow b_0$ est un \'el\'ement du treillis $T$.
On a donc $\bar b \in \bar B'$, montrant que $\bar B' =\bar B$, 
c'est-\`a-dire que $T$ est bien le treillis engendr\'e par 
${\cal{R}}$  \quad\qed

\smallskip
Les calculs dans le treillis distributif $T$ sont facilit\'es
par l'identit\'e de Morgan
$$t \bar \beta\, = \, NEG(B\setminus t\beta)  \quad (t\in T)$$
que l'on d\'eduit imm\'ediatement du lemme 8.5 en identifiant, 
par compl\'e\-men\-ta\-tion ensembliste, le treillis antiisomorphe
$\bar T \in 2^{2^{\overline{B} } }$ \`a un sous treillis
de ($2^B,\, \subset$).

Il est curieux que l'\'egalit\'e num\'erique $card(B) = card(\bar B)$ 
entre la base et la cobase reste vraie dans la vari\'et\'e des 
treillis modulaires dont les treillis distributifs sont une sous vari\'et\'e.


\smallskip 
Pour avoir des exemples plus substantiels, nous consid\'erons le treillis
des partitions d'un entier $n$. Nous faisons r\'ef\'erence \`a un article r\'ecent de 
C.Greene et Kleitman [G-K] dans lequel le lecteur trouvera expos\'es les 
principaux r\'esultats sur l'ensemble des partitions en tant que treillis
( cf. aussi S.Kim dans un article \`a para\^\i tre).

Nous adoptons la notation exponentielle pour les partitions, 
et appelons {\it \'equerre} une partition du type
$1^k c$, i.e. une partition qui a au plus une part diff\'erente de 1.


\th PROPOSITION 8.6 
\enonce  La base du treillis des partitions d'un entier fix\'e $n $ est 
constitu\'ee des partitions, ayant trois parts diff\'erentes au plus, du type
$a b^k c$, o\`u  $k\geq2$ et $a<b<c $, avec les cas d\'eg\'en\'er\'es suivants :
$a b^k$, $b^k c$, $b^k$, ( $k\geq2$),  et $bc$. 

La cobase est form\'ee des partitions transpos\'ees des \'el\'ements de la 
base.
L'intersection de la base et de la cobase est constitu\'ee
par les \'equerres.

Pour que deux partitions $g$, $\bar g$, d\'eterminent un clivage,
il faut que l'une d'entre elles soit une \'equerre. R\'eciproquement,
chaque \'equerre donne deux clivages, selon qu'elle est consid\'er\'ee comme
un \'el\'ement de la base ou de la cobase.
\endth

\smallskip\noindent{\it Preuve}\pointir   
En effet, deux partitions sont cons\'ecutives dans le diagramme des 
partitions ssi l'on obtient le diagramme de l'une \`a partir de celui de 
l'autre en d\'epla\c{c}ant de mani\`ere minimale une bo\^\i te. 
Si la partition a au 
moins quatre parts diff\'erentes, elle ne peut \^etre irr\'eductible pour $\vee$. 
On exclut ensuite les cas $a^h b^k c^l$ o\`u $hl >1$. Les cas restants se
v\'erifient sans difficult\'e.

Soit maintenant un clivage $[g\leq],\, [\leq\bar g] $. La partition $g$
appartient \`a la base, supposons la du type 
$g= a b^k c$, $  a<b\leq c$ o\`u  $ 2\leq k$ si $b\neq c$ et $1\leq k  $ si 
$b=c$. 
Consid\'erons $h=  1^{n-c-1} c+1$. L'\'el\'ement $g$ ne v\'erifie pas 
$ g\leq h$, puisque $a<a+1$.
Or $h$ est couverte par une seule partition, \`a savoir
$h_+ := 1^{n-c-2}2\, c$ et l'on a $g\leq h_+$.  Donc $h$ est un \'el\'ement
maximal du compl\'ement de $[g\leq]$. Comme par hypoth\`ese, 
ce compl\'ement est \'egal \`a $[ \leq\bar g]$, on doit avoir
$\bar g=h$. De plus alors $g= a c^m$, 
o\`u $m$ est la partie enti\`ere de $n/c$ et $a$ le reste.
Par conjugaison des partitions, on v\'erifie que sym\'etriquement,
le compl\'ement de $[h\leq] $ est un intervalle inf\'erieur  \quad \qed

\smallskip Par exemple, les rectrices de $1^5 2 4^2$
sont $34^3$, $1 3^3 5$, $1 2^4 6$ et $1^7 8$. Le lecteur pourra
v\'erifier que le nombre des rectrices d'une partition est au plus 
\'egal \`a la valeur de sa deuxi\`eme plus grande part.



\vskip 5mm
\centerline{\bf  Bibliographie}

\parindent 0mm
\vskip 3mm

[Bi]\ G. Birkoff, {\it Lattice theory}, 3\`eme ed., Am. Math. Soc.,
   Providence (1967).

[Bj]\ A. Bj\"orner, {\it Ordering of Coxeter groups}, 
   Contemp. Math. {\bf 34}, A.M.S. (1984) 175-195.

[B-W]\ A. Bj\"orner, M. Wachs, {\it Generalized quotients in Coxeter groups},
Trans. A.M.S. {\bf 308} (1988) 1-37.

[Bo]\ N. Bourbaki, {\it Groupes et Alg\`ebres de Lie}, Fasc {\it 34},
 Hermann, Paris (1968).

[De]\ V.V. Deodhar, {\it Some characterizations of Bruhat ordering on a 
Coxeter group}, Invent. Math. {\bf 39} (1977) 187-198.

[Ch]\ I. Cherednik, {\it A unification of Knizhnik-Zamolodchikov 
and Dunkle operators via affine Hecke algebras}, Invent. Math. {\bf 106}
(1991) 411-431.

[Eh]\ C. Ehresmann, {\it Sur la topologie de certains espaces homog\`enes},
Ann. Math. {\bf 35} (1934) 396-443.

[Er]\ H. Eriksson, {\it Computational and combinatorial aspects of
Coxeter groups}, th\`ese, KTH Stockholm (1994).

[Fo]\ Fokko du Cloux, {\it A transducer approach to  Coxeter groups}, 
pr\'epubli\-ca\-tion (1995).

[Fu]\ W. Fulton, {\it Flags, Schubert polynomials, degeneraci loci}
Duke Math. {\bf 65} (1992) 381-420.

[G-Ki]\ M. Geck, S. Kim, {\it On the Bruhat order of
finite Coxeter groups}, pr\'epublication (1996).

[G-K]\ C. Greene, D. Kleitman, {\it Longest chains in the lattice of integer
partitions ordered by majorization}, Europ. J. Comb. {\bf 7} (1986) 1-10.

[G-R]\ G. Guilbaud, P. Rosenstiehl, {\it Analyse alg\'ebrique d'un scrutin},
in {\it Ordres totaux finis}, Gauthiers-Villars, Paris (1971).

[Lak]\ V. Lakshmibai, {\it Geometry of G/P. The symplectic group
and the involution $\sigma $}, J. Alg. {\bf 108} (1987) 403-434.

[L-S 1]\ A. Lascoux, M.P. Sch\"utzenberger, {\it Structure de Hopf 
de l'anneau de cohomologie de la vari\'et\'e de drapeaux},
C.R. Acad. Sc. Paris {\bf 295} (1982) 629-633.

[L-S 2]\ A. Lascoux, M.P. Sch\"utzenberger, 
{\it Symmetrization operators on polynomial rings},
Funk. Anal. {\bf 21} (1987) 77-78.

[Mo]\ A. Molev, {\it On Stirling partitions of the symmetric group},
pr\'epublica\-tion, Australian National University (1995).

[MRR]\ W.H. Mills, D.P. Robbins, H. Rumsey, {\it Alternating sign
matrices and descending plane partitions}, J. Comb. Th. A 
(1983) 340-359.

[Pr]\ R.A. Proctor, {\it Classical Bruhat orders and lexicographic 
shellability}, J. Alg. {\bf 77} (1982) 104-126.

[Vr]\ D.N Verma, {\it M\"obius inversion for the Bruhat ordering on a
Weyl group}, Ann. Sc. Ec. Norm. Sup {\bf 4} (1971) 393-398.

\vfill\eject
\topskip 6in
\setbmp{-.2in}{6in}{6in}{c:/hsw/e-jc/foatavol/permuto1.bmp}
\vfill\eject
\topskip 6in
\setbmp{-.2in}{6in}{6in}{c:/hsw/e-jc/foatavol/permuto2.bmp}
\vfill\eject

\bye


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


