Limit shapes of bumping routes in the Robinson-Schensted correspondence

Abstract

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 $α$. 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 $α$. This extends our previous result on the asymptotic determinism of Robinson-Schensted insertion, and answers a question posed by Moore in 2006.

14 pages