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
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.