The symmetric functions catalog

An overview of symmetric functions and related topics

2023-08-17

The Robinson–Schensted–Knuth correspondence

The Robinson–Schensted–Knuth correspondence (RSK), is a bijection between matrices with non-negative integer entries and pairs of semi-standard Young tableaux of the same shape. Let $M(\mu,\nu)$ denote the set of matrices with entries in $\setN,$ row sums are determined by $\mu$ and column sums determined by $\nu.$ The RSK correspondence provides the following bijections, where $\lambda,$ $\mu$ are integer partitions of $n$:

\begin{align} M(\mu,\nu) & \qquad \rskArrow \qquad \bigcup_{\lambda \vdash n} \SSYT(\lambda,\nu) \times \SSYT(\lambda,\mu) \\ [d]^n & \qquad \rskArrow \qquad \bigcup_{\lambda \vdash n} \SSYT(\lambda,d) \times \SYT(\lambda) \\ \symS_n & \qquad\rskArrow \qquad \bigcup_{\lambda \vdash n} \SYT(\lambda) \times \SYT(\lambda) \\ \{\sigma \in \symS_n : \sigma^2 = e \} & \qquad \rskArrow \qquad \bigcup_{\lambda \vdash n} \SYT(\lambda). \end{align}

In particular, the first bijection proves the first Cauchy identity for Schur functions. The second variant of RSK proves the second Cauchy identity.

For an excellent overview on the different variants of RSK, see C. Krattenthaler's survey [Kra06]. We shall cover the same four variants of RSK as in his paper and keep the same numbering. See also [App. A.4.3, Ful97] and [Sag01] for more resources on RSK.

See the evacuation section on how RSK interacts with evacuation.

Row insertion

In order to describe RSK, we need the notion of row insertion. Given a SSYT $T$ and $k \in \setN,$ the insertion $T \leftarrow k$ recursively as follows, where $T_1$ is the first row of $T$ and $T_{2\sim}$ denotes the SSYT with the first row of $T$ removed.

  1. If $T = \emptyset,$ then $T \leftarrow k$ is just the tableau
    $k$
    .
  2. If $k$ is not smaller than the largest entry in $T_1,$ then $T \leftarrow k$ is given by appending $k$ at the end of the first row of $T.$
  3. Otherwise, find the leftmost entry in $T_1$ larger than $k,$ and let this be $k'.$ The insertion $T \leftarrow k$ is then given as the tableau with first row $T_1,$ except that $k'$ has been replaced by $k,$ and the remaining rows are given by the insertion $T_{2\sim} \leftarrow k'.$

Given a word $w,$ inserting the letters one by one gives the insertion tableau, $\ins(w).$ This is sometimes denoted $P(w).$

Example.

Inserting the entries $w = 34112312$ from left to right gives the following sequence of tableaux, where $\ins(w)$ is the last.

