## Algebraic combinatorics Lecture 4: patience sorting, symmetry of schur functions and Kostka numbers

Recall the definition of skew Young tableaux and their Schur functions ${\lambda \setminus \mu}$ and ${s_{\lambda \setminus \mu}}$. When ${\mu = \emptyset}$, we get the usual Schur functions .The reason we consider skew tableaux is

1. they are related to skew characters of ${S_n}$ to be discussed later.
2. the argument for symmetry goes through easily for the skew case as well.

Proposition 1 ${s_{\lambda \setminus \mu}}$ is symmetric.

Proof: Recall the definition

$\displaystyle s_{\lambda \setminus \mu}: = \sum_{T \text{ SSYT of shape } \lambda \setminus \mu} x^T \ \ \ \ \ (3)$

Let ${\alpha = (\alpha_1, \alpha_2, \ldots)}$ be the type of a SSYT of shape ${\lambda \setminus \mu}$ and ${\bar{\alpha} = (\alpha_1, \alpha_2, \ldots, \alpha_{i-1}, \alpha_{i+1}, \alpha_i, \ldots)}$ be ${\alpha}$ with two entries switched. ${T_{\lambda \setminus \mu ,\alpha}}$ be the set of SSYT of ${\lambda \setminus \mu}$ with type ${\alpha}$. It would suffice to find a bijection between ${T_{\lambda \setminus \mu ,\alpha}}$ and ${T_{\lambda \setminus \mu ,\bar{\alpha}}}$, since adjacent transpositions generate ${S_n}$ and switching ${x_{i+1}}$ and ${x_i}$ in ${s_{\lambda \setminus \mu}}$ is equivalent to switching the number of SSYTs of type ${\alpha}$ and ${\bar{\alpha}}$. The bijection is defined as following: take any ${y \in T_{\lambda \setminus \mu ,\alpha}}$. Delete all the columns of ${y}$ with both ${i+1}$ and ${i}$. For the remaining filled in diagram, each row consist of a bunch of ${i}$‘s and ${i+1}$‘s, say row ${j}$ has ${a_j}$ ${i}$‘s and ${b_j}$ ${i+1}$‘s. The in the spaces occupied by ${i}$‘s and ${i+1}$‘s in row ${j}$, fill in the first ${b_j}$ spaces with ${i}$‘s and the last ${a_j}$ spaces with ${i+1}$‘s, i.e., switching the number of ${i}$‘s and ${i+1}$‘s, while preserving the weak increasingness. The resulting diagram when combined with the deleted columns will still be a valid SSYT for ${\lambda \setminus \mu}$, and clearly is of type ${\bar{\alpha}}$, hence defines a bijection. $\Box$

Definition 2 The Kostka numbers ${K_{\lambda \setminus \mu, \alpha}}$ are the change of basis coefficients from skew-Schur to monomial. Clearly

$\displaystyle m_\alpha = x^T \ \ \ \ \ (4)$

where ${T}$ is any SSYT of ${\lambda \setminus \mu}$ with type ${\alpha}$, viewed as a partition ${(1^{\alpha_1} 2^{\alpha_2} \ldots)}$.

By definition of Schur function in terms of the ${x^T}$,’s, ${K_{\lambda \setminus \mu, \alpha} =}$ the number of SSYT of shape ${\lambda \setminus \mu}$ and type ${\alpha}$.

Proposition 3 If ${\lambda, \mu \vdash n}$, ${K_{\lambda, \mu} \neq 0}$, then ${\lambda \ge \mu}$ in dominance ordering.

Norbert Wiener proved this when he was 16, but it’s not hard. Proof: The assumption implies the existence of some SSYT ${T}$ of shape ${\lambda}$ type ${\mu}$. Then

1. T has ${\mu_1}$ 1’s, all of which must fit in the first row of ${\lambda}$.
2. ${\mu_1 + \mu_2}$ 1’s and 2’s all fit in the first 2 rows of ${\lambda}$.
3. ${\ldots}$

The claim follows from the definition of dominance relation. $\Box$

From the above proof, ${K_{\lambda, \lambda} =1}$ is also clear. Thus

$\displaystyle s_\lambda = m_\lambda + \sum_{\mu < \lambda} K_{\lambda, \mu} m_\mu, \ \ \ \ \ (5)$

i.e., under any total refinement of the dominance ordering, ${K_{\lambda, \mu}}$ is unipotent lower triangular.

Corollary 4 ${\{s_\lambda\}_{\lambda \vdash n}}$ is a ${{\mathbb Z}}$-basis for ${\Lambda^n}$, because the change of basis equations are monic.

