Limit shapes of bumping routes in the Robinson–Schensted correspondence1. Issue 1 (8th September 2014)

• Record Type: Journal Article
• Authors: Romik, Dan; Śniady, Piotr
• Is Part Of: Random structures & algorithms. Volume 48:Issue 1(2016)
• Page Start: 171
• Page End: 182
• Publication Date: 2014-09-08
• Subjects: Robinson–Schensted correspondence -- bumping routes -- Young tableau -- limit shape; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20570
• Languages: English
• ISSNs: 1042-9832

Abstract

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