# How to get the weak order out of a digraph ?

François Viard

► To cite this version:

François Viard. How to get the weak order out of a digraph?. 27th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2015), Jul 2015, Daejeon, South Korea. pp.559-570, 10.46298/dmtcs.2538 . hal-01337793

HAL Id: hal-01337793

https://hal.science/hal-01337793

Submitted on 27 Jun 2016

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# How to get the weak order out of a digraph ?

François Viard¹†

¹Université Lyon 1, Institut Camille Jordan, UMR 5208 du CNRS, 69622 Villeurbanne, France

**Abstract.** We construct a poset from a simple acyclic digraph together with a valuation on its vertices, and we compute the values of its Möbius function. We show that the weak order on Coxeter groups $A_{n-1}$, $B_n$, $\tilde{A}_n$, and the flag weak order on the wreath product $Z_r \bowtie S_n$ introduced by Adin, Brenti and Roichman (2012), are special instances of our construction. We conclude by briefly explaining how to use our work to define quasi-symmetric functions, with a special emphasis on the $A_{n-1}$ case, in which case we obtain the classical Stanley symmetric function.

**Résumé.** On construit une famille d'ensembles ordonnés à partir d'un graphe orienté, simple et acyclique munit d'une valuation sur ses sommets, puis on calcule les valeurs de leur fonction de Möbius respective. On montre que l'ordre faible sur les groupes de Coxeter $A_{n-1}$, $B_n$, $\tilde{A}_n$, ainsi qu'une variante de l'ordre faible sur les produits en couronne $Z_r \bowtie S_n$ introduit par Adin, Brenti et Roichman (2012), sont des cas particuliers de cette construction. On conclura en expliquant brièvement comment ce travail peut-être utilisé pour définir des fonction quasi-symétriques, en insistant sur l'exemple de l'ordre faible sur $A_{n-1}$, où l'on obtient les séries de Stanley classiques.

**Keywords:** Tableaux, digraphs, posets, Coxeter groups, weak order, reduced decompositions.

# 1 Introduction

A *tableau* is a map from a finite subset $S \subset \mathbb{N} \times \mathbb{N}$ to $\mathbb{N}$. Some families of tableaux are very classical in combinatorics and algebra, such as *standard* and *semi-standard* tableaux which play a fundamental role in the study of symmetric functions and representation theory.

In [4], Edelman and Greene introduced a new family of tableaux called *balanced* and exhibited a beautiful connection between them and the theory of reduced decompositions in the symmetric groups. This study has been extended by Fomin *et al*. in [5] by considering *balanced labellings* of the *Rothe diagram* of a permutation. Those labelled diagrams are a convenient way to visualise both the inversion set of a permutation and its associated set of reduced decompositions, and can be interpreted as a generalization of standard Young tableaux. Moreover, they introduced *column-strict balanced labellings* which generalize the notion of semi-standard Young tableaux. Column-strict labellings of the diagram of a permutation $\sigma$ yield the Stanley symmetric function $F_\sigma$ (introduced in [7]) in the same way semi-standard tableaux yield *Schur functions*. This approach has been generalized to the affine *Coxeter group* $\tilde{A}_n$ by Yun and Yoo in [10], and leads to a combinatorial description in terms of tableaux of the *affine Stanley symmetric function* introduced by Lam in [6].

<footnote>†Email: Viard@math.univ-lyon1.fr.</footnote>
The main purpose of this paper is to introduce a new family of posets, defined from a simple acyclic digraph together with a valuation on its vertices, by using an iterative process which peels the graph vertex by vertex. Then, we exhibit some general properties of these posets: we show that they are complete meet semi-lattice, and we give an explicit formula to compute the values of their Möbius function. Then we give some examples of classical posets which are special instances of this construction, namely the weak order on $A_{n-1}$, $B_n$, $\tilde{A}_n$, the flag weak order on $\mathbb{Z}_r \ltimes S_n$ introduced by Adin, Brenti and Roichman (2012, [1]), the tree order of any tree, and the up-set (resp. down-set) lattice of any finite poset. In the $A_{n-1}$ case we explain how this description naturally leads to associate a family of tableaux to each element of $A_{n-1}$, and we explain how they can be used to find the result of [5] again. To finish we mention that a similar method can be applied to the $\tilde{A}_n$ case, and we briefly mention how these combinatorial consequences can be generalized to the other examples.

## 2 Definition of the family of posets

