most recent 30 from http://mathoverflow.net 2013-05-23T20:52:15Z http://mathoverflow.net/feeds/question/90540 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/90540/the-number-of-rows-in-a-tableau-generated-by-the-rsk-algorithm Igor Makhlin 2012-03-08T04:18:55Z 2012-03-08T13:39:44Z

<p>It is well known that the number of rows in the semistandard Young tableaux correspondent to a two-line array via RSK is equal to the length of the longest (strictly) decreasing subsequence in the array's second line, in the case the array's columns are ordered lexicographically. Note that this statement by itself involves nothing more than the definition of Schensted's row insertion procedure (row bumping). Namely, it can be rephrased in the following way: the number of rows in $(\ldots((\emptyset\leftarrow x_1)\leftarrow x_2)\leftarrow\ldots)\leftarrow x_n$ is equal to the length of the longest decreasing subsequence in $(x_1,x_2,\ldots,x_n)$, where $\leftarrow$ is row insertion and $\emptyset$ denotes the empty tableau.</p> <p>However, proofs of this fact I've come across are quite complicated in the sense that they tend to employ some more or less advanced theoretic basis. For an example see exercise 1 in §3.2 of W. Fulton's book "Young tableaux: with applications to representation theory and geometry" and the proposed solution to it. I'm looking for a short self-contained proof of the above statement considering row insertion.</p> <p>Actually, I'd be more than satisfied by such a proof for the number of rows not exceeding the length of the longest decreasing subsequence. <strike> Note that the in a way dual fact of the number of columns not exceeding the length of the longest nondecreasing subsequence is nearly obvious. </strike> It may not be obvious but can certainly be proven very simply, see <a href="http://cms.math.ca/cjm/v13/cjm1961v13.0179-0191.pdf" rel="nofollow">Schensted's original paper</a>.</p> <p><b> Clarification. </b> By short I mean really short. Short enough to post as 1-2 screen long answer here without a single external reference. Once again, the motivation here is that the standard proof of the "dual" statement definitely satisfies this criterion. </p>