The domination order on tableaux, Garnir tableaux and bricks

The permutation criterion. Let $t=(ab)$ with $a<b$ act on values and write $p=x^{-1}(a)$, $q=x^{-1}(b)$. If $p<q$, direct inversion counting gives $\mathrm{\ell }(tx)-\mathrm{\ell }(x)=1+2\mathrm{\#}\{j:p<j<q,a<x(j)<b\}>0$; if $p>q$ the difference is its negative. A positive difference need not equal one. The rank inequalities in [F5] show $x<tx$ precisely in the first case: the rank count decreases by one for $p\le h<q$ and $a\le k<b$, and is unchanged elsewhere. Thus every displayed earlier-node transposition lowers strong Bruhat order. Conversely a saturated strong-Bruhat chain from $w_S$ to $w_T$ consists of transposition covers by [F6], each of whose inverse lowering move has the earlier larger value by the formula just proved. Reading this chain backwards yields the displayed transposition criterion.

Agreement outside the Garnir belt. In the row-reading initial labelling the two pieces of the belt form one contiguous interval of positions $[L,U]$: the upper-row tail is immediately followed by the lower-row prefix. A Garnir tableau changes labels only inside this interval, so $w_T$ is in the parabolic subgroup generated by $s_L,\dots ,s_{U-1}$. Sorting its interval permutation gives a reduced expression using only these generators. The Bruhat subword criterion applied to this expression says that every $w_S\le w_T$ likewise uses only these generators. Hence $w_S$ fixes all positions outside $[L,U]$, proving agreement with $t^{\mu }$ outside the belt. This applies even to nonstandard $S$.

The prefix-shape criterion. For a row-strict $W$ and a value $c$, row-strictness makes the entries $\le c$ in each row a prefix, so $\mathrm{sh}(W^{\le c})$ is a row sequence of size $c$, and for $p=P_k+t$ with $P_k$ the number of nodes in the first $k$ rows and $0\le t<{\mu }_{k+1}$ we get $N_W(p,c):=\mathrm{\#}\{i\le p:\text{entry }i\text{ of }W\le c\}=A_k(W,c)+\min (t,s_{k+1}(W,c)),$ where $A_k(W,c)$ is the number of entries $\le c$ in the first $k$ rows and $s_{k+1}(W,c)$ the prefix length in row $k+1$. By [F5], $w_S\le w_T$ iff $N_S(p,c)\ge N_T(p,c)$ for all $p,c$. At $p=P_k$ this says $A_k(S,c)\ge A_k(T,c)$ for all $k,c$, which is exactly $\mathrm{sh}(S^{\le c})⊵\mathrm{sh}(T^{\le c})$ for all $c$; hence the prefix criterion is necessary. Conversely assume all these prefix inequalities, fix $p=P_k+t$ and put $a=A_k(S,c)-A_k(T,c)\ge 0$, $s=s_{k+1}(S,c)$, $s^{\mathrm{\prime }}=s_{k+1}(T,c)$; the inequality at $k+1$ gives $a+s\ge s^{\mathrm{\prime }}$. If $t\le s$ then $a+\min (t,s)=a+t\ge \min (t,s^{\mathrm{\prime }})$, because $t\le s^{\mathrm{\prime }}$ gives $a+t\ge t$ and $t>s^{\mathrm{\prime }}$ gives $a+t\ge t\ge s^{\mathrm{\prime }}$; if $t>s$ then $a+\min (t,s)=a+s\ge s^{\mathrm{\prime }}\ge \min (t,s^{\mathrm{\prime }})$. Thus $N_S(p,c)\ge N_T(p,c)$ for all $p,c$ and $S⊴T$. Since the first $k$ rows of $t^{\mu }$ contain $\min (c,P_k)$ entries $\le c$, the maximum possible, $\mathrm{sh}(t^{\mu \le c})$ dominates every $\mathrm{sh}(W^{\le c})$, so $t^{\mu }$ is the least element of $⊴$ on row-strict tableaux.

Consecutive swaps and the edges of the weak graph. Let $T$ be standard. If $r,r+1$ share a row, row-strictness puts $r$ immediately left of $r+1$ and the swap reverses an adjacent pair, so $s_{r}T$ is not row-strict; if they share a column, column-strictness puts $r$ immediately above $r+1$ and the swap reverses an adjacent column pair, so $s_{r}T$ is not column-strict. If in one component $r+1$ lies strictly above and strictly left of $r$, let $x$ be the entry of $T$ in the node in the row of $r$ and the column of $r+1$: row-strictness gives $x<r$ while column-strictness gives $x>r+1$, impossible, and symmetrically $r$ cannot lie strictly above and strictly left of $r+1$. The only remaining same-component configurations are $r{\nearrow }_{T}r+1$ and $r+1{\nearrow }_{T}r$; in either, the nodes sharing a row or column with the two positions are unchanged except for the interchange of the consecutive values $r,r+1$, so all strict neighbour inequalities survive and $s_{r}T$ is standard. If $r,r+1$ lie in different components the swap is standard as well. This proves the stated equivalence. For the edge criterion note that $S=s_{r}T$ with both standard and $r$ earlier than $r+1$ in $T$: in one component the alternatives of the equivalence leave only $r+1{\nearrow }_{T}r$ (in the other alternative $r+1$ is in a higher row and hence earlier, and same-row or same-column swaps are excluded), while in different components $r$ is earlier exactly when its component is earlier.

Row sorting. Let $S,T$ be $\mu$-tableaux with $S⊴T$; by steps 1.1 and 2.1 it suffices to treat a single transposition $S=(ab)T$ with $a<b$ and $b$ earlier than $a$ in $T$, the general case following by composing the finitely many single-swap comparisons. Write $S^{+},T^{+}$ for the tableaux obtained by sorting every row increasingly. If $a,b$ share a row of $T$, then $S$ and $T$ have the same row sets and $S^{+}=T^{+}$. Otherwise the node of $b$ lies in a strictly earlier row than the node of $a$: they are in different rows by the previous sentence, and $b$ earlier than $a$ forces $b$'s row to be the earlier one. Entries other than $a,b$ occupy the same nodes in $S$ and $T$. For a value $c$, the prefix row lengths of $S^{+}$ and $T^{+}$ at $c$ are the rows' counts of entries $\le c$; if $c<a$ or $c\ge b$ these counts agree, while if $a\le c<b$ the count vector of $S^{+}$ is obtained from that of $T^{+}$ by moving one unit from the row of $a$ to the earlier row of $b$. Moving a unit to an earlier row raises every partial sum of the row sequence, so $\mathrm{sh}(S^{+\le c})⊵\mathrm{sh}(T^{+\le c})$ for every $c$; both tableaux are row-strict, so step 2.1 gives $S^{+}⊴T^{+}$. Hence $S⊴T$ implies $S^{+}⊴T^{+}$ in general.

The vertical consecutive swap and its exceptional prefix. Assume $\mu$ is a multipartition, $T$ standard, $r{\downarrow }_{T}r+1$, so $r$ and $r+1$ occupy adjacent rows $a,a+1$ of one component in the same column $b$; the neighbour check of step 3.1 shows that $U:=s_{r}T$ is row-strict. Let $S$ be standard with $S⊲U$; we prove $S⊴T$. By step 2.1, $\mathrm{sh}(S^{\le c})⊵\mathrm{sh}(U^{\le c})$ for all $c$, and for $c\mathrm{\ne }r$ the tableaux $U^{\le c}$ and $T^{\le c}$ occupy the same nodes, so their shapes agree. For $c=r$ let $A_k$ be the number of entries $\le r-1$ in the first $k$ rows of $T$ (the same for $U$) and note that $\mathrm{sh}(U^{\le r})$ has row lengths $A_k-A_{k-1}+[k=a+1]$ while $\mathrm{sh}(T^{\le r})$ has $A_k-A_{k-1}+[k=a]$; thus $\mathrm{sh}(T^{\le r})$ is obtained from $\mathrm{sh}(U^{\le r})$ by moving one node from row $a+1$ up to row $a$. Because $T$ is standard, the node of $r$ in row $a$ has column $b$, so exactly $b-1$ entries of row $a$ lie in columns $<b$, all of them $\le r-1$, and the same count holds in row $a+1$ whose node in column $b$ is occupied by $r+1$; hence $A_a-A_{a-1}=b-1=A_{a+1}-A_a$ and the switch hypothesis $\mathrm{sh}(U^{\le r}{)}_a-\mathrm{sh}(U^{\le r}{)}_{a+1}=(b-1)-((b-1)+1)=-1$ holds. Lemma 3.1 of the source, proved here: if $\nu$ is a row sequence and ${\nu }_a-{\nu }_{a+1}=-1$, and $\widehat{\nu }$ interchanges the two consecutive parts ${\nu }_a,{\nu }_{a+1}$, then $\widehat{\nu }$ has the same partial sums as $\nu$ except at index $a$, where they are larger by one; consequently any multipartition $\lambda$ with $\lambda ⊵\nu$ also satisfies $\lambda ⊵\widehat{\nu }$: if its partial sum at $a$ equalled that of $\nu$, the inequalities at $a-1$ and $a+1$ would force ${\lambda }_a\le {\nu }_a<{\nu }_{a+1}\le {\lambda }_{a+1}$, contradicting the weakly decreasing parts in that component. Thus its partial sum at $a$ is at least one larger; other partial sums are unchanged. Apply this with $\lambda =\mathrm{sh}(S^{\le r})$, $\nu =\mathrm{sh}(U^{\le r})$, $\widehat{\nu }=\mathrm{sh}(T^{\le r})$: the row sequence of a standard tableau's prefix is a multipartition, and the computed switch identity verifies the hypothesis, so $\mathrm{sh}(S^{\le r})⊵\mathrm{sh}(T^{\le r})$. With the equalities for $c\mathrm{\ne }r$, step 2.1 gives $S⊴T$. In the same-row case $r{\to }_{T}r+1$ one has $T=U^{+}$ and $S=S^{+}$, so step 3.2 gives $S⊴T$ directly; this proves both clauses of the vertical exceptional-prefix fact.

The four terminal alternatives (horizontal). Let $\mu$ be a multipartition and $T$ be standard with $r{\to }_{T}r+1$. Consider the three properties: (a) there is $t$ with $\mathrm{\mid }t-r\mathrm{\mid }>1$ such that $t{\nearrow }_{T}t+1$ or $t$ lies in a later component than $t+1$; (b) $r+1{\nearrow }_{T}r+2$ or $r+1$ lies in a later component than $r+2$; (c) $r-1{\nearrow }_{T}r$ or $r-1$ lies in a later component than $r$. By step 3.1 an incoming edge at $t$ (that is, $s_{t}T$ standard with $t$ earlier than $t+1$ in $s_{t}T$) is equivalent to $t{\nearrow }_{T}t+1$ or $t$ in a later component than $t+1$. If (a) holds, then $X:=s_{t}T$ is standard and $X\stackrel{t}{\to }T$ is an edge, so $T$ is $t$-terminal, and since $t\mathrm{\notin }\{r,r+1\}$ the relation $r{\to }_{T}r+1$ persists in $X$; this is alternative (1). If (b) holds with $r+1{\nearrow }_{T}r+2$, then in $X:=s_{r+1}T$ the entry $r+1$ occupies the higher node of $r+2$, so $X\stackrel{r+1}{\to }T$ is an edge; since $r,r+1$ are adjacent in one row and $r+2$ is above and right, $r+1$ is above and right of $r$ in $X$, so $Y:=s_{r}X$ is standard and $Y\stackrel{r}{\to }X$ is an edge with $r$ moving to the higher node, and in $Y$ the entries $r+1,r+2$ are adjacent in one row with $r+1$ to the left; this is alternative (2). If (b) holds with $r+1$ in a later component than $r+2$, the same construction with component arguments gives (2). If (c) holds, the mirror construction gives (3). It remains to observe that if none of (a),(b),(c) holds, then $T$ has no incoming edge: indeed (a) is exactly the incoming-edge alternative at any $t\mathrm{\notin }\{r-1,r,r+1\}$, (c) at $t=r-1$, and (b) at $t=r+1$, while at $t=r$ both alternatives of step 3.1 fail because $r$ and $r+1$ lie in one row with $r$ to the left. A standard tableau with no incoming edge is $t^{\mu }$: if $T\mathrm{\ne }{t}^{\mu }$, choose the least $t$ with the node of $t+1$ earlier than the node of $t$ in $T$ (such $t$ exists because otherwise the entries occur in the order $1,2,\dots ,d$); then standardness forces $t{\nearrow }_{T}t+1$ or an earlier component for $t+1$, so the incoming-edge alternative at $t$ holds and gives the existence of an edge into $T$, a contradiction. Hence in this final case $T=t^{\mu }$, which is alternative (4).

The vertical terminal alternatives. Let $\mu$ be a multipartition and $r{\downarrow }_{T}r+1$ at $(a,b,n)$, so the two nodes are vertically adjacent. Use the following precise tests: (a) an incoming edge $t$ with $\mathrm{\mid }t-r\mathrm{\mid }>1$; (b) $r{\nearrow }_{T}r+2$ or $r+1$ is in a later component than $r+2$; (c) $r-1{\nearrow }_{T}r+1$ or $r-1$ is in a later component than $r$. Test (a) gives $s_{t}T\stackrel{t}{\to }T$ and preserves the vertical pair. In test (b), standardness and the consecutiveness of the three entries force $s_{r+1}T$ and $s_r{s}_{r+1}T$ to be standard: the node of $r+2$ is above and right of $r$, hence above and right of the node of $r+1$, and after the first swap the nodes of $r,r+1$ are incomparable. Thus $s_r{s}_{r+1}T\stackrel{r}{\to }{s}_{r+1}T\stackrel{r+1}{\to }T$, while $r+1,r+2$ occupy the original vertical pair in $s_r{s}_{r+1}T$. The different-component case uses the same two swaps without any within-component inequality. Test (c) gives the analogous $s_r{s}_{r-1}T\stackrel{r}{\to }{s}_{r-1}T\stackrel{r-1}{\to }T$, with $r-1,r$ in the original vertical pair. If none of the tests holds, labels other than the triple adjacent to $r$ cannot have an inversion between consecutive row-reading positions: any such inverse-order consecutive pair is in incomparable nodes or distinct components and is exactly an incoming edge. Reading $r-1,r-2,\dots ,1$ backwards and $r+2,r+3,\dots ,d$ forwards consequently places them in row-reading order except for the lower-row prefix before the vertical pair and the upper-row tail after it; tests (c) and (b) exclude any further excursion. More explicitly, if $L$ is the initial label at $(a,b,n)$ and $U$ the initial label at $(a+1,b,n)$, the forced belt filling is $L,\dots ,L+b-2$ in the first $b-1$ lower-row positions, $r=L+b-1$ in $(a,b,n)$, $r+1=L+b$ in $(a+1,b,n)$, and $L+b+1,\dots ,U$ in the remaining upper-row tail; all outside entries are unchanged. Among standard belt fillings this is Bruhat-maximal: the $b$ lower-row entries are the lexicographically smallest possible increasing subset, namely $L,\dots ,L+b-2,L+b$, because choosing the $b$ smallest would violate column $b$. Every other valid subset has no smaller prefix counts in the upper row, hence is below it by step 2.1. This is exactly the Garnir tableau, including $b=1={\mu }_a$. A horizontal brick is a consecutive same-row string. All selections, chains and comparisons are finite, so no choice principle is used.