\magnification=\magstep1
\hsize=6truein
\vsize=9truein
\font\smcp=cmcsc8
\nologo
\def\m {\preccurlyeq} 
\def\endemo{\qed\enddemo} 
\def\D{\Delta} 
\def\Do{\Delta^{0}} 
\def\Dp{\Delta^{+}} 
\def\Dop{(\Do)^{+}}
\def\Dom{(\Do)^{-}}
\def\Dr{\D_{re}} 
\def\Drp{\Dr^{+}} 
\def\Di{\Delta_{im}} 
\def\d{\delta} 
\def\ir{\{\,\alpha_{1}, \ldots,\alpha_{l}\,\}}
\def\raN{\{\,\beta_{1}, \ldots ,\beta_{N}\,\}}
\def\rar{\{\,\beta_{1}, \ldots,\beta_{r}\,\}} 
\def\ram{\{\,\beta_{1}, \ldots ,\beta_{m}\,\}} 
\def\a{\alpha} 
\def\l{\lambda}
\def\b{\beta}
\def\t{\tau_{\pi}(i,j)}
\def\tp{\tau(i,j)} 
\def\sm{s_{i_{1}}\ldots s_{i_{m-1}}} 
\def\ss{s_{i_{1}}\ldots s_{i_{p-1}}}
\def\st{s_{i_{1}}\ldots s_{i_{t-1}}} 
\def\stt{s_{i_{1}}\ldots s_{i_{t}}} 
\def\smm{s_{i_{1}}\ldotss_{i_{m}}} 
\def\sh{s_{i_{1}}\ldots s_{i_{h-1}}} 
\def\sr{s_{i_{1}}\ldots s_{i_{r}}}
\def\sN{s_{i_{1}}\ldots s_{i_{N}}}
\def\Sn{\tilde S_n}
\def\figura#1#2#3{\bigskip{\noindent\centerline{\vbox to #2{\hrule width #1
 height 0pt depth 0pt \vfill\special{illustration
#3}}}}\medskip}

\topmatter \title{Affine permutations and inversion multigraphs}
\endtitle
\author Paolo Papi
\endauthor 

\affil
   Dipartimento di Matematica, Istituto G. Castelnuovo,\\ 
Universit\`a degli studi di Roma "La Sapienza",\\
P.le Aldo Moro 5, 00185 Roma, Italy. E-mail address: papi\@mat.uniroma1.it \\
\endaffil
\headline={\ifnum\pageno>1 {\smcp the electronic journal of
          combinatorics 4 (1997), \#R5\hfill\folio} \fi}
 \date{ Submitted: October 4, 1996. Accepted: January 21, 1997.}\enddate     
%\address\hskip-\parindent
   %Dipartimento di Matematica Istituto G. Castelnuovo\newline
   %Universit\`a di Roma "La Sapienza"  \newline
   %Piazzale Aldo Moro 5\newline  
   %00185 Rome --- ITALY  \newline
   %e-mail address:  \  papi\@mat.uniroma1.it
%\endaddress


 \abstract 
In this paper we solve the problem of  characterizing inversion multigraphs (cf. \cite{BB})
associated to affine permutations.
\endabstract
\endtopmatter


 
\document 
\heading \S 1 Introduction and basic definitions \endheading 
\bigskip
Let $W$ be an affine Weyl group of type $\tilde A_{n-1}$; $W$ is a group admitting the
following presentation: generators $s_1,\ldots,s_n$ and defining relations: 
$$\alignat 2  s_i^2&=1 & \quad i&=1,\ldots,n\\
s_is_{i+1}s_i&=s_{i+1}s_is_{i+1} & \quad i&=1,\ldots,n-1\tag 1\\
s_1s_ns_1&=s_ns_1s_n.\endalignat$$
The elements of $W$ can be regarded as "affine permutations": in fact, as Lusztig observed in
\cite{L}, the map $\Phi:W\to \Sn$ defined on generators as
$\Phi(s_i)=\pi_i,\,i=1,\ldots,n$ 
$$\pi_i(t)=\cases
t &\overline t\ne \overline i,\overline{i+1}\\
t-1 & \overline t=\overline{i+1}\\
t+1 & \overline t=\overline i\endcases.\tag 2$$
($\overline t$ denotes the residue class of $t$ modulo $n$) is an isomorphism onto
the following subgroup of permutations of the integers:
$$\Sn:=\{\pi:\Bbb Z\to\Bbb Z\mid \pi(t+n)=\pi(t)+n\ \forall\,t\in \Bbb Z,\quad
\sum_{t=1}^n\pi(t)=\frac{n(n+1)}{2}\}.$$
It follows at once from the previous description that an element $\pi\in\Sn$ is completely determined
by the n-tuple $[\pi(1),\ldots,\pi(n)]$.\smallskip
In \cite{BB} the authors develop a detailed analysis of the combinatorics of affine permutations;
moreover they exhibit various encodings of affine permutations and minimal coset representatives
of $\Sn/S_n$. In connection with the weak Bruhat order, they describe affine permutations through
certain {\it inversion multigraphs} and leave open the problem of classifying them.\par In this paper
we solve this last problem using our previous results on {\it compatible orderings} in root systems
proceeding as follows.
An inversion multigraph   encodes an  affine permutation $\pi$ by determining
its "affine inversions"; from the point of view of root systems this amounts to describing the set
of positive roots sent into negative ones by $\pi$. 
On the other hand, this kind of sets of positive roots has been combinatorially classified in
\cite{P} (where they are called {\it compatible sets}). So we translate the combinatorics of
compatible sets into that of inversion multigraphs, working out some further simplifications;
finally we obtain a characterization of the inversion multigraphs, involving  weight conditions on
certain triples of edges.\par As a notational convention, we will denote by
$\Bbb N$ (resp.
$\Bbb Z_+$) the set of positive (resp. non-negative) integer numbers. 
\medskip
\heading\S2 Affine roots in the geometric realization of $\Sn$\endheading
\bigskip
 As any Coxeter group, $\Sn$ can be faithfully represented as a transformation group (see e.g.
\cite{H}, \S5.3-5.4); for this consider the complex vector space
$V$ with basis
$\Pi=\{\a_1,\ldots,\a_n\}$ (the "simple roots") and let $W$ act on  $V$ by linear extension of the following formula:
$$s_i(\a_j)=\a_j-a_{ij}\a_i$$
where the $a_{ij}$'s are entries from the following $n\times
n$ matrix:
$$A=\left(a_{ij}\right)=\left(
\matrix
2&-1&0&0&\ldots&0&0&-1\\
-1&2&-1&0&\ldots&0&0&0\\
0&-1&2&-1&\ldots&0&0&0\\
\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots\\
0&0&0&0&\ldots&-1&2&-1\\
-1&0&0&0&\ldots&0&-1&2\endmatrix
\right).$$
\indent Define the root system as the set of $W$-orbits in $V$ of the simple roots:
$$\Delta:=W.\Pi.$$
Denote  by $\Dp$ the set of positive roots, i.e., the elements in $\Delta$ which are linear
combinations with non-negative coefficients of the simple roots.\newline
\indent Note that $W$ acts on
$V$ as a reflection group with respect to the bilinear form associated to the previous matrix
(in the basis $\Pi$); this
form is degenerate with 1-dimensional kernel generated by the so-called {\it fundamental imaginary
root}\footnote{This terminology is borrowed from the theory of Kac-Moody algebras \cite{K}; note
however that in our setting
$\d$ is not a root.}\newline
$\d:=\sum_{i=1}^n
\a_i$.
$W$ permutes $\D$ and fixes  $\d$; moreover this linear action on $V$ is
equivalent to an affine action on the subspace
$V^0:=\oplus_{i=1}^{n-1}\Bbb C\a_i$; in this equivalence $W$ maps
isomorphically to the semidirect product of $S_{n}$ with a group of "translations" (see \cite{K},
Prop. 6.5). Roots can be explicitly described as follows:
$$\eqalign{
\D=\pm\big(&\{\a_i+\ldots+\a_j+k\d\mid 1\leq i\leq j\leq n-1,\ k\in\Bbb
Z_+\}\cup
\cr
 &\left\{-(\a_i+\ldots+\a_j)+h\d\mid 1\leq i\leq j\leq n-1,\ h\in\Bbb
N\right\}\big).
}$$

For $\pi\in\Sn$ introduce the set 
$$R_\pi:=\{\a\in\Dp\mid \pi(\a)\in\D^-\}.$$
It is well known (see e.g. \cite{H}, \S1.7) that if $\sr$ is a reduced expression of $\pi\in\Sn$,
then
$$R_\pi=\{\a_{i_r},s_{i_r}(\a_{i_{r-1}}),s_{i_r}s_{i_{r-1}}(\a_{i_{r-2}}),\ldots,s_{i_r}\ldots
s_{i_2}(\a_{i_1})\}.$$
\proclaim{Theorem 1}(\cite{P})\footnote{In \cite{P} the theorem is stated for subsets of positive
roots in a finite crystallographic root system; however it obviously holds for {\it finite} subsets
of roots in the affine case.} A
finite subset
$L\subset
\Dp$ is of the form
$R_\pi$ for some
$\pi\in\Sn$ if and only if it satisfies the following conditions:\roster
\item If $\l,\mu\in L$ and $\l+\mu\in\D$, then $\l+\mu\in L$.
\item If $\l+\mu\in L, \ \l,\mu\in\Dp$, then $\l\in L$ or $\mu\in L$.
\endroster
Moreover, $R_\phi=R_\psi$ if and only if $\phi=\psi$.\endproclaim
\smallskip
We will need in the following the explicit description of 
 the action of $\pi\in\Sn$ on $\D$ in the permutation realization.
 Suppose $\a\in\Dp$; then $\a$ is of the form 
$\a_i+\ldots+\a_{j}+k\d$ or of the form  $-(\a_i+\ldots+\a_{j})+h\d$ for some integers
$1\leq i\leq j<n,\,k\geq 0, h\geq 1$. Let $q_i,r_i,i=1,2$ be the unique integers such that 
$\pi(i)=q_1n+r_1,\
\pi(j+1)=q_2n+r_2,\ (q_1,q_2\in\Bbb Z, 0< r_i\leq n,\,i=1,2)$. Recall from \cite{BB}, \S3,
that $\pi(i)\equiv\pi(j)\ mod\,n \Leftrightarrow i\equiv j\ mod\,n$; so we can define
$$\pi(\a_i+\ldots+\a_{j}+k\d)= (\a_{1}+\ldots+\a_{r_2-1})
-(\a_{1}+\ldots+\a_{r_1-1})+(k-q_1+q_2)\d\tag 3 $$
$$\pi(-(\a_i+\ldots+\a_{j})+h\d)=(\a_{1}+\ldots+\a_{r_1-1})
-(\a_{1}+\ldots+\a_{r_2-1})+(h+q_1-q_2)\d\tag 4 $$
By a
straightforward verification, easily performed on generators using (1), (2), we get the following
result.
\proclaim{Proposition 2} The previous formulas define an  action of $\Sn$ on $\D$; this action
coincides with the reflection representation. 
\endproclaim\smallskip
 We finally recall the formula for the length function $\ell$ in $\Sn$, 
affording the minimal number of Coxeter generators occurring in an expression of an affine
permutation $\pi$; if square brackets
denote the integer part of a rational number, we have (cf. \cite{Shi}, Lemma 4.2.2):
$$ \ell(\pi)=\sum_{1\leq i< j\leq n}\vert \left[\frac{\pi(j)-\pi(i)}{n}\right]\vert.\tag5$$

\par\newpage
\heading \S3 Affine permutations, inversion multigraphs and shifted tableaux \endheading
\bigskip
Let $\Cal G_n$ denote the set of weighted oriented graphs having $\{1,\ldots,n\}$ as set of vertices;
let then $A_G$ denote the set of oriented edges of an element $G\in \Cal G_n$; if an edge 
$x\in A_G$ starts from the vertex $i$ and ends in the vertex $j$ we will denote it by $i\to j$;
the corresponding weight will be denoted by $t(i,j)$ or $t(x)$.\par An element $G\in \Cal G_n$ is
characterized by $A_G$ and the set of weights $\Cal W_G=\{t(i,j)\mid i\ne j\}$ (we enclose $0$
among the weights, so
$\Cal W_G$ is a set consisting  exactly of
$n(n-1)$ non-negative integer numbers).
\par
 Recall from \cite{BB} the definition
of  the {\it inversion multigraph} $I_\pi$ relative to\break 
$\pi\in\Sn$.
$I_\pi$ is the element of $\Cal G_n$ which has an edge of multiplicity
$\vert\left[\frac{\pi(j)-\pi(i)}{n}\right]\vert$ between $i$ and
$j$, directed towards the node with highest $\pi$-value, for all $1\leq i< j\leq n$; edges of
multiplicity zero are deleted. The figure below shows the inversion multigraph associated to  
$\pi=[4,5,-1,2]\in\tilde S_4$:
\figura{5.5truein}{4truecm}{graph2}
  Note that , by formula (5), $\ell(\pi)=\sum_{x\in
A_{I_\pi}}t(x)$. Moreover, it is shown in \cite{BB} that $I_\pi$ determines $\pi$; the problem
of classifying inversion multigraphs is left open. In other words the  map
$\Lambda_n:\Sn\to\Cal G_n$ defined by $\Lambda_n(\pi)=I_\pi$
is injective and we have to find its image. By the very definitions it is
clear that $Im\,(\Lambda_n)\subseteq \Cal G'_n$ where
$$\Cal G'_n:=\{G\in \Cal G_n\mid \forall\, i,j\in \{1,\ldots,n\},\, i\ne j,\
t(i,j)\ne 0\Longrightarrow t(j,i)=0\}.$$ \indent
{From} this remark it follows that we may organize the data appearing in an inversion
multigraph in a slightly different way, which is more convenient for our goals. Let $\Cal T_n$ denote
the set of shifted tableaux of shape
$\l=(n-1,n-2,\ldots,1)$; we associate to a given element $\pi\in\Sn$ a
shifted tableau of shape $\l$,
 $T_\pi=(\t )_{(i,j)\in I_n},\,I_n:=\{(i,j)\mid 1\leq i\leq j\leq n-1\}$, in
the following way:
$$\t:=\left[\frac{\pi(j+1)-\pi(i)}{n}\right].$$
For instance, if  $\pi=[4,5,-1,2]\in\tilde S_4$, then
$T_\pi=\matrix 0&-2&-1\\ \ &-2&-1\\ \ &\ &0\endmatrix.$\par
It is clear how to recover $I_\pi$ from $T_\pi$ and vice versa; we will prove that
$$R_\pi=\{\a_1+\a_2,\a_1+\a_2+\d,\a_1+\a_2+\a_3,\a_2,\a_2+\d,\a_2+\a_3\}.$$
So, roughly speaking, the  coefficient $\tau_\pi(i,j)$ in $T_\pi$ gives, according to its
sign the number of roots of the string $\a_i+\ldots+\a_{j}+k\d$  (or  of  the string
$-(\a_i+\ldots+\a_{j})+k\d$) belonging to $R_\pi$.
Recall that, using the algorithm described in \cite{P}, we may get a reduced expression of $\pi$
from the knowledge of $R_\pi$; in the example $\pi=s_3s_4s_2s_1s_3s_2$.\par\smallskip Set now, for
$T\in \Cal T_n$:
$$\eqalign{N_T:=\bigcup_{(i,j)\in I_n}\big(
&\{\a_i+\ldots+\a_j+k\d\mid \tp<0,\ 0\leq k< -\tp\}\cup\cr
&\{-(\a_i+\ldots+\a_j)+h\d\mid \tp>0,\ 1\leq h\leq \tp\}\big).}$$
The following proposition, combined with the last statement of theorem 2, affords a
proof of the injectivity of the map $\Lambda_n$; the proposition could be however deduced from the
results  of \cite{BB}, \S3-4.
\proclaim{Proposition 3} $R_\pi=N_{T_{\pi}}$.\endproclaim
\demo{Proof} 
For $(i,j)\in I_n$ introduce
the sets
$$\eqalign{J^+_{ij}:&=\{\a_i+\ldots+\a_{j}+k\d\mid k\geq 0\}\cr
J^-_{ij}:&=\{-(\a_i+\ldots+\a_{j})+h\d\mid h\geq 1\}.}$$
\indent We want to calculate the  roots belonging to $(J^+_{ij}\cup J^-_{ij})\cap R_\pi$.\newline
Suppose $\pi(i)=q_1n+r_1,\
\pi(j+1)=q_2n+r_2,\ q_1,q_2\in\Bbb Z, 0< r_i\leq n,\,i=1,2$ and $a\in J_{ij}^+,\,\tilde a\in
J_{ij}^-$; then formulas (4), (5) imply the following relations:
$$r_1>r_2\implies\cases
\pi(a)\in\D^-\Leftrightarrow k\leq q_1-q_2\\
\pi(\tilde a)\in\D^-\Leftrightarrow h< q_2-q_1\endcases$$
$$r_1<r_2\implies\cases
\pi(a)\in\D^-\Leftrightarrow k< q_1-q_2\\
\pi(\tilde a)\in\D^-\Leftrightarrow h\leq q_2-q_1\endcases$$
These relations clearly allow to determine $R_\pi$. In particular at most one of the
two strings $J_{ij}^+,\,J_{ij}^-$ has non-empty intersection with $R_\pi$;
moreover:
$$Card\left((J^+_{ij}\cup J^-_{ij})\cap R_\pi\right)=
\cases \vert q_2-q_1-1\vert &\text{if\ } r_1>r_2\\
\vert q_2-q_1\vert&\text{if\ } r_1<r_2.\endcases $$

Now observe that
$$\tau_\pi(i,j)\!=\!
\left[\frac{\pi(j+1)-\pi(i)}{n}\right]\!=\!\left[\frac{(q_2-q_1)n+r_2-r_1}{n}\right]
\!=\!\cases \! q_2-q_1-1 &\text{if\ } r_1>r_2\\
\! q_2-q_1&\text{if\ } r_1<r_2.\endcases $$
{From} this and the previous remarks we can easily deduce that $R_\pi=N_{T_{\pi}}$.
\endemo
\medskip\par\newpage
\heading\S4 The main result\endheading
\bigskip
We want to characterize the image of the map $\Lambda_n$; we have to translate conditions (1) and (2)
of the theorem of section 2 into the combinatorics of inversion multigraphs.
For $i,j\in\{1,\ldots,n\},\, i\ne j$ set:
$$\Cal C_{i\to j}:=\{(i\to k,k\to j)\mid k\ne i,j\}.$$
$$\tilde t(i,j):=\cases t(i,j)\quad &\text{\sl if\ }i<j\\
t(i,j)-1\quad  &\text{\sl if\ }i>j\endcases$$
Now we can state our main theorem; we say for shortness that an (oriented) edge $i\to j$ is {\it
positive} if
$i<j$, {\it negative} otherwise.
\proclaim{Theorem 4} A multigraph $G\in\Cal G'_n$ belongs to $Im\,(\Lambda_n)$ if and only if it
satisfies the following conditions:\newline
{\bf(I)}\ $\forall\, i,j\in \{1,\ldots,n\},\, i\ne j,\,\forall\,(x,y)\in \Cal C_{i\to j}\cap 
\left( A_G\times A_G\right)$
$$\tilde t(i,j)\geq \tilde t(x)+ \tilde t(y).$$
{\bf(II)}\ $\forall\,x\in A_G,\ \forall\, (a,b)\in\Cal C_x,\ \forall\,(m,r):\,m+r=\tilde t(x)$
$$\tilde t(a)\geq m\ \text{\sl or}\ \tilde t(b)\geq r.$$
Here $m$ (resp. $r$) ranges over $\Bbb N$ or $\Bbb Z_+$ according to whether $a$ (resp. $b$) is
positive or negative.\endproclaim
\noindent {\it Remark. } Condition (II) must be interpreted as follows. For each edge $x=i\to j$ in
$G$, we have to consider all the paths starting from $i$ and ending in $j$ consisting of two edges,
which do not necessarily belong to $A_G$ -- in such a case we conventionally assign to them the
weight $0$ --; then the stated weight condition should be verified.
\demo{Proof} We want first to translate conditions 
  (I), (II) on
a multigraph  $G\in\Cal G'_n$ into analogous conditions on the shifted tableaux
$T=\left(\tau(i,j)\right)\in
\Cal T_n$ which encodes $G$ as previously explained.\par
Suppose for instance $(i,j)\in I_n,\,i\leq k<j$ and 
consider the relation
$$(i\to k+1,k+1\to j+1)\in (A_G\times A_G)\implies \tilde t(i,j+1)\geq \tilde t(i,k+1) + \tilde
t(k+1,j+1).\eqno(*)$$ Remark that the vertices $i,k+1$ and  $k+1,j+1$ are joined by an edge if and
only if\break 
$ t(i,k+1)\ne 0,\ t(k+1,j+1)\ne 0$;  considering the  orientation of edges, the previous relations
are equivalent to $\tau(i,k)>0,\ \tau(k+1,j)>0$. Therefore $(*)$ is equivalent to 
$$\tau(i,k)>0,\ \tau(k+1,j)>0\ \implies\ \tau(i,j)\geq \tau(i,k)+ \tau(k+1,j).$$
It is not hard to check that the following set of conditions is equivalent to (I), (II).\newline
 {\bf(A)}\
$\forall\, (i,j)\in I_n,\,\forall\,h,k,p:\ 1\leq h<i\leq k<j<p\leq n-1$
$$\alignat4
&\tau(i,k)>0,\ &&\tau(k+1,j)>0\ &&\implies\ &&\tau(i,j)\geq \tau(i,k)+ \tau(k+1,j)\\
&\tau(i,k)<0,\ &&\tau(k+1,j)<0\ &&\implies\ &&\tau(i,j)\leq \tau(i,k)+ \tau(k+1,j)+1\\
&\tau(h,j)>0,\ &&\tau(h,i-1)<0\ &&\implies\ &&\tau(i,j)\geq \tau(h,j)- \tau(h,i-1)-1\\
&\tau(h,j)<0,\ &&\tau(h,i-1)>0\ &&\implies\ &&\tau(i,j)\leq \tau(h,j)- \tau(h,i-1)\\
&\tau(i,p)>0,\ &&\tau(j+1,p)<0\ &&\implies\ &&\tau(i,j)\geq \tau(i,p)- \tau(j+1,p)-1\\
&\tau(i,p)<0,\ &&\tau(j+1,p)>0\ &&\implies\ &&\tau(i,j)\leq \tau(i,p)- \tau(j+1,p).
\endalignat$$
{\bf(B)}\ If $\tau(i,j)<0$, set $s:=-\tau(i,j)
-1$; then the following relations  hold:
$$\alignat4
&\forall\,k:i\leq k<j,\ \forall\,(m,r)\in \Bbb Z_+\times \Bbb Z_+:m+r=s
&&\tau(i,k)<-m\ &&\text{\sl or}\ &&\tau(k+1,j)<\!\!-r\\
&\forall\,h:1\leq h<i,\ \forall\,(m,r)\in \Bbb Z_+\times \Bbb N:m+r=s
&&\tau(h,j)<-m\ &&\text{\sl or}\ &&\tau(h,i-1)\geq r\\
&\forall\,p:j< p\leq n-1,\forall\,(m,r)\in \Bbb Z_+\times \Bbb N\!:m+r=s\ \
&&\tau(i,p)<-m\,&&\text{\sl or}\ &&\tau(j+1,p)\geq r.\endalignat
$$
{\bf(B')}\ If $\tau(i,j)>0$, set $s:=\tau(i,j)$;  then the following
relations  hold:
$$\alignat4
&\forall\,k:i\leq k<j,\ \forall\,(m,r)\in \Bbb N\times \Bbb N:m+r=s
&&\tau(i,k)\geq m\ &&\text{\sl or}\ &&\tau(k+1,j)\geq r\\
&\forall\,h:1\leq h<i,\ \forall\,(m,r)\in \Bbb N\times \Bbb Z_+:m+r=s
&&\tau(h,j)\geq m\ &&\text{\sl or}\ &&\tau(h,i-1)<- r\\
&\forall\,p:j< p\leq n-1,\,\forall\,(m,r)\in \Bbb N\times \Bbb Z_+:m+r=s\ \
&&\tau(i,p)\geq m\,&&\text{\sl or}\ &&\tau(j+1,p)<- r\!.\endalignat
$$ 
On the other hand conditions (A) and (B), (B') correspond to relations (1) and (2) of the theorem
of section
2 respectively. Let us explain how to recover the former set of relations from the latter.\par
Remark that, given an affine root $(\a_i+\ldots+\a_j)+s\d\in\Dp,\,s\in\Bbb Z_+$, its  decompositions
into the sum of two positive roots are only the following ones:
\par
$$
\alignat3
&(\a_i+\ldots+\a_k+m\d)+(\a_{k+1}+\ldots +\a_j+r\d),\  & &(m,r)\in  \Bbb Z_+\times
\Bbb Z_+\!:\, & &m+r=s\\
&(\a_h+\ldots +\a_j+m\d)+(-(\a_h+\ldots +\a_{i-1})+r\d),\  & &(m,r)\in \Bbb
Z_+\times
\Bbb N:& &m+r=s\\
&(\a_i+\ldots +\a_p+m\d)+(-(\a_{j+1}+\ldots +\a_p)+r\d),\  & &(m,r)\in \Bbb
Z_+\times
\Bbb N:& &m+r=s\endalignat
$$
where $i\leq k< j,\,1\leq h< i,\,j<p\leq n-1$.
The analogous relations for a root of the form $-(\a_i+\ldots +\a_j)+s\d\in\Dp,\,s\in\Bbb N$ are the
following:
$$
\alignat3
&(-(\a_i+\ldots +\a_k)+m\d)+(-(\a_{k+1}+\ldots +\a_j)+r\d),\  & &(m,r)\in  \Bbb
N\times
\Bbb N:& &m+r=s\\
&(-(\a_h+\ldots +\a_j)+m\d)+(\a_h+\ldots +\a_{i-1}+r\d),\  & &(m,r)\in  \Bbb
N\times
\Bbb Z_+\!:\,& &m+r=s\\
&(-(\a_i+\ldots +\a_p)+m\d)+(\a_{j+1}+\ldots +\a_p+r\d),\  & &(m,r)\in \Bbb
N\times
\Bbb Z_+\!:\,& &m+r=s\endalignat
$$
($i\leq k< j,\,1\leq h< i,\,j<p\leq n-1$).\par
Note further that the sum of two positive roots is again a root if and only if  we are in one of the
previous cases (for some $(i,j)\in I_n$).\par
Now assume $T=T_\pi$ for $\pi\in\Sn$.  If, for instance, $\tau(i,k)>0,\ \tau(k+1,j)>0$ then, by
proposition 3, the roots
$-(\a_i+\ldots +\a_k)+\tau(i,k)\d,\,-(\a_{k+1}+\ldots +\a_j)+\tau(k+1,j)\d$ belong to $R_\pi$. So (1) forces
also $(-(\a_i+\ldots +\a_j)+(\tau(i,k)+\tau(k+1,j))\d)$ to belong to $R_\pi$. Therefore, again by
proposition 3, the relation 
$\tau(i,j)\geq \tau(i,k)+ \tau(k+1,j)$
must hold. Small variations of this argument imply the other relations in (A).\par
Condition (2) means that, if a root $x=-(\a_i+\ldots +\a_j)+k\d$ (resp.
$y=\a_i+\ldots +\a_j+k\d$)
  belongs to $R_\pi$, then for each
decomposition of $x$ (resp. $y$) into the sum of two positive roots at least one component belongs to
$R_\pi$; it is easy to prove that it suffices to check this property when $k$ is the greatest
integer such that a root of the form
$-(\a_i+\ldots +\a_j)+r\d$  or $\a_i+\ldots +\a_j+r\d$ belongs to $R_\pi$:
so if
$\tau(i,j)<0$ (resp.
$\tau(i,j)>0$) then
conditions (B) (resp. (B')) must hold.
We have finally proved that inversion multigraphs satisfy the conditions in the statement of the
theorem; on the other hand we claim that, if a multigraph $G$ verifies (I) and (II) and 
$T$ is the associated shifted tableau, then
$N_T$ is a compatible set. Let us verify condition (1) of theorem 2; suppose that 
$\a_i+\ldots+\a_k+r\d,\,\a_{k+1}+\ldots+\a_j+s\d$\newline
$1\leq i\leq k< j\leq n-1,\ r,s\in\Bbb Z_+$ belong to $N_T$: we have to prove that
$\a_i+\ldots+\a_j+(r+s)\d\in N_T$. We know that $r<-\tau(i,k),\ s<-\tau(k+1,j)$: then condition (A)
(which is equivalent to (I)) implies
$$\tau(i,j)\leq\tau(i,k)+\tau(k+1,j)+1<-r-s$$
and in turn we get $\a_i+\ldots+\a_j+(r+s)\d\in N_T$. The other cases relative to condition (1)
and condition (2) can be verified in a similar way.\par
Since $N_T$ is compatible,  there exists an (unique) element $\pi\in\Sn$ such that
$N_T=R_\pi$. Therefore $\Lambda_n(\pi)=G$ and the proof is completed.\endemo
\medskip
\noindent{\it Examples.} Consider the following multigraphs:
\figura{15truecm}{1.7truecm}{graph3}
\noindent The first satisfies the conditions of theorem 4: in fact it encodes the affine
permutation 
$\pi=[4,2,0]$. The other two graphs are not associated to affine permutations since they satisfy
exactly one of the conditions in the previous theorem (the second does not satisfy (I) whereas the
third does not satisfy (II)\ ).
\smallskip
\par\newpage
\Refs \widestnumber\key {BB}\smallskip

\ref\key{BB}\by A. Bj\"orner, F. Brenti \paper Affine permutations of type $A$
\yr1995
\vol3(2)
\jour The electronic journal of combinatorics\endref

\ref\key{H}\by J.E. Humphreys \book Reflection groups and Coxeter groups \publ Cambridge
University Press\publaddr Cambridge\yr 1990\endref

\ref\key{K}\by V.G. Kac \book Infinite Dimensional Lie Algebras \publ Birkh\"auser\publaddr
Boston\yr 1983\endref

\ref\key{L}\by G. Lusztig \paper Some examples of square integrable
representations of semisimple $p$-adic groups\pages99--111
\yr1983\vol277 \jour Trans. Amer. Math. Soc.\endref

\ref\key{P}\by P. Papi \paper A characterization of a special ordering in a root
system\pages661--665 \yr1994\vol120 \jour Proc. Amer. Math. Soc. \endref

\ref\key{Shi}\by Shi Jian-yi \book The Kazdhan-Lusztig cells in certain affine Weyl groups\yr
1986, Lect. Notes in Math. 1179 \publ Springer\publaddr Berlin \endref


\endRefs
 
\enddocument\end