The oriented swap process and last passage percolation

DOI10.1002/RSA.21055zbMATH Open1523.60158arXiv2005.02043OpenAlexW3210483736MaRDI QIDQ6074699FDOQ6074699

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)

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.

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

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

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)

Cites Work

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

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)