Limit shapes of bumping routes in the Robinson-Schensted correspondence

Dan Romik, Piotr Śniady

Published 2013-04-29, updated 2014-07-04Version 2

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.