Limit shapes of bumping routes in the Robinson–Schensted correspondence |
| |
| Authors: | Dan Romik Piotr Śniady |
| |
| Affiliation: | 1. Department of Mathematics, University of California, Davis, California;2. Zentrum Mathematik, M5, Technische Universit?t München, Garching, Germany;3. Instytut Matematyczny, Polska Akademia Nauk, Warszawa, Poland;4. Instytut Matematyczny, Uniwersytet Wroc?awski, Wroclaw, Poland |
| |
| 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 |
| |
| Keywords: | Robinson– Schensted correspondence bumping routes Young tableau limit shape |
|
|
