A common false belief regarding patience sorting and RSK

The precedure of patience sorting is deceptively similar to the RSK algorithm that one might fathom more is true besides the coincidence about the longest increasing subsequence. For instance, I had always believed that the column sizes of the output from both algorithms match. But the following counterexample flew right into my face:
take the permutation to be 134652, then patience sorting gives
2 5
1 3 4 6
whereas RSK yields the following standard Young tableau

1 2 4 5
3
8
It would be interesting to see the what the second and third rows of SYT correspond to in patience sorting.

Advertisements

About aquazorcarson

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

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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