### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Class Note for MATH 796 at KU 2

### View Full Document

## 24

## 0

## 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

### 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

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### 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'

## Why people love StudySoup

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "I used the money I made selling my notes & study guides to pay for spring break in Olympia, Washington...which was Sweet!"

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.