Limit Shapes of Bumping Routes in The Robinson-Schensted Correspondence

作者：Romik Dan; Sniady Piotr^*

来源：Random Structures and Algorithms, 2016, 48(1): 171-182.

DOI：10.1002/rsa.20570

• Robinson-Schensted correspondence
• bumping routes
• Young tableau
• limit shape

We prove a limit shape theorem describing the asymptotic shape of bumping routes when the Robinson-Schensted algorithm is applied to a finite sequence of independent, identically distributed random variables with the uniform distribution U[0, 1] on the unit interval, followed by an insertion of a deterministic number alpha. The bumping route converges after scaling, in the limit as the length of the sequence tends to infinity, to an explicit, deterministic curve depending only on alpha. This extends our previous result on the asymptotic determinism of Robinson-Schensted insertion, and answers a question posed by Moore in 2006.

• 出版日期2016-1