Animation of the RSK construction for the Polynuclear growth (PNG) model
The blue points represents the nucleation events in space-time of the PNG model (space=horizontal axis, time=vertical axis). The dynamics of the PNG model is the following:
- stochastic part: randomly in space-time some nucleations occurs, and they create an island of unit height, which then moves deterministically.
- deterministic part: each island spread with unit speed and whenever two islands meed, they simply merge.
The red line of the upper display represents the one-dimensional growing one-dimensional, where the vertical axis is the height coordinate. The surface height at a fixed time do not contains anymore the complete information on the nucleations, because when two islands merge information is lost. To avoid this, we memorize the merging by considering that there is a nucleation in a second line (the first blue one). This is repeated recursively and when islands of the n-th line merges, a nucleation in the (n+1)-th line is added. In this way we obtain the so-called multiline PNG. It contains all the information of the nucleations occurred in the past, so that from the lines it is possible to run the algorithm backwards too (which would not be possible from the knowledge of the only red line). The construction of the multilines is also called RSK construction. For the PNG model was first used in the paper Scale invariance of the PNG Droplet and the Airy Process by Prähofer and Spohn.
For more information on the PNG model and the RSK construction, see the also our paper Polynuclear growth on a flat substrate and edge scaling of GOE eigenvalues in Publications, and references therein.
The source code is also available.