The oriented swap process and last passage percolation. Issue 4 (20th October 2021)

• Record Type: Journal Article
• Authors: Bisi, Elia; Cunden, Fabio Deelan; Gibbons, Shane; Romik, Dan
• Is Part Of: Random structures & algorithms. Volume 60:Issue 4(2022)
• Page Start: 690
• Page End: 715
• Publication Date: 2021-10-20
• Subjects: Burge correspondence -- Edelman–Greene correspondence -- last passage percolation -- reduced word decomposition -- Robinson–Schensted–Knuth correspondence -- sorting network -- staircase Young tableau -- Tracy–Widom distribution; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.21055
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract: We present new probabilistic and combinatorial identities relating three random processes: the oriented swap process (OSP) on n particles, the corner growth process, and the last passage percolation (LPP) model. We prove one of the probabilistic identities, relating a random vector of LPP 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 OSP, 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. The conjectural identity provides precise finite‐ n and asymptotic predictions on the distribution of the absorbing time of the OSP, thus conditionally solving an open problem posed by Angel, Holroyd, and Romik.