As a remark, computing ${K_{\lambda, \mu}}$ is ${\#}$-P complete. But some special cases can be computed:

1. ${\lambda}$ is anything, ${\mu = 1^n}$, then ${K_{\lambda, \mu} = f(\lambda)}$, the dimension of the irrep of ${S_n}$ associated with ${\lambda}$.
2. ${\mu}$ anything, ${\lambda = (n)}$, ${K_{\lambda, \mu} \equiv 1}$.

Proposition 5 (Sketched inline item 2) ${f(\lambda)}$ enumerates

1. saturated paths in patitions from ${\emptyset}$ to ${\lambda}$. Proof follows from the item below.
2. Ballot sequences: suppose we have ${f}$ candidates in an election, ${A_i}$ votes for ${i}$ in the end, ${\sum_{i=1}^f A_i = n}$. How many ways can these be drawn so that candidate ${i}$ is never behind ${i+1}$? This number is ${f(\lambda)}$, where ${\lambda = (A_1, \ldots, A_f)}$. If ${\lambda = (n,n)}$, it specializes to the Catalan number ${\frac{\binom{n}{2}}{n+1}}$. Finally if ${a_1, a_2, \ldots, a_n \in [f]}$ is a Ballot sequence, we can build SYT by placing ${j}$ in row ${i}$ if ${a_j = i}$: eg., ${11122 \mapsto (123)(45)}$. We use the latter notation to denote Young tableau with two rows: first row being 123, second being 45. Thus we have a bijection between the Ballot sequence and Young tableaux with type ${1^n}$ (hence a proof).
3. Lattice paths in ${{\mathbb R}^l}$, where ${l = l(\lambda)}$ is the number of parts of ${\lambda}$. Of course this is just a restatement of item 1.

There is a version of Kolmogorov Smirnov statistics defined in terms of ${f(\lambda)}$. Next we talk about one of the big topics in the course: Robinson-Schensted-Knuth algorithm. Patience sorting: a toy version of Solitaire (whose winning probability is not computed). Take a well-shuffled deck of ${n}$ cards. Turn the cards up one at a time:

• play low card or high card
• if turn up higher than any showing, start a new pick
• objective is to have as few piles as possible

Greedy algorithm is to put each card in the left most possible pile. Then For ${\omega \in S_n}$, let ${l(\omega)= }$ the length of the longest increasing subsequence of ${\omega(1), \omega(2), \ldots, \omega(n)}$. then

1. Any strategy of patience sorting on the deck ${(\omega(1), \ldots, \omega(n))}$ has at least ${l(\omega)}$ piles.
2. Greedy achieves this.

Proof: The first point is clear, since the cards in any increasing subsequence must be on different piles by the rule of the game. To show that greedy is good, let ${p_i}$ be the pile card ${i}$ is in. Define for each card ${i}$ a pointer function ${f(i)=}$ the last card to be placed on pile ${p_i-1}$ before ${i}$ is placed on ${p_i}$. ${f}$ is undefined on cards in the first pile (but it’s ok). Now start at any card ${j}$ in the last pile ${p_j = m}$. Then it’s predecesor ${f(j) < j}$, because otherwise one could put card ${j}$ on top of ${f(j)}$ in pile ${m-1}$. Continuing, we get an increasing subsequence in reverse order ${j > f(j) > f^2(j) > \ldots }$. $\Box$

In fact Patience sorting is provably the fastest algorithm for computing ${l(\omega)}$. We also have ${d(\rm{id}, \omega) = n - l(\omega)}$, where ${d(\sigma, \tau)}$ is a metric on ${S_n}$ (found in Knuth vol III), given by the minimum number of deletion and insertion moves needed to go from ${\sigma}$ to ${\tau}$, i.e., pairwise rotation. Motivation: Pick ${\omega \in S_n}$ at random, what is the distribution of ${l(\omega)}$? Ulam’s problem: ${\mathbb{E} l(\omega) = 2 \sqrt{n} + o(\sqrt{n})}$. proved by Virshick-Kerov, and Logam-Shepp (1979)

$\displaystyle \lim_n \mathbb{P} (\frac{l(\omega) - 2 \sqrt{n}}{n^{1/6}} \le x) = F(x) := \exp[\int_x^\infty (x-t) q^2(t) dt] \ \ \ \ \ (6)$

where ${q}$ satisfies the Painleve II ODE

$\displaystyle q' = x q + q^2 \ \ \ \ \ (7)$

with ${q(x) \sim \rm{AI}(x)}$ as ${x \rightarrow \infty}$, where ${\rm{AI}}$ is the Airy function. Baik-Deift-Johansson have shown that the largest eigenvalue of GUE properly normalized also converges to ${F}$, the Tracy-Widom distribution.

Advertisements

## About aquazorcarson

math PhD at Stanford, studying probability
This entry was posted in algebraic combinatorics, Uncategorized and tagged , , . Bookmark the permalink.