The oriented swap process and last passage percolation

DOI10.1002/RSA.21055MaRDI QIDQ6074699zbMATH OpenOpenAlexFDO

Authors Elia Bisi, Fabio Deelan Cunden, Shane Gibbons, Dan Romik

Publication date 12 October 2023

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2005.02043

zbMATH Keywords

last passage percolationTracy-Widom distributionsorting networkEdelman-Greene correspondenceRobinson-Schensted-Knuth correspondenceBurge correspondencereduced word decompositionstaircase Young tableau

Mathematics Subject Classification ID

Interacting random processes; statistical mechanics type models; percolation theory (60K35) Exact enumeration problems, generating functions (05A15) Percolation (82B43)

Abstract: We present new probabilistic and combinatorial 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 $nle6$ 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 oriented swap process, thus conditionally solving an open problem posed by Angel, Holroyd and Romik.

Recommendations

• Sorting networks, staircase Young tableaux, and last passage percolation
• Absorbing time asymptotics in the oriented swap process
• The oriented swap process
• Random sorting networks: local statistics via random matrix laws
• Shift-invariance of the colored TASEP and finishing times of the oriented swap process

Cites work

• scientific article; zbMATH DE number 1001729 (Why is no real title available?)
• scientific article; zbMATH DE number 3861335 (Why is no real title available?)
• scientific article; zbMATH DE number 47598 (Why is no real title available?)
• scientific article; zbMATH DE number 1268810 (Why is no real title available?)
• Algebraic aspects of increasing subsequences
• An extension of Schensted's theorem
• Balanced tableaux
• Circular support in random sorting networks
• Combinatorial aspects of the Lascoux-Schützenberger tree
• Combinatorics of Coxeter Groups
• Fluctuation properties of the TASEP with periodic initial configuration
• Four correspondences between graphs and generalized Young tableaux
• Growth diagrams, and increasing and decreasing chains in fillings of Ferrers shapes
• Log-gases and random matrices.
• On orthogonal and symplectic matrix ensembles
• On the distribution of the largest eigenvalue in principal components analysis
• On the number of reduced decompositions of elements of Coxeter groups
• Permutations, matrices, and generalized Young tableaux
• Point-to-line last passage percolation and the invariant measure of a system of reflecting Brownian motions
• Probability
• Random sorting networks
• Relating Edelman-Greene insertion to the Little map
• Sorting networks, staircase Young tableaux, and last passage percolation
• The asymptotics of monotone subsequences of involutions
• The local limit of random sorting networks
• The oriented swap process
• The surprising mathematics of longest increasing subsequences

Cited in

(3)

• The oriented swap process
• Absorbing time asymptotics in the oriented swap process
• Shift-invariance of the colored TASEP and finishing times of the oriented swap process

This page was built for publication: The oriented swap process and last passage percolation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6074699)