Description of flipping tableau for inversions in reduced decompositions of permutations

Short version: Is there a graphical description of the possible orders in which inversions can appear in a reduced decomposition of a permutation?

Something akin to the definition of standard Young tableaux.

Inversions of longest permutation version

A permutation of degree $n$ is a bijection on $\{1,2,\cdots,n\}$. An inversion of a permutation $\pi$ of degree $n$ is a pair $(i,j)$ such that $1 \leq i < j \leq n$ but $\pi(i) > \pi(j)$. A reduced decomposition of a permutation $\pi$ of degree $n$ is an expression $\pi = g_1 \cdots g_m$ so that (1) each $g_k = (i,i+1)$ is an adjacent transposition for some $i$, (2) $m$ is the number of inversions of $\pi$. The longest element $\pi_0$ of degree $n$ is the permutation in which every pair is an inversion; $\pi_0 = (1,n)(2,n-1)\cdots$ is the "reversal".

In a reduced decomposition, the set of inversions of $g_1 \cdots g_{k+1}$ has precisely one more element $u_k = \{i,j\}$ than the set of inversions of $g_1 \cdots g_k$. The flipping tabelau of the decomposition is the tableau whose $j,i$ entry is $k$ where $u_k=\{i,j\}$ with $i<j$.

How does one describe all those possible flipping tableaux?

In particular, it should be easy to tell if a tableaux is in fact flipping without exhaustively constructing the flipping tableaux of all reduced decompositions of the longest permutation and checking if it appears in the list.

Example:

If $n=3$, then $\pi_0 = [3,2,1] = (1,3)(2)$ takes $1$ to $3$ and back, leaving $2$ alone. Its inversions are $\{ \{1,2\}, \{1,3\}, \{2,3\} \}$. A reduced decomposition is $\pi_0 = (1,2)(2,3)(1,2)$ and the prefix subwords are:

• $[1,2,3] = ()$ has no inversions
• $[2,1,3] = (1,2)$ has only one inversion: $\{\{1,2\}\}$
• $[2,3,1] = (1,2)(2,3)$ has two inversions: $\{\{1,2\}, \{1,3\}\}$
• $[3,2,1] = (1,2)(2,3)(1,2)$ has three inversions: $\{\{1,2\},\{1,3\},\{2,3\}\}$

The sequence $u_k$ is thus $\{1,2\}, \{1,3\}, \{2,3\}$, and so the flipping tableau is: $$\begin{array}{ccc} . & . & . \\ 3 & . & . \\ 2 & 1 & . \\ \end{array}$$

where empty boxes are listed as "."

More Examples:

By switching $(1,2)(2,3)(1,2)$ with $(2,3)(1,2)(2,3)$ we get the other possible flipping tableau for $n=3$:

$$\begin{array}{ccc|ccc} .&.&.&.&.&.\\ 1&.&.&3&.&.\\ 2&3&.&2&1&.\\ \end{array}$$

For $n=4$ there are 16 possible flipping tableaux:

$$\small\begin{array}{cccc|cccc|cccc|cccc} .&.&.&.&.&.&.&.&.&.&.&.&.&.&.&.\\ 1&.&.&.&1&.&.&.&1&.&.&.&1&.&.&.\\ 2&3&.&.&2&4&.&.&2&6&.&.&5&6&.&.\\ 4&5&6&.&3&5&6&.&3&5&4&.&3&4&2&.\\ \hline .&.&.&.&.&.&.&.&.&.&.&.&.&.&.&.\\ 1&.&.&.&3&.&.&.&6&.&.&.&5&.&.&.\\ 4&6&.&.&2&1&.&.&2&1&.&.&2&1&.&.\\ 3&5&2&.&4&5&6&.&4&3&5&.&4&3&6&.\\ \hline .&.&.&.&.&.&.&.&.&.&.&.&.&.&.&.\\ 6&.&.&.&5&.&.&.&6&.&.&.&2&.&.&.\\ 3&1&.&.&3&1&.&.&5&1&.&.&5&6&.&.\\ 4&2&5&.&4&2&6&.&4&2&3&.&3&4&1&.\\ \hline .&.&.&.&.&.&.&.&.&.&.&.&.&.&.&.\\ 2&.&.&.&4&.&.&.&6&.&.&.&6&.&.&.\\ 4&6&.&.&5&6&.&.&5&4&.&.&5&3&.&.\\ 3&5&1&.&3&2&1&.&3&2&1&.&4&2&1&.\\ \end{array}$$

There are 768 possibilities for $n=5$, and 292864 possibilities for $n=6$. This is OEIS:A005118 in general, but I don't see how my flipping tableaux are standard Young tableaux (rows are not monotonic, columns are not monotonic). Stanley also describes a similar set of tableaux, the balanced tableaux, which are put in bijection with reduced decompositions in Edelman–Greene (1987). However, I still don't see the connection with my flipping tableaux.

Solution 1:

The short answer to seeing if a tableau $T$ is a flipping tableau is to check if the tableau is balanced, which in this setting means that each hook $H_{ij}$ contains an equal number of entries greater than $T_{ij}$ and smaller.

The construction you have outlined for the flipping tableau of a reduced decomposition is precisely the same as the Edelman-Greene construction of the corresponding balanced tableau, modulo one detail. If you check the tableaux you have constructed, you will see that they are in fact balanced. The only difference is that your construction produces tableau in the French notation, while Edelman-Greene produce tableaux in the American notation. To change from one to the other, replace $j$ with $n-j$. This would have $T_{ij} =k$ where $k$ is the swap time between $i$ and $n+1-j$, precisely as stated in Section 4 of $\it{Balanced\ Tableaux}$.