Tableau combinatorics

Arun Ram
Department of Mathematics and Statistics
University of Melbourne
Parkville, VIC 3010 Australia
aram@unimelb.edu.au

Last update: 3 March 2013

Tableau combinatorics

Skew shapes and standard tableaux. A partition $\lambda$ is a collection of $n$ boxes in a corner. We shall conform to the conventions in [Mac1995] and assume that gravity goes up and to the left.

$$$$

Any partition $\lambda$ can be identified with the sequence $\lambda =({\lambda }_1\le {\lambda }_2\ge \dots )$ where ${\lambda }_i$ is the number of boxes in row $i$ of $\lambda \text{.}$ The rows and columns are numbered in the same way as for matrices. In the example above we have $\lambda =\left(553311\right)\text{.}$ If $\lambda$ and $\mu$ are partitions such that ${\mu }_i\le {\lambda }_i$ for all $i$ we write $\mu \subseteq \lambda \text{.}$ The skew shape $\lambda /\mu$ consists of all boxes of $\lambda$ which are not in $\mu \text{.}$ Any skew shape is a union of connected components. Number the boxes of each skew shape $\lambda /\mu$ along major diagonals from southwest to northeast and

$$\text{write}\hspace{0.17em}{\text{box}}_i\hspace{0.17em}\text{to indicate the box numbered}\hspace{0.17em}i\text{.}$$

Let $\lambda /\mu$ be a skew shape with $n$ boxes. A standard tableau of shape $\lambda /\mu$ is a filling of the boxes in the skew shape $\lambda /\mu$ with the numbers $1,\dots ,n$ such that the numbers increase from left to right in each row and from top to bottom down each column. Let

$${ℱ}^{\lambda /\mu }=\text{{standard tableaux of shape}\hspace{0.17em}\lambda /\mu \text{}.}$$

The column reading tableau $C$ of shape $\lambda /\mu$ is the standard tableau obtained by entering the numbers $1,2,\dots ,n$ consecutively down the columns of $\lambda /\mu ,$ beginning with the southwest most connected component and filling the columns from left to right. The row reading tableau $R$ of shape $\lambda /\mu$ is the standard tableau obtained by entering the numbers $1,2,\dots ,n$ left to right across the rows of $\lambda /\mu ,$ beginning with the northeast most connected component and filling the rows from top to bottom. In general, if $L$ is a standard tableau and $w\in S_n$ then $wL$ will denote the filling of $\lambda /\mu$ obtained by permuting the entries of $L$ according to the permutation $w\text{.}$

Proposition 2.1. [BWa1988, Theorem 7.1] Given a standard tableau $L$ of shape $\lambda /\mu$ define the word of $L$ to be permutation

$$w_L=\left(\begin{array}{ccc}1& \dots & n\\ L\left({\text{box}}_1\right)& \dots & L\left({\text{box}}_n\right)\end{array}\right)$$

where $L\left({\text{box}}_i\right)$ is the entry in ${\text{box}}_i$ of $L\text{.}$ Let $C$ and $R$ be the column reading and row reading tableaux of shape $\lambda /\mu ,$ respectively. The map

$$\begin{array}{ccc}{ℱ}^{\lambda /\mu }& ⟶& S_n\\ L& ⟼& w_L\end{array}$$

defines a bijection from ${ℱ}^{\lambda /\mu }$ to the interval $[w_C,w_R]$ in $S_n$ (in the Bruhat-Chevalley order).

Placed skew shapes. Let $ℝ+i[0,2\pi /\text{ln}\left(q^2\right))=\{a+bi\hspace{0.17em}\mid \hspace{0.17em}a\in ℝ,0\le b\le 2\pi /\text{ln}\left(q^2\right)\}\subseteq ℂ\text{.}$ If $q$ is a positive real number then the function

$$\begin{array}{ccc}ℝ+i[0,2\pi /\text{ln}\left(q^2\right))& ⟶& {ℂ}^{*}\\ x& ⟼& q^{2x}=e^{\text{ln}\left(q^2\right)x}\end{array}$$

is a bijection. The elements of $[0,1)+i[0,2\pi /\text{ln}\left(q^2\right))$ index the $\mathbb{Z}\text{-cosets}$ in $ℝ+i[0,2\pi /\text{ln}\left(q^2\right))\text{.}$

A placed skew shape is a pair $(c,\lambda /\mu )$ consisting of a skew shape $\lambda /\mu$ and a content function

$$c:\{\text{boxes of}\hspace{0.17em}\lambda /\mu \}⟶ℝ+i[0,2\pi /\text{ln}\left(q^2\right))\text{such that}$$

$$\begin{array}{cc}c\left({\text{box}}_j\right)\ge c\left({\text{box}}_i\right),& \text{if}\hspace{0.17em}i\le j\hspace{0.17em}\text{and}\hspace{0.17em}c\left({\text{box}}_j\right)-c\left({\text{box}}_i\right)\in \mathbb{Z},\\ c\left({\text{box}}_j\right)=c\left({\text{box}}_i\right)+1,& \text{if and only if}\hspace{0.17em}{\text{box}}_i\hspace{0.17em}\text{and}\hspace{0.17em}{\text{box}}_j\hspace{0.17em}\text{are on adjacent diagonals, and}\\ c\left({\text{box}}_i\right)=c\left({\text{box}}_j\right),& \text{if and only if}\hspace{0.17em}{\text{box}}_i\hspace{0.17em}\text{and}\hspace{0.17em}{\text{box}}_j\hspace{0.17em}\text{are on the same diagonal.}\end{array}$$

