The Robinson-Schensted-Knuth bijection, quantum matrices and piece-wise linear combinatorics

Arkady Berenstein and Anatol N. Kirillov

To appear at Formal Power Series and Algebraic Combinatorics (FPSAC01), Tempe, Arizona (USA), May 20-26, 2001


We explicitly compute the celebrated Robinson--Schensted--Knuth bijection (RSK) between the set of the matrices with non-negative integer entries, and the set of the plane partitions. More precisely, in suitable linear coordinates on both sets, the RSK is expressed via minima of linear forms, i.e, in piece--wise linear terms. In particular, we answer the following question by C.~Greene and G.~Viennot: ``What shape corresponds to a given matrix under the Robinson--Schensted--Knuth correspondence?" Our main tools in establishing these formulae are the quantum matrices and crystal bases. As a byproduct of our approach, we compute the corresponding crystal equivalence in terms of "generalized" Kazhdan--Lusztig polynomials.

Server START Conference Manager
Update Time 23 Feb 2001 at 08:48:02
Start Conference Manager
Conference Systems