Séminaire Lotharingien de Combinatoire, 84B.3 (2020), 12 pp.
Elia Bisi, Fabio Deelan Cunden, Shane Gibbons and Dan Romik
Sorting Networks, Staircase Young Tableaux, and Last Passage Percolation
Abstract.
We present new combinatorial and probabilistic identities relating
three random processes: the oriented swap process on n particles,
the corner growth process, and the last passage percolation model. We
prove one of the probabilistic identities, relating a random vector of
last passage percolation times to its dual, using the duality between
the Robinson-Schensted-Knuth and Burge correspondences. A second
probabilistic identity, relating those two vectors to a vector of
"last swap times" in the oriented swap process, is conjectural. We
give a computer-assisted proof of this identity for n <= 6 after
first reformulating it as a purely combinatorial identity, and discuss
its relation to the Edelman-Greene correspondence.
Received: November 20, 2019.
Accepted: February 20, 2020.
Final version: April 30, 2020.
The following versions are available: