Essays on representations of finite groups An elementary introduction to the Robinson-Schensted-Knuth algorithm

This essay is about the algorithm of Robinson, Schensted, and Knuth, which establishes a bijection between the symmetric group Sn and pairs of Young tableaux of size n and the same shape. There is already a huge literature on this topic, but it seems to me that the RSK algorithm is familiar to us only through habituation, not through any good understanding as to how one might have come across it to begin with. That is what I hope to supply here. In a future version, I’ll include a discussion of the result that the equivalence defined by the Knuth relations onSn is the same as those defined by theW graph defined in [KazhdanLusztig:1979]. I’ll also discuss the application of [Steinberg:1988]. I begin with the problem that motivated Schensted’s original paper, that of finding subsequences of maximal length in an arbitrary sequence of distinct integers. But I believe that the best motivation of Schensted’s algorithm comes from something even more natural, the problem of assigning ranks in a partially ordered set, and that is where I actually start. In this I am expanding the treatment in §4 of [Knuth:1970] (see also §5.1.4 of [Knuth:1975])