Class Note for MATH 796 at KU 2
Popular in Course
Popular in Department
This 5 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at Kansas taught by a professor in Fall. Since its upload, it has received 24 views.
Reviews for Class Note for MATH 796 at KU 2
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 02/06/15
Wednesday 430 The RSK Correspondence De nition 1 Let A b n A standard Young tableau of shape A is a lling of the Ferrers diagram of A with the numbers 1 2 l l l n that is increasing lefttoright and toptobottoml We write SYT A for the set of all standard tableaux of shape A and set F lSYTAl For example if A 33 then f 5 the members of SYTA are as follows The RSK correspondence for Robinson Schensted Knuth constructs for every permutation w E G a pair RSKw P of standard tableaux of the same shape A b n The idea is to rowinsert the numbers 101102 1107 into P one by one and to use Q to record the order in which cells are added Example 1 Let w 57214836 E 63 We start with a pair P of empty tableauxl Step 1 Rowinsert wl 5 into Pl We do this in the obvious way Since it s the rst cell added we add a cell containing 1 to Q Step 2 Rowinsert 112 7 into Pl Since 5 lt 7 we can do this by appending the new cell to the top row and adding a cell labeled 2 to Q to record where welve put the new cell in Pl 1 Q Step 3 Rowinsert wg 2 into Pl This is a bit trickier We canlt just append a 2 to the rst row of P because the result would not be a standard tableaul The 2 has to go in the top left cell but that already contains a 5 Therefore the 2 bumps the 5 out of the rst row into a new second rowl Again we record the location of the new cell by adding a cell labeled 3 to 1b 10 Step 4 Rowinsert w4 1 into Pl This time the new 1 bumps the 2 out of the rst rowl The 2 has to go into the second row but again we canlt simply append it to the right Instead the 2 bumps the 5 out of the second row into the new third rowl 101 Step 5 Rowinsert w5 4 into P The 4 bumps the 7 out of the rst row The 7 however can comfortably t at the end of the second row without any more bumping 1 4 1 2 2 7 3 5 16 5 4 Step 6 Rowinsert wt 8 into P The 8 just goes at the end of the rst row 1 4 8 1 2 6 2 7 3 5 1f 5 4 Step 7 Rowinsert w7 3 into P 3 bumps 4 and then 4 bumps 7 1 3 8 1 2 6 2 4 3 5 5 7 4 7 1g Step 8 Rowinsert W3 6 into P 6 bumps 8 into the second row 1 3 6 1 2 6 2 4 8 3 5 8 1h 5 7 4 7 A crucial feature of the RSK correspondence is that it can be reversed That is given a pair P Q we can recover the permutation that gave rise to it Example 2 Suppose that we were given the pair of tableaux in 1h What was the previous step To get the previous Q we just delete the 8 As for P the last cell added must be the one containing 8 This is in the second row so somebody must have bumped 8 out of the rst row That somebody must be the largest number less than 8 namely 6 So 6 must have been the number inserted at this stage and the previous pair of tableaux must have been those in lg Example 3 Suppose P is the standard tableau with 18 boxes shown on the left 12581018 1258 18 341112 3411 6 713 6 7 91517 9 17 1416 14 Suppose in addition that we know that the cell labeled 16 was the last one added because the corresponding cell in Q contains an 18 Then the bumping path77 must be as shown on the right That is the 16 was bumped by the 15 which was bumped by the 13 and so on To nd the previous tableau in the algorithm we push every number in the bumping path up and toss out the top one 5 8 18 11 17 l 411 3 6 9 14 That is we must have gotten the original tableau by rowinserting 10 into the tableau just showni Since the correspondence is reversible we have the following fact Theorem 1 The RSK correspondence is a bijection 6 U SYT gtlt SYT1 Abn Some Nice Properties of RSK Here is an immediate consequence of Theorem 1 Corollary 2 SAMOA nl To con rm this for n 3 here are all the SYT7s with 3 boxes Note that f3 f1gt1gt1 l and fed 2 and 12 12 22 6 3 This calculation ought to look familiar Another neat fact about the RSK correspondence is this Proposition 3 Let w E G If RSKw P Q then RSKw 1 QP In particular the number of involutions in 6 is Min Generalized RSK and Schur Functions The RSK correspondence can be extended to obtain more general tableaux than just SYT sl We can think of a permutation in twoline notation ilel 57214836lt12 3 4 5 6 7 8gtl 5 7 2 l 4 8 3 6 What if we allowed generalized permutations ilel things of the form 797041042quot3904n lt2 1121 b2 b where aibi E n and the ordered pairs a1b1luanbn are in lexicographic order but repeats are allowed Example 4 Consider the generalized permutation 7112444555 w 241133224 We can rowinsert the elements of the bottom row into a tableau P while recording the elements of the top row in a tableau Q Q 4 1 2 2 1 24 24 etc The tableaux PQ we get in this way will always be weakly increasing eastward and strictly increasing southwardithat is they will be columnstrict tableaux Moreover their weights will be Q 1PIa1quot39ran7 I 151quot39Ibn Meanwhile a generalized permutation w as in 2 can be encoded by an n X n matrix M E Nnxn with mij ah i 12h For example the generalized permutation w of Example 4 corresponds to the integer matrix 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 1 0 2 0 0 0 2 0 1 0 Therefore7 PQESYT Z 2 1P Z W 28mm A PESYTO QESYTQ A Corollary 4 The Schur functions form an orthonormal Zbasis for A under the Hall inner product
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'