$3$
$3$$4$
$1$$4$
$3$ 
$1$$1$
$3$$4$
$1$$1$$2$
$3$$4$ 
$1$$1$$2$$3$
$3$$4$  
$1$$1$$1$$3$
$2$$4$  
$3$   
$1$$1$$1$$2$
$2$$3$  
$3$$4$  
Theorem (Greene's theorem, [Gre74Sag01]).

Let $\pi$ be a permutation and let $I_k(\pi)$ denote the length of the longest sub-word of $\pi$ that can be expressed as a disjoint union of $k$ increasing subsequences of $\pi.$ Similarly, let $D_k(\pi)$ be the length of the longest subword of $\pi$ that can be expressed as a disjoint union of $k$ decreasing subsequences of $\pi.$

Let $\lambda$ be the shape of $P(\pi).$ Then

\[ I_k(\pi) = \lambda_1+\dotsb + \lambda_k \qquad D_k(\pi) = \lambda'_1+\dotsb + \lambda'_k. \]
Example (An application: Erdős–Szekeres theorem).

The Erdős–Szekeres theorem[ES09] states that any sequence of distinct real numbers of length $(r-1)(s-1)+1$ contains a monotonically increasing subsequence of length $r,$ or a monotonically decreasing subsequence of length $s.$

Suppose we have a sequence $w$ of such numbers. We apply row insertion on this sequence, and obtain a tableau $P$ (with real numbers). Note that this tableau cannot be contained in an $(r-1)\times (s-1)$-rectangle, so either the first row is longer than $r,$ or the first column is longer than $s.$

Application of Greene's theorem finishes the proof.

RSK (variant I)

The RSK correspondence is done in two steps. A matrix $A \in M(\lambda,\mu)$ is first turned into a biword $W$ of length $n$ as follows. For each entry $A_{ij},$ we have $A_{ij}$ columns in $W$ equal to $\binom{i}{j}.$ Furthermore, the columns are ordered lexicographically, with respect to the top-most value first.

Given a pair $(P,Q)$ of SSYT of the same shape, the insertion $(P,Q) \leftarrow \binom{i}{j} $ is defines as the pair $(P',Q'),$ where $P' = P \leftarrow j$ and $Q'$ is obtained from $Q$ by putting $i$ in the box where the last insertion took place to get $P'.$

Finally, the pair $(P,Q)$ in the correspondence $W \rskArrow (P,Q)$ is obtained by inserting each column $\binom{i}{j}$ from left to right in $W.$ One can prove that $(P,Q)$ is indeed a pair of semi-standard Young tableaux, provided that $W$ correspond to some matrix $A.$ We refer to $P = \ins(W)$ as the insertion tableau and $Q=\rec(W)$ as the recording tableau.

Example.

The word

\begin{equation*} W= \begin{pmatrix} 1& 1& 1& 2& 2& 3& 3& 4 \\ 1& 3& 4& 1& 2& 1& 3& 2 \end{pmatrix} \end{equation*} is mapped to the pair $(P,Q)$
$1$$1$$1$$2$
$2$$3$  
$3$$4$  
$1$$1$$1$$3$
$2$$2$  
$3$$4$  
Theorem (Greene's theorem for words, [Gre74Sag01]).

Let $W$ be a biword with lexicographically sorted columns. We use $I_k(W)$ and $D_k(W)$ to denote $k$-weakly increasing and $k$-strictly decreasing subwords of the bottom row of $W.$

Let $\lambda$ be the shape of $\ins(W).$ Then

\[ I_k(W) = \lambda_1+\dotsb + \lambda_k \qquad D_k(W) = \lambda'_1+\dotsb + \lambda'_k. \]

Dual RSK (variant II)

There is a dual notion of row insertion, called column insertion, traditionally indicated with a right-pointing arrow. We now insert into dual SSYT. A dual SSYT is a filling that is the transpose of an SSYT.

Given a dual SSYT $T$ and $k \in \setN,$ the dual insertion $k \to T $ is defined recursively as follows where $T_1$ is the first row of $T$ and $T_{2\sim}$ denotes the dual SSYT with the first row of $T$ removed.

  1. If $T = \emptyset,$ then $k \to T$ is just the tableau
    $k$
    .
  2. If $k$ is greater than the largest entry in $T_1,$ then $k \to T$ is given by appending $k$ at the end of the first row of $T.$
  3. Otherwise, find the leftmost entry in $T_1$ larger than or equal to $k,$ and let this be $k'.$ The insertion $k \to T$ is then given as the tableau with first row $T_1,$ except that $k'$ has been replaced by $k,$ and the remaining rows are given by the insertion $k' \to T_{2\sim}.$

This series of operations correspond to inserting boxes in the columns of $T^t,$ hence the name.

Example.

Dual-inserting the entries $w=34112312$ from left to right gives the following sequence of tableaux, where $P$ is the last.

$3$
$3$$4$
$1$$4$
$3$ 
$1$$4$
$1$ 
$3$ 
$1$$2$
$1$$4$
$3$ 
$1$$2$$3$
$1$$4$ 
$4$  
$1$$2$$3$
$1$$4$ 
$1$  
$3$  
$1$$2$$3$
$1$$2$ 
$1$$4$ 
$3$  

Dual RSK is defined on biwords such that there are no duplicate columns. We denote the dual RSK map as $W \rskDualArrow (P,Q),$ and we obtain a pair of tableaux such that $P$ is dual semistandard and $Q$ is semistandard. Let $B(\mu,\nu)$ denote the set of binary matrices with given row- and column-sums. Dual RSK provides the following bijections:

\begin{align} B(\mu,\nu) & \qquad \rskDualArrow \qquad \bigcup_{\lambda \vdash n} \SSYT(\lambda',\nu) \times \SSYT(\lambda,\mu) \\ [d]^n & \qquad \rskDualArrow \qquad \bigcup_{\lambda \vdash n} \SSYT(\lambda',d) \times \SYT(\lambda) \\ \symS_n & \qquad\rskDualArrow \qquad \bigcup_{\lambda \vdash n} \SYT(\lambda') \times \SYT(\lambda) \\ \{\sigma \in \symS_n : \sigma^2 = e \} & \qquad \rskDualArrow \qquad \bigcup_{\lambda \vdash n} \SYT(\lambda). \end{align}
Example (Dual RSK biword insertion).

The matrix and corresponding word

\begin{equation*} A = \begin{pmatrix} 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \end{pmatrix} \qquad W= \begin{pmatrix} 1& 1& 1& 2& 2& 3& 3& 4 \\ 1& 3& 4& 1& 2& 1& 3& 2 \end{pmatrix} \end{equation*} is mapped to the pair $(P,Q)$
$1$$2$$3$
$1$$2$$4$
$1$$3$ 
$1$$1$$1$
$2$$2$$3$
$3$$4$ 
Proposition (RSK vs. dual RSK).

Let $\pi \in \symS_n.$ Then [Thm. 4.1.1, van95] states that the following are equivalent:

  • $\pi \rskArrow (P,Q)$
  • $n+1-\pi \rskDualArrow (\evac(P^t),Q^t)$
  • $\rev(\pi) \rskDualArrow (P^t,\evac(Q^t))$
  • $\revCompl(\pi) \rskArrow (\evac(P^t),\evac(Q^t))$
  • $\revCompl(\pi) \rskDualArrow (\evac(P),\evac(Q))$

The following extension is proved in [Prop. 2.3.14, But94]. Let $w \in [d]^n$ be a word. We have that

\[ w \rskArrow P \iff \rev(w) \rskDualArrow P^t. \]

This property generalizes to biwords, see this section.

RSK (variant III)

In the usual RSK we require that the biword $W$ is sorted in a lexicographical fashion. Suppose instead the columns $\binom{i}{j}$ are sorted first on $i$ and in case of equality, sort decreasingly with respect to $j.$ Furthermore, we impose the same condition as in dual RSK that two columns may not be identical. We call such biwords Burge words as this ordering was studied in Burge insertion.

Each binary matrix $B$ give rise to a Burge word by recording the row and column coordinates of the ones. That is, if $B_{ij}=1$ then $\binom{i}{j}$ appear as a column in the corresponding biword. For example,

\[ \begin{pmatrix} 1 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 \end{pmatrix} \qquad \longleftrightarrow \qquad \begin{pmatrix} 1 & 1 & 2 & 2 & 2 & 3 \\ 4 & 1 & 3 & 2 & 1 & 3 \end{pmatrix} \]

In this setting, we write $W \rskbArrow (P,Q)$ if the biword $W$ is first sorted in the Burge fashion and the entries are inserted using row insertion.

For this map, we have that $W \rskbArrow (P,Q)$ where $P$ and $Q^T$ are semistandard tableaux of the same shape and we get a second set of bijections. We let $B(\mu,\nu)$ denote the set of binary matrices with row sums $\mu$ and column sums $\nu.$

\begin{align} B(\mu,\nu) & \qquad \rskbArrow \qquad \bigcup_{\lambda \vdash n} \SSYT(\lambda,\nu) \times \SSYT(\lambda',\mu) \\ [n]^n & \qquad \rskbArrow \qquad \bigcup_{\lambda \vdash n} \SYT(\lambda) \times \SSYT(\lambda') \\ \symS_n & \qquad \rskbArrow \qquad \bigcup_{\lambda \vdash n} \SYT(\lambda) \times \SYT(\lambda') \end{align}
Example (Burge biword insertion).

The matrix and corresponding word

\begin{equation*} A = \begin{pmatrix} 1 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 \end{pmatrix} \qquad W= \begin{pmatrix} 1& 1& 1& 2& 2& 3& 3& 4 \\ 4& 3& 1& 3& 1& 2& 1& 2 \end{pmatrix} \end{equation*}

is mapped to the pair $(P,Q)$ below.

$1$$1$$1$$2$
$2$$3$  
$3$   
$4$   
$1$$2$$3$$4$
$1$$2$  
$1$   
$3$   
Proposition (See [Kra06] and [p. 200, Ful97]).

Let $B$ be a binary matrix. Then

\[ B \rskbArrow (P,Q) \iff B^T \rskDualArrow (Q,P). \]

Using biwords, this can be phrased as

\[ \binom{w_1}{w_2} \rskbArrow (P,Q) \iff \binom{w_2}{w_1} \rskDualArrow (Q,P). \]

Knuth relations

Let $A$ be an alphabet. The plactic monoid is the quotient $A^*/\equiv,$ where $\equiv$ is the equivalence class generated by the Knuth relations

\begin{align*} xzy \equiv zxy &\quad (x\leq y \lt z) \\ yxz \equiv yzx &\quad (x\lt y \leq z). \end{align*}

Two words $w$ and $w'$ are Knuth-equivalent if and only if they have the same insertion tableau, $T.$ Moreover, the reading word of $T$ is also Knuth-equivalent to $w,$ and it is the unique word in the equivalence class which is the reading word of a semistandard tableau, see [p.22, Ful97] or [Cor. 2.3.21, But94].

Dual Knuth relations

Two words $w$ and $w'$ are dual Knuth-equivalent if and only if they have the same recording tableau.

An elementary dual Knuth transformation on a permutation on a permutation $\sigma_1,\dotsc,\sigma_n$ interchanges $\sigma_i =k$ and $\sigma_j =k+1$ if and only if $k-1$ or $k+2$ occur somewhere between.

For example, $\underline{5}34\underline{6}7182$ and $\underline{6}34\underline{5}7182$ are equivalent, since $4$ appear between them.

Two words are dual Knuth equivalent if and only if one can be transformed to the other via elementary dual Knuth transformations, see [p.200, Ful97].

Properties of RSK

Here is an overview of the properties of RSK. Note that RSK is closely connected to charge.

  • For $A \in M(\mu,\nu),$ \[ A \quad \rskArrow \quad (P,Q) \qquad \iff \qquad A^{T} \quad \rskArrow \quad (Q,P). \]
  • For a permutation $\pi \in \symS_n,$ the following statements are equivalent, see [A.1.2.11, Sta01]. \begin{align} \pi \quad &\rskArrow \quad (P,Q) \\ \pi^{-1} \quad &\rskArrow \quad (Q,P) \\ \rev(\pi) \quad &\rskArrow \quad (P^t, \evac(Q)^t) \end{align}

    For dual RSK, we have the same properties: \begin{align} \pi \quad &\rskDualArrow \quad (P,Q) \\ \pi^{-1} \quad &\rskDualArrow \quad (Q,P) \\ \rev(\pi) \quad &\rskDualArrow \quad (P^t, \evac(Q)^t) \end{align}

  • For words, $w \equiv w'$ if and only if $\ins(w)=\ins(w').$
  • If $w \equiv w',$ then $\charge(w)=\charge(w').$
  • We have that \[ \sum_{\sigma \in \symS_n} t^{\des(\sigma)} = \sum_{\lambda} f^{\lambda} \sum_{Q\in\SYT(\lambda)} t^{\des(T)}, \] since RSK maps descents on permutations to descents in tableaux.

  • If $\pi \rskArrow (P,Q)$ then $\sign(\pi) = \sign(P)\sign(Q)(-1)^e,$ where $\sign(T)$ is defined as $(-1)^{\inv(\rw(T))}$ and $e$ is the total length of the even-indexed rows in $P,$ see [Rei04].

RSK and standardization

RSK commutes with standardization, so if $W\rskArrow (P,Q)$ then $W'=\std(W)$ is mapped to $(\std(P),\std(Q)).$

Example.

We have that

\[ W=\begin{pmatrix} 1& 1& 1& 2& 2& 3 \\ 1& 2& 2& 1& 1& 2 \end{pmatrix} \]

is mapped to the pair

$1$$1$$1$$2$
$2$$2$  
$1$$1$$1$$3$
$2$$2$  

and the standardization of the word

\[ W'=\begin{pmatrix} 1& 2& 3& 4& 5& 6 \\ 1& 4& 5& 2& 3& 6 \end{pmatrix} \]

is mapped to the following pair of standard Young tableaux.

$1$$2$$3$$6$
$4$$5$  
$1$$2$$3$$6$
$4$$5$  
Lemma.

We have that for $w \in [d]^n,$

\[ \rev(w) \rskDualArrow P \implies \std(w) \rskArrow \std(P^t), \]

and

\[ (\rev \circ w) \rskDualArrow P \implies (\rev \circ \std \circ w) \rskDualArrow \std(P^t)^t. \]
Proof.

From [Prop. 2.3.14, But94] we have that

\[ w \rskArrow P \iff \rev(w) \rskDualArrow P^t. \]

This together with the fact that usual RSK commutes with standardization gives the first statement. It is then easy to derive the second statement as well.

Skew RSK

B. Sagan and R. Stanley consider a skew extension of RSK http://www-math.mit.edu/~rstan/pubs/pubfiles/76.pdf.

Also, I recommend the FPSAC2020 talk, https://www.youtube.com/watch?v=SeFLyM3zDV0 on injections (seen as generalizations of permutations).

Statistical properties of RSK

See https://arxiv.org/pdf/2005.03147.pdf and https://arxiv.org/pdf/2005.14397.pdf

RSK and pattern avoidance

See this preprint, https://arxiv.org/pdf/1907.09451.pdf on how RSK can be applied to solve problems regarding pattern avoidance in permutations.

Rimhook RSK

In [Thm. 3, SW85], the authors define a bijection,

\[ \begin{pmatrix} H(1)& H(2)& \dotsc & H(\ell) \\ H_1& H_2& \dotsc & H_\ell \\ \end{pmatrix} \rskArrow_{d} (P,Q) \]

where $H(1), H(2),\dotsc, H(\ell)$ is a sequence of hook shapes of size $d,$ filled with $1,2,\dotsc,\ell$ and $H_1, H_2, \dotsc, H_\ell$ is the same sequence of hook shapes, but the values are permuted. The output is a pair $(P,Q)$ of $d$-rim-hook tableaux of the same shape. The map $\rskArrow_{d}$ can be decomposed into a $d$-tuple of usual RSK-maps.

As a corollary, they have that $d$-hook tableaux of shape $\lambda$ are in bijection with $d$-tuples of standard Young tableaux (with different entries!) whose shapes are given by the $d$-quotient of $\lambda.$

Hillman–Grassl correspondence

A $\lambda$-array is a filling of the Young diagram of shape $\lambda$ with non-negative integers. There are no other conditions. A reverse plane partition of shape $\lambda$ is a $\lambda$-array with weakly increasing rows and columns.

The Hillman–Grassl correspondence is a bijection from the set of $\lambda$-arrays to the set of reverse plane partitions of shape $\lambda.$

See http://sporadic.stanford.edu/reference/combinat/sage/combinat/tableau.html#sage.combinat.tableau.Tableau.hillman_grassl for definition.

The Pak–Sulzgruber correspondence

A different bijection is defined by I. Pak [Pak01], from reverse plane partitions to $\lambda$-arrays. The inverse of this map is called the Sulzgruber correspondence.

Signed permutations and RSK

See https://arxiv.org/pdf/math/0308265.pdf

Berele insertion for the symplectic case

In [Ber86], a version of Schensted insertion is described, which proves the identity

\[ (a_1+ a_1^{-1} + \dotsb + a_n + a^{-1}_{n})^m = \sum_{\lambda} Q^\lambda_m(n)\schurSp_\lambda(a_1,\dotsc,a_n) \]

where $\schurSp_\lambda(a_1,\dotsc,a_n)$ is a symplectic Schur function and $Q^\lambda_m(n)$ is the number of oscillating sequences of diagrams $\emptyset = \lambda^0,\lambda^1,\dotsc,\lambda^n = \lambda$ with length at most $n.$

https://arxiv.org/pdf/1705.05454.pdf

See also http://fpsac2019.fmf.uni-lj.si/resources/Proceedings/67.pdf for $SO(2n+1).$

Multiset RSK

See https://arxiv.org/pdf/1905.02071.pdf, https://arxiv.org/abs/math/0601514, https://arxiv.org/pdf/0705.2915.pdf, and https://www.macalester.edu/~halverson/papers/rsk-partition.pdf

Probabilistic RSK

In https://arxiv.org/pdf/2009.03526.pdf, a $qt$-deformation of RSK is described. The output consists of several tableaux (with some probabilities), and this proves a (squarefree) version of the Cauchy identity for Macdonald polynomials.

Geometric RSK

There is a geometric lift of RSK, where the classical RSK is given by the tropicalization of this lift. The Whittaker functions then take the place of Schur functions. See https://maths.ucd.ie/~noconnell/pubs/cosz.pdf

Key polynomials and RSK

References