Sorting networks, staircase Young tableaux, and last passage percolation

MaRDI QIDQ2199826zbMATH OpenFDO

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

Publication date 14 September 2020

Published in Séminaire Lotharingien de Combinatoire (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2003.03331, http://www.mat.univie.ac.at/~slc/wpapers/FPSAC2020//3.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

last passage percolationsorting networkoriented swap processstaircase Young tableaux

Mathematics Subject Classification ID

Combinatorial probability (60C05) Combinatorial aspects of representation theory (05E10)

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 $nle6$ after first reformulating it as a purely combinatorial identity, and discuss its relation to the Edelman-Greene correspondence.

Recommendations

• A pattern theorem for random sorting networks
• Sorting probability for large Young diagrams
• The local limit of random sorting networks
• On random shifted standard Young tableaux and 132-avoiding sorting networks
• On random shifted standard Young tableaux and 132-avoiding sorting networks
• The Archimedean limit of random sorting networks
• Random sorting networks: local statistics via random matrix laws
• Random sorting networks
• Percolation on sequences of graphs
• Random subnetworks of random sorting networks

Cites work

• scientific article; zbMATH DE number 1001729 (Why is no real title available?)
• An extension of Schensted's theorem
• Balanced tableaux
• Circular support in random sorting networks
• GOE and \(\text{Airy}_{2\rightarrow 1}\) marginal distribution via symplectic Schur functions
• Growth diagrams, and increasing and decreasing chains in fillings of Ferrers shapes
• Random sorting networks
• The local limit of random sorting networks
• The oriented swap process
• The surprising mathematics of longest increasing subsequences

Cited in

(9)

• A pattern theorem for random sorting networks
• The oriented swap process
• Absorbing time asymptotics in the oriented swap process
• Cutoff profile of ASEP on a segment
• The oriented swap process and last passage percolation
• Random sorting networks: local statistics via random matrix laws
• OrientedSwaps
• The geometric Burge correspondence and the partition function of polymer replicas
• Shift-invariance of the colored TASEP and finishing times of the oriented swap process

This page was built for publication: Sorting networks, staircase Young tableaux, and last passage percolation

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