We begin with some standard definitions about poset theory and graph theory. A poset is a couple $\mathcal{P} = (P, \leq)$, where $P$ is a set and $\leq$ is a binary relation which is reflexive, antisymmetric, and transitive. A poset $\mathcal{P}$ is called a complete meet (resp. join) semi-lattice if and only if every subset $S$ of $\mathcal{P}$ has an infimum (resp. supremum) in $\mathcal{P}$, i.e. there exists $z$ in $\mathcal{P}$ such that if $y \in \mathcal{P}$ and $y \leq x$ (resp. $x \leq y$) for all $x \in S$, then $y \leq z$ (resp. $z \leq y$). If $\mathcal{P}$ is both a complete join and meet semi-lattice, then we say that $\mathcal{P}$ is a complete lattice. A lower set of $\mathcal{P}$ is a subset $A$ of $\mathcal{P}$ such that for all $x \in A$ and $y$ in $P$, if $y \leq x$ then $y \in A$. It is classical that the lower sets of $\mathcal{P}$ ordered by inclusion is a lattice (for more details about poset theory, see [8]).

A simple digraph is a couple $G = (V, E)$, where $V$ is the set of vertices of $G$, and $E$ is a subset of $V \times V$ called the set of arcs of $G$. A cycle of $G$ is a finite sequence $x_1, \dots, x_n$ of vertices of $G$ such that $(x_i, x_{i+1}) \in E$ for all $i \in \mathbb{N}$, where the indices are taken modulo $n$. A graph $G$ is called acyclic if it does not have any cycle. On each vertex $x$ of $G$, we define the statistic

$$d^+(x) = |\{y \mid (x, y) \in E\}|,$$

called the out-degree of $x$, and which is possibly infinite.

### 2.1 General idea of the construction

We first present a suitable method to construct all lower sets of a finite poset $\mathcal{P} = (P, \leq)$, using the notion of linear extension of $\mathcal{P}$. A linear extension of $\mathcal{P}$ is an injective sequence $[a_1, \dots, a_n]$ (with $|P| = n$) of elements of $P$ such that: if $a_i \leq a_j$ in $\mathcal{P}$, then $i \leq j$. It is classical that $A \subseteq P$ is a lower set of $\mathcal{P}$ if and only if there exists $[a_1, \dots, a_n]$ a linear extension of $\mathcal{P}$ and $1 \leq k \leq n$ such that $A = \{a_1, \dots, a_k\}$ (see [8]). Then to construct all the lower sets of $\mathcal{P}$, we just have to construct all the linear extensions of $\mathcal{P}$, and this can easily be done recursively thanks to the following iterative method.

Since $\mathcal{P}$ is finite, there exists $a_1$ in $\mathcal{P}$ which is a minimum, that is if $x \leq a_1$ in $\mathcal{P}$, then $x = a_1$. Set $\mathcal{P}_2 = (P \setminus \{a_1\}, \leq)$ the finite poset obtained by suppressing $a_1$ in $\mathcal{P}$. Then there exists $a_2$ in $\mathcal{P}_2$ which is a minimum. Then we can consider the poset $\mathcal{P}_3$ obtained by suppressing $a_2$ in $\mathcal{P}_2$, and so on. At the end we obtain an injective sequence $[a_1, \dots, a_n]$ of elements of $\mathcal{P}$. By construction, this sequence is a linear extension of $\mathcal{P}$. Furthermore, one can easily prove by induction that all the linear extensions of $\mathcal{P}$ can be obtained by this way.
<figure><img src="image_2.png" /></figure>

## 3 General properties of $\mathcal{P}(\mathcal{G})$

In this section we give the main properties of the poset $\mathcal{P}(\mathcal{G})$. We start by announcing our results, and the scheme of the proofs will be given in the sequel.

**Theorem 3.1** For all $\mathcal{G} = (G, \theta)$, the poset $\mathcal{P}(\mathcal{G})$ is a graded complete meet semi-lattice, and its rank function is $\rho: A \to |A|$. Moreover, when the underlying graph $G$ is finite, $\mathcal{P}(\mathcal{G})$ is a complete lattice.

In the context of these posets, it is possible to give an explicit formula for the values of their Möbius function. Recall that the Möbius function on a graded poset $\mathcal{P} = (P, \leq)$ is the application $\mu: P^2 \to \mathbb{N}$ recursively defined by $\mu(x, x) = 1$ for all $x \in P$, and $\sum_{x \leq z \leq y} \mu(x, z) = 0$ for all $(x, y) \in P^2$.

For the sake of clarity, we give the formula only for the couples of the form $(\emptyset, A)$, $A \in \mathcal{IS}(\mathcal{G})$, but a similar one can be stated for all couples in $\mathcal{IS}(\mathcal{G})$.

**Theorem 3.2** *Set $A \in \mathcal{IS}(\mathcal{G})$. We denote $\mathcal{N}(A) = \{x \in A \mid \theta_x = 0\}$, and $\mathcal{F}(A) = \{x \in A \mid A \setminus \{x\} \in \mathcal{IS}(\mathcal{G})\}$. Then we have the two following possibilities:*

