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.


About aquazorcarson

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

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s