Limit shapes of bumping routes in the Robinson–Schensted correspondence1. Issue 1 (8th September 2014) - Romik, Dan; Śniady, Piotr
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. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 48, 171–182, 2016