1. if $\mathcal{F}(A) = \mathcal{N}(A)$, then $\mu(\emptyset, A) = (-1)^{|\mathcal{N}(A)|}$;

2. otherwise, $\mu(\emptyset, A) = 0$.

### 3.1 Proof of Theorem 3.1

The proof of this theorem has to be divided into several steps. The first one is a characterization of the elements of $\mathcal{IS}(\mathcal{G})$.

**Proposition 3.1.1** *Set $A$ a finite subset of vertices of $G$. We have that $A \in \mathcal{IS}(\mathcal{G})$ if and only if the two following conditions are satisfied:*

(1) for all $x \in A$, $\theta_x \leq |\{y \mid y \in A \text{ and } (x, y) \in E\}|$;

(2) for all $x \in V \setminus A$, $\theta_x \geq |\{y \mid y \in A \text{ and } (x, y) \in E\}|$.
**Proof:** The proof of the necessary condition consists in a straightforward verification using the construction of a peeling sequence. The reverse direction is proved by induction on $|A|$: essentially, the fact that $G$ is acyclic together with condition (1) and (2) imply that there exists $x$ in $A$ which is erasable in $G$. Then we begin the peeling process by picking this vertex and we set $G'$ the obtained digraph and OCV. One can show that $A \setminus \{x\}$ satisfies conditions (1) and (2) in $G'$, and the induction hypothesis applies. Hence $A \setminus \{x\} \in \text{IS}(G')$ and this concludes the proof. $\square$

The next proposition implies immediately that $\mathcal{P}(G)$ is a graded poset with rank function $\rho: A \mapsto |A|$.

**Proposition 3.1.2** *Set A and B two elements of $\mathcal{IS}(G)$, and denote $k = |A|$ and $q = |B|$. If $A \subseteq B$, then there exists $L = [x_1, x_2, \dots] \in \mathcal{PS}(G)$ such that $A = \{x_1, \dots, x_k\}$ and $B = \{x_1, \dots, x_q\}$.*

**Proof:** We suppose that $k < q$. We construct explicitly the sequence $L$ as follows. Since $A \in \text{IS}(G)$, we can start by picking the first $k$ elements $x_1, \dots, x_k$ in $A$. Set $G' = (G', \theta')$ obtained from $G$ after this procedure. Thus $B \setminus A$ is a finite subset of vertices of $G'$, moreover $B \setminus A$ satisfy the conditions of Proposition 3.1.1, hence $B \setminus A \in \text{IS}(G')$. So there exists $L' = [x_{k+1}, \dots, x_q, \dots] \in \text{PS}(G')$ such that $B \setminus A = \{x_{k+1}, \dots, x_q\}$. At the end if we concatenate the sequences $[x_1, \dots, x_k]$ and $L'$, we obtain $L = [x_1, x_2, \dots]$ which is a peeling sequence of $G$ by construction, and satisfies all the claimed properties. $\square$

We conclude by an explicit construction of the infimum (also called the *meet*) of a set $S \subseteq \text{IS}(G)$. We start by a useful lemma, which is an immediate consequence of Proposition 3.1.1.

**Lemma 3.1.1** *Set $S \subseteq \text{IS}(G)$, and denote $X := \bigcap_{A \in S} A$. If there exists $x \in X$ such that $\theta_x = 0$, then there exists $z \in X$ which is erasable in $G$.*

**Construction of the meet.** We consider $S$ and $X$ as defined in the previous lemma, and we construct a set $C \in \text{IS}(G)$ as follows. If for all $x \in X$, $\theta_x \neq 0$, we set $C = \emptyset$. Otherwise, let $z_1 \in X$ be an erasable vertex of $G$. We start the peeling process by picking this vertex and we denote $G_2 = (G_2, \theta^2)$ the obtained graph and OCV. Then for all $A \in S$, $A \setminus \{z_1\} \in \text{IS}(G_2)$, so we can again apply Lemma 3.1.1 to $X \setminus \{z_1\}$ seen as a subset of vertices of $G_2$. If for all $x \in X \setminus \{z_1\}$, $\theta_x^2 \neq 0$ we set $C = \{z_1\}$; otherwise, let $z_2 \in X \setminus \{z_1\}$ be an erasable vertex of $G_2$ and we perform the peeling process by picking this vertex. We repeat this procedure until there is not any erasable vertex left (this process always ends, since $X$ is finite), and we set $C$ the obtained set. By construction, $C \in \text{IS}(G)$.

At first glance, this set $C$ seems to depend heavily on the choices of vertices made at each step of its construction. The next proposition shows that it is not the case.

**Proposition 3.1.3** *Set $U \in \text{IS}(G)$. If $U \subseteq X$, then $U \subseteq C$.*

**Proof:** Since $U \in \text{IS}(G)$, there exists $L = [x_1, x_2, \dots] \in \text{PS}(G)$ and $k \in \mathbb{N}^*$ such that $U = \{x_1, \dots, x_k\}$. Assume that $U \not\subseteq C$ and set $j \ge 1$ minimal such that $x_j \notin C$. Then by construction of $C$ and Lemma 3.1.1, $x_j$ has to be in $C$, which is a contradiction. $\square$

Since $C \subseteq X$ by construction, the previous proposition leads to the following corollary.

**Corollary 3.1.1** *The set $C$ is the infimum of $S$.*
When the underlying graph $G$ is finite, we obviously have that $V$, the set of all the vertices of $G$, satisfies the conditions of Proposition 3.1.1, hence $V \in \mathcal{IS}(G)$, and the poset $\mathcal{P}(G)$ is bounded. Since it is a meet semi-lattice, then $\mathcal{P}(G)$ is a lattice, and this concludes the proof of Theorem 3.1.

## 3.2 Proof of Theorem 3.2

The proof of this formula is purely combinatorial, and is based on the well-known inclusion-exclusion principle (see [8]). For all $B \in \mathcal{IS}(G)$, we denote $[\emptyset, B] = \{U \in \mathcal{IS}(G) | \emptyset \subseteq U \subseteq B\}$. Set $A, \mathcal{N}(A)$ and $\mathcal{F}(A)$ as defined in Theorem 3.2. For all $S \subseteq \mathcal{F}(A)$, we denote $A_S$ the infimum of $\{A \setminus \{x\} | x \in S\} \subseteq \mathcal{IS}(G)$. We have the following lemma.

**Lemma 3.2.1** Set $S \subseteq \mathcal{F}(A)$. We have that $A_S \neq \emptyset$ if and only if $\mathcal{N}(A) \not\subseteq S$.

**Proof:** We have that the intersection of all the $A \setminus \{x\}$, for $x$ in $S$, is equal to $A \setminus S$. By Lemma 3.1.1, if $\mathcal{N}(A) \not\subseteq S$ then there exists $z \in A \setminus S$ which is erasable in $G$, so the infimum of $\{A \setminus \{x\} | x \in S\}$ is not $\emptyset$. The reciprocal is based on similar arguments. $\square$

An immediate consequence of the meet semi-lattice structure of $\mathcal{P}(G)$ is that, for all $U$ and $V$ in $\mathcal{IS}(G)$, $[\emptyset, U] \cap [\emptyset, V] = [\emptyset, U \wedge V]$ where $U \wedge V$ is the infimum of $\{U, V\}$. This basic remark leads to the claimed formula: first, we obviously have

$$[\emptyset, A] \setminus \{A\} = \bigcup_{x \in \mathcal{F}(A)} [\emptyset, A_{\{x\}}].$$

Then, by the inclusion-exclusion principle we have that

$$|[\emptyset, A] \setminus \{A\}| = \sum_{\emptyset \neq S \subseteq \mathcal{F}(A)} (-1)^{|S|+1} \left| \bigcap_{x \in S} [\emptyset, A_{\{x\}}] \right| = \sum_{\emptyset \neq S \subseteq \mathcal{F}(A)} (-1)^{|S|+1} |[\emptyset, A_S]|.$$

Once applied to the Möbius function of $\mathcal{P}(G)$, this gives rise to the following identity:

$$\mu(\emptyset, A) = - \sum_{\emptyset \neq S \subseteq \mathcal{F}(A)} (-1)^{|S|+1} \sum_{B \in [\emptyset, A_S]} \mu(\emptyset, B). \quad (1)$$

By definition of the Möbius function, $\sum_{B \in [\emptyset, A_S]} \mu(\emptyset, B) = 1$ if $A_S = \emptyset$, and 0 otherwise. Hence by

Lemma 3.2.1, if $\mathcal{N}(A) \not\subseteq \mathcal{F}(A)$, then $\mu(\emptyset, A) = 0$. As a consequence, Equation (1) becomes

$$\mu(\emptyset, A) = - \sum_{\mathcal{N}(A) \subseteq S \subseteq \mathcal{F}(A)} (-1)^{|S|+1} = (-1)^{|\mathcal{N}(A)|} \sum_{S \subseteq \mathcal{F}(A) \setminus \mathcal{N}(A)} (-1)^{|S|} \quad (2)$$

$$= (-1)^{|\mathcal{N}(A)|} (1 - 1)^{|\mathcal{F}(A) \setminus \mathcal{N}(A)|}. \quad (3)$$

The claimed formula follows immediately.
# 4 Applications of this construction

Let $W$ be a Coxeter group with finite generating set $S$, and Coxeter matrix $M = (m_{st})_{s,t \in S}$. That is, $M$ is a symmetric matrix with $m_{ss} = 1$ and, for $s \neq t$, $m_{st} = m_{ts} \in \{2, 3, \dots\} \cup \{\infty\}$. The relations among the generators are of the form $(st)^{m_{st}} = 1$ if $m_{st} < \infty$. For $w \in W$ we denote by $\ell(w)$ the minimum length of any decomposition $w = s_1 \cdots s_l$ with $s_i \in S$. Such decompositions with minimum length are called reduced, and we denote by $\mathcal{R}(w)$ the set of all reduced decompositions of $w$.

This statistic $\ell$ on $W$ is the rank function of a poset structure $(W, \leq_R)$ called the (right) weak order on $W$, and which is defined as follows: we say that $w \leq_R \tau$ if and only if there exists $s_1, \dots, s_k$ in $S$ such that $\tau = \omega s_1 \cdots s_k$ and $\ell(\tau) = \ell(w) + k$. It is classical that $(W, \leq_R)$ is a complete meet semi-lattice when $W$ is infinite, a complete lattice when $W$ is finite, and that its Möbius function take values into $\{\pm 1, 0\}$ (see [2] and [3]). Hence, it is natural to look for an interpretation of the weak order through the theory developed in the previous section. Indeed, we can provide such a description in some cases. In the next theorem, we give a list of posets which admit such an interpretation.

**Theorem 4.1** For each poset $\mathcal{P}$ in the following list, there is an explicit $\mathcal{G} = (G, \theta)$ such that $\mathcal{P}$ is isomorphic to $\mathcal{P}(\mathcal{G})$.

* The (right) weak order on Coxeter groups $A_{n-1}$, $B_n$ and $\tilde{A}_n$.

* The flag weak order on $\mathbb{Z}_r \setminus S_n$ (see [1]).

* The up-set (resp. down-set) lattice of any finite poset.

* The tree order of any finite tree.

In this extended abstract we will focus on the case of the symmetric group $A_{n-1}$.

## 4.1 The weak order on $A_{n-1}$

Recall that $A_{n-1}$ is the Coxeter group with generating set $S = \{s_1, \dots, s_{n-1}\}$, and with Coxeter matrix given by $m_{s_i s_{i+1}} = 3$ for all $1 \leq i \leq n-2$, and $m_{st} = 2$ otherwise. One can see $A_{n-1}$ as the symmetric group $S_n$ by identifying the generator $s_i$ to the transposition of $S_n$ which exchanges the integers $i$ and $i+1$. The main issue that arises when we want to find a pair $\mathcal{G} = (G, \theta)$ such that $(A_{n-1}, \leq_R)$ is isomorphic to $\mathcal{P}(\mathcal{G})$, is that on the one side we have a poset whose elements are permutation (once $A_{n-1}$ identified to the symmetric group $S_n$), and on the other side we have a poset whose elements are sets. Fortunately, there is a canonical set associated with each permutation $\sigma \in S_n$, its inversion set:

$$ \mathrm{Inv}(\sigma) = \{(a, b) \in \{1, \dots, n\}^2 \mid a < b \text{ and } \sigma^{-1}(a) > \sigma^{-1}(b)\}. \quad (4) $$

There is a deep connection between inversion sets and the weak order on $S_n$. That is, if $\sigma$ and $\omega$ are two elements of $S_n$, then $\sigma \leq_R \omega$ if and only if $\mathrm{Inv}(\sigma) \subseteq \mathrm{Inv}(\omega)$. This property allows us to clarify our goal: we are looking for a pair $\mathcal{G} = (G, \theta)$ such that,

1. the vertices of the graph are indexed by the couple of integers $(a, b) \in \{1, \dots, n\}^2$ such that $a < b$;

2. the digraph structure of $\mathcal{G}$, together with the valuation $\theta$, imply that $\mathrm{IS}(\mathcal{G})$ is constituted exactly of the sets of the form $\mathrm{Inv}(\sigma)$, $\sigma \in S_n$.
There is a convenient way to represent the set $\{(a, b) \in \{1, \dots, n\}^2 | a < b\}$, by considering the $n$-th staircase diagram, namely the Ferrers diagram of the partition $\lambda_n = (n-1, n-2, \dots, 1)$ of size $N = \binom{n}{2}$. At the left of the next figure, the diagram associated to the case $n=5$ is represented. The coordinates of each box can be read thanks to the circled integers on the diagonal.

<figure><img src="image_3.png" /></figure>

The coordinates of
this box are (2, 5)

<figure><img src="image_4.png" /></figure>

The inversion set of
$\sigma = [4, 1, 3, 5, 2]$

<figure><img src="image_5.png" /></figure>

Hook based on (2, 5)

As depicted in the middle of the figure, one can easily visualize the inversion set of any element of $S_n$ as a subset of boxes in $\lambda_n$. Note that the set constituted by all the boxes of the diagram corresponds to the inversion set of the reverse permutation $[n, n-1, \dots, 1] \in S_n$, which is the maximal element in the weak order.

**Definition 4.1** We define a digraph structure $G$ on this diagram (where the vertices are the boxes of the diagram), thanks to a classical combinatorial object associated to each box $c$, the hook based on $c$, denoted $\mathcal{H}(c)$ and composed of all the boxes which are on the right and below $c$ (represented at the right of the Figure): we say that there is an arc from $c$ to $d$ if and only if $c \neq d$ and $d \in \mathcal{H}(c)$. The obtained digraph $G$ is obviously a simple acyclic digraph whose vertices are the boxes of the diagram. Moreover, with this definition we have that the out-degree of any box is an even number. Hence we set $\theta$ the valuation $\theta: c \mapsto \frac{d^+(c)}{2}$. Finally, we denote $\mathcal{G}^A = (G, \theta)$.

Among others natural choices for a valuation on this digraph, this one is in fact the “good” choice as stated in the next theorem.

**Theorem 4.2** Set $n \in \mathbb{N}$ and $\mathcal{G}^A$ associated with $\lambda_n$. The posets $(S_n, \le_R)$ and $\mathcal{P}(\mathcal{G}^A)$ are isomorphic.

**Proof:** It is enough to show that $\mathrm{IS}(\mathcal{G}) = \{\mathrm{Inv}(\sigma) | \sigma \in S_n\}$. The inclusion $\supseteq$ is based on a verification using Proposition 3.1.1.

To give a sketch of the proof of the reverse inclusion, we recall a classical concept about permutations. Set $\sigma \in S_n$ and $1 \le a < b \le n$ two integers. We say that $a$ and $b$ are adjacent in $\sigma$ if and only if $\sigma^{-1}(a) + 1 = \sigma^{-1}(b)$. This notion is linked to the weak order thanks to the following property: we have that $\sigma \le_R \omega$ with $\ell(\omega) = \ell(\sigma) + 1$ if and only if $\omega$ can be obtained from $\sigma$ by exchanging the position of two adjacent entries of $\sigma$. In that case, we say that $\omega$ covers $\sigma$ and we denote it $\sigma \triangleleft \omega$. This can be transposed in the context of the inversion sets as follows: we have that $\sigma \triangleleft \omega$ if and only if $\mathrm{Inv}(\omega) = \mathrm{Inv}(\sigma) \cup \{(a, b)\}$ where $a$ and $b$ are two adjacent entries of $\sigma$.

Now consider $B \in \mathrm{IS}(\mathcal{G}^A)$ and $L = [(a_1, b_1), \dots, (a_N, b_N)] \in \mathrm{PS}(\mathcal{G}^A)$ such that $B = \{(a_1, b_1), \dots, (a_k, b_k)\}$. Set $B_0 = \emptyset$, and $B_i = \{(a_1, b_1), \dots, (a_i, b_i)\}$ for all $1 \le i \le k$. We can show recursively that $B_i$ is the inversion set of a permutation.
• If we denote $\mathit{Id} = [1, 2, \dots, n]$, then $B_0 = \mathit{Inv}(\mathit{Id})$.

• By definition of $\mathcal{G}^A$, we have that $(a_1, b_1)$ is of the form $(j, j+1)$ for some $j \in \{1, \dots, n-1\}$. Since $j$ and $j+1$ are adjacent in $\mathit{Id}$, we have that $\mathit{Id} \triangleleft \sigma_1 := [1, \dots, j+1, j, \dots, n]$, thus $\mathit{Inv}(\sigma_1) = \{(j, j+1)\} = \{(a_1, b_1)\} = B_1$.

• Now, consider $\mathcal{G}_2^A$ obtained with the peeling process after we picked $(a_1, b_1)$. Since $L \in \mathcal{PS}(\mathcal{G}^A)$, $(a_2, b_2)$ is erasable in $\mathcal{G}_2^A$. Then we can show that $a_2$ and $b_2$ are adjacent in $\sigma_1$, hence $\sigma_1 \triangleleft \sigma_2$, where $\sigma_2$ is obtained from $\sigma_1$ by exchanging the positions of $a_2$ and $b_2$. Hence $\mathit{Inv}(\sigma_2) = \mathit{Inv}(\sigma_1) \cup \{(a_2, b_2)\} = \{(a_1, b_1), (a_2, b_2)\} = B_2$.

• The sequel of the induction is similar: if there is $\sigma_j$ such that $\mathit{Inv}(\sigma_j) = \{(a_1, b_1), \dots, (a_j, b_j)\}$, then we show that $a_{j+1}$ and $b_{j+1}$ are adjacent in $\sigma_j$, and we construct $\sigma_{j+1}$ as before. The exact proof is quite technical and is essentially based on refinements of the arguments introduced by Edelman and Greene about balanced tableaux of staircase shape. The interested reader can look at [9] for a proof using another terminology.

As an immediate consequence, $B = B_k = \mathit{Inv}(\sigma_k)$. This concludes the proof. $\square$

<figure><img src="image_6.png" /></figure>

## 4.2 A combinatorial model for reduced decompositions in $A_{n-1}$

**Remark 4.2.1** For a more detailed description of the content of this section, the reader can look at [9].

This construction provides a new combinatorial interpretation of the elements of $\mathcal{R}(\sigma)$ for each $\sigma \in S_n$. That is, consider $\sigma \in S_n$ and $B \in \mathcal{IS}(\mathcal{G}^A)$ such that $B = \mathit{Inv}(\sigma)$. We may associate to $B$ a canonical digraph structure and an OCV by “restriction” of the structure of $\mathcal{G}^A$. That is, the sub-diagram $B$ inherit of the digraph structure of the original diagram. Moreover, since $B$ is an initial section, the restriction of $\theta$ to this sub-diagram is an OCV of it. The next figure depict this restriction on the example of $[4, 1, 3, 5, 2]$ (the integers in the boxes represent the values of $\theta$ on each box).

<figure><img src="image_7.png" /></figure>

We will denote $\mathcal{PS}(B)$ the set of all the peeling sequences of the sub-graph and OCV induced by $B$.

**Proposition 4.2.1** Set $\sigma \in S_n$ and $B$ its associated diagram. There is a bijection between $\mathcal{R}(\sigma)$ and $\mathcal{PS}(B)$.

**Proof:** Recall that a maximal chain from $\mathit{Id}$ to $\sigma$ (in the weak order) is a sequence $(\sigma_j)_{1 \le j \le k}$ such that $\mathit{Id} \triangleleft \sigma_1 \triangleleft \dots \triangleleft \sigma_k = \sigma$. There is a canonical bijection between elements of $\mathcal{R}(\sigma)$ and maximal chains from $\mathit{Id}$ to $\sigma$. That is, set $s_{i_1} \cdots s_{i_k} \in \mathcal{R}(\sigma)$ and denote $\sigma_j = s_{i_1} \cdots s_{i_j}$, then we have $\mathit{Id} \triangleleft \sigma_1 \triangleleft \dots \triangleleft \sigma_k = \sigma$. Conversely, if $\sigma \triangleleft \omega$, we have that there exists $s_p$ such that $\omega = \sigma s_p$ by definition of the weak order, thus a maximal chain leads to a reduced decomposition of $\mathcal{R}(\sigma)$.
Now set $L = [(a_1, b_1), \dots, (a_k, b_k)] \in \mathbf{PS}(B)$, and denote $B_i = \{(a_1, b_1), \dots, (a_i, b_i)\}$. By construction of the isomorphism between $(S_n, \le_R)$ and $\mathcal{P}(\mathcal{G}^A)$, there exists $\sigma_i$ such that $\mathrm{Inv}(\sigma_i) = B_i$. Hence we have $\emptyset \subset \mathrm{Inv}(\sigma_1) \subset \dots \subset \mathrm{Inv}(\sigma_k)$. Then we transpose this expression to the weak order, and it becomes $\mathrm{Id} \triangleleft \sigma_1 \triangleleft \dots \triangleleft \sigma_k = \sigma$. To summarize, we associated a maximal chain (from $\mathrm{Id}$ to $\sigma$) to each element of $\mathbf{PS}(B)$, and we can show that it is a bijection. This concludes the proof. $\square$

**Example 4.2.1** We conclude by an example of application of this bijection to $\sigma = [4, 1, 3, 5, 2]$. Denote $B$ the diagram associated with $\sigma$, and consider $L = [(2, 3), (2, 4), (3, 4), (1, 4), (2, 5)] \in \mathbf{PS}(B)$. The maximal chain associated with $L$ is: $\sigma_1 = [1, 3, 2, 4, 5] = s_2$, $\sigma_2 = [1, 3, 4, 2, 5] = \sigma_1 s_3$, $\sigma_3 = [1, 4, 3, 2, 5] = \sigma_2 s_2$, $\sigma_4 = [4, 1, 3, 2, 5] = \sigma_3 s_1$, and $\sigma_5 = [4, 1, 3, 5, 2] = \sigma_4 s_4$. Thus the associated reduced decomposition is $s_2 s_3 s_2 s_1 s_4$. The next figure describes completely the bijection in the case of $[4, 1, 3, 5, 2]$ (for the reader convenience, peeling sequences are represented by tableaux).

<figure><img src="image_8.png" /></figure>

## 4.3 Application to the Stanley series of type A

The graphical interpretation of the reduced decomposition of a permutation as set of tableaux leads to a natural question: can we define a good generalization of the concept of semi-standard Young tableaux in this context ? If this is the case, what does the associate formal power series look like ?

A natural starting point is to consider tableaux defines by a "column-strictness" condition as in [5].

**Definition 4.2** Set $\sigma \in S_n$ and $B$ its associated diagram. A tableau $T$ of shape $B$ is a sequence of integers indexed by the elements of $B$, that is $T = (t_c)_{c \in B}$. We say that $T$ is $\sigma$-semi-standard if and only if there exists $L = [c_1, \dots, c_k] \in \mathbf{PS}(B)$ such that:

1. for all $i < j$, $t_{c_i} \le t_{c_j}$;

2. for all $i < j$ such that $c_i$ and $c_j$ lies in the same column of $B$, $t_{c_i} < t_{c_j}$.

The set of the $\sigma$-semi-standard tableaux is denoted $\mathrm{SST}(\sigma)$. Finally, we denote $x^T$ the monomial $\prod_{c \in B} x_{t_c}$.

It appears that the tableaux in $\mathrm{SST}(\sigma)$ and the column-strict balanced labellings of the Rothe diagram of $\sigma$ introduced in [5], are basically the same objects. That is, one can travel from one point of view to another just by swapping some lines of the tableaux, as depicted below.
<figure><img src="image_9.png" /></figure>

Hence, as an immediate consequence of (Theorem 4.3, [5]), we have the following Theorem.

**Theorem 4.3** For all $\sigma \in S_n$, $F_{\sigma}(x_1, x_2, \dots) = \sum_{T \in SST(\sigma)} x^T$, where $F_{\sigma}$ is the Stanley series of type A associated with $\sigma$ and defined by

$$F_{\sigma}(x_1, x_2, \dots) = \sum_{s_{i_1} \cdots s_{i_{\ell(\sigma)}} \in \mathcal{R}(\sigma)} \sum_{\substack{b_1 \le b_2 \le \cdots \le b_{\ell(\sigma)} \\ b_j < b_{j+1} \text{ if } i_j > i_{j+1}}} x_{b_1} x_{b_2} \cdots x_{b_{\ell(\sigma)}}.$$

## 5 Other cases

In the previous section we studied the case A in details, and showed how it naturally leads to a combinatorial interpretation of the associated Stanley series. A similar process can be performed in the $\tilde{A}$ case, and leads to an analogous combinatorial interpretation of the reduced decompositions in $\tilde{A}$, and of the corresponding Stanley series (using [10]) introduced by Lam in [6]. In that case, the underlying graph can be seen as an infinite version of $G^A$, which is rolled around a cylinder. For a graphical representation, see the following figure.

In the case of the weak order on the type B, the digraph is a bit more complicated and can be visualize as a *shifted diagram*, where the digraph structure is given by the *shifted hooks*. In that case, the study of the associated formal power series which arise is undone, and the author will focus on that topic later. To conclude, we mention that some clues suggest that a description of the weak order on any Coxeter group with this theory is possible, and this will be the subject of a later publication.

We finish by giving, without justification, the graphical representation of some of these objects.

<figure><img src="image_10.png" /></figure>
References

[1] R. Adin, F. Brenti, Y. Roichman, *Flag weak order on wreath products*. Sém. Lothar. Combin. 67 (2011/12), B67e, 20pp.

[2] A. Bjorner, *Orderings of Coxeter groups*. Contemp. Math., 34, Amer. Math. Soc., Providence, RI, 1984.

[3] A. Bjorner, F. Brenti, *Combinatorics of Coxeter groups*. Springer, New York, NY, 2005.

[4] P. Edelman, C. Greene, *Balanced tableaux*. Adv. Math., 63, 42-99, 1987.

[5] S. Fomin, C. Greene, V. Reiner, M. Shimozono, *Balanced Labellings and Schubert Polynomials*. Europ. J. Combin., 18, 373-389, 1995.

[6] T. Lam, *Affine Stanley symmetric functions*. Amer. J. Math., 128(6):1553-1586, 2006.

[7] R. P. Stanley, *On the number of reduced decompositions of elements of Coxeter groups*. Europ. J. Combin., 5, 359-372, 1984.

[8] R. P. Stanley, *Enumerative combinatorics. Vol. 1*, volume 62 of Cambridge studies in advanced mathematics. Cambridge university press, Cambridge, 1999. With a foreword by Gian-Carlo Rota and appendix 1 by Sergey Fomin.

[9] F. Viard, *A natural generalisation of balanced tableaux*. Preprint arXiv.org:1407.6217, 2014 (24 pages).

[10] H. Yoo, H. Yun, *Balanced labellings of affine permutations*. DMTCS Proceedings, north America, FPSAC 2013. Available at: www.dmtcs.org/dmtcs-ojs/index.php/proceedings/article/view/dmAS0166.