This is a generalization of the usual notion of the content of a box in a partition (see [Mac1995] I §1 Ex. 3).

Suppose that $(c,\lambda /\mu )$ is a placed skew shape such that $c$ takes values in $\mathbb{Z}\text{.}$ One can visualize $(c,\lambda /\mu )$ by placing $\lambda /\mu$ on a piece of infinite graph paper where the diagonals of the graph paper are indexed consecutively (with elements of $\mathbb{Z}\text{)}$ from southeast to northwest. The content of a box $b$ is the index $c\left(b\right)$ of the diagonal that $b$ is on. In the general case, when $c$ takes values in $ℝ+i[0,2\pi /\text{ln}\left(q^2\right)),$ one imagines a book with $r$ pages of infinite graph paper where the diagonals of the graph paper are indexed consecutively (with elements of $\mathbb{Z}\text{)}$ from southeast to northwest. The pages are numbered by values ${\beta }_1,\dots ,{\beta }_r$ from the set $[0,1)+i[0,2\pi /\text{ln}\left(q^2\right))$ and there is a skew shape ${\lambda }^{\left(k\right)}/{\mu }^{\left(k\right)}$ placed on page ${\beta }_k\text{.}$ The skew shape $\lambda /\mu$ is a union of the disjoint skew shapes ${\lambda }^{\left(i\right)}/{\mu }^{\left(i\right)},$

$$\lambda /\mu ={\lambda }^{\left(1\right)}/{\mu }^{\left(1\right)}\cup \dots \cup {\lambda }^{\left(r\right)}/{\mu }^{\left(r\right)},$$

and the content function is given by

$$c\left(b\right)=\left(\text{page number of the page containing}\hspace{0.17em}b\right)+\left(\text{index of the diagonal containing}\hspace{0.17em}b\right)\text{.}$$

Example. The following diagrams illustrate standard tableaux and the numbering of boxes in a skew shape $\lambda /\mu \text{.}$

$$\begin{array}{cc} 10 12 13 14 6 8 11 5 7 9 4 2 3 1 & 3 4 9 12 1 5 10 7 13 14 2 6 8 11 \\ \lambda /\mu \hspace{0.17em}\text{with boxes numbered}& \text{A standard tableau}\hspace{0.17em}L\hspace{0.17em}\text{of shape}\hspace{0.17em}\lambda /\mu \end{array}$$

The word of the standard tableau $L$ is the permutation $w_L=(11,6,8,2,7,1,13,5,14,3,10,4,9,12)$ (in one-line notation).

The following picture shows the contents of the boxes in the placed skew shape $(c,\lambda /\mu )$ such that the sequence $(c\left({\text{box}}_1\right),\dots ,c\left({\text{box}}_n\right))$ is $(-7,-6,-5,-2,0,1,1,2,2,3,3,4,5,6)\text{.}$

$$\begin{array}{c} 3 4 5 6 1 2 3 0 1 2 -2 -6 -5 -7 \\ \text{Contents of the boxes of}\hspace{0.17em}(c,\lambda /\mu )\end{array}$$

The following picture shows the contents of the boxes in the placed skew shape $(c\prime ,\lambda /\mu )$ such that the sequence $(c\left({\text{box}}_1\right),\dots ,c\left({\text{box}}_n\right))$ is $(-7,-6,-5,-3/2,1/2,3/2,5/2,5/2,7/2,7/2,9/2,11/2,13/2)\text{.}$

This “book” has two pages, with page numbers 0 and $\frac{1}{2}\text{.}$

Lemma 2.2. Let $(c,\lambda /\mu )$ be a placed skew shape with $n$ boxes and let $L$ be a standard tableau of shape $\lambda /\mu \text{.}$ Let $L\left(i\right)$ denote the box containing i in $L\text{.}$ The content sequence

$$(c\left(L\left(1\right)\right),\dots ,c\left(L\left(n\right)\right))$$

uniquely determines the shape $(c,\lambda /\mu )$ and the standard tableau $L\text{.}$

		Proof.
	Proceed by induction on the number of boxes of $L\text{.}$ If $L$ has only one box then the content sequence $\left(c\left(L\left(1\right)\right)\right)$ determines the placement of that box. Assume that $L$ has $n$ boxes. Let $L\prime$ be the standard tableau determined by removing the box containing $n$ from $L\text{.}$ Then $L\prime$ is also of skew shape and the content sequence of $L\prime$ is $(c\left(L\left(1\right)\right),\dots ,c\left(L(n-1)\right))\text{.}$ By the induction hypothesis we can reconstruct $L\prime$ from its content sequence. Then $c\left(L\left(n\right)\right)$ determines the diagonal which must contain box $n$ in $L\text{.}$ So $L\prime$ and $c\left(L\left(n\right)\right)$ determine $L$ uniquely. $\square$

Notes and References

This is an excerpt of the preprint entitled Skew shape representations are irreducible authored by Arun Ram in 1998.

Research supported in part by National Science Foundation grant DMS-9622985, and a Postdoctoral Fellowship at Mathematical Sciences Research Institute.

page history