Sorting networks, staircase Young tableaux, and last passage percolation

zbMATH Open1447.05218arXiv2003.03331MaRDI QIDQ2199826FDOQ2199826

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

Publication date: 14 September 2020

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

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.

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

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

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

zbMATH Keywords

last passage percolationsorting networkoriented swap processstaircase Young tableaux

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• 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
• The oriented swap process
• Circular support in random sorting networks
• GOE and \(\text{Airy}_{2\rightarrow 1}\) marginal distribution via symplectic Schur functions

Cited In (7)

• A pattern theorem for random sorting networks
• Absorbing time asymptotics in the oriented swap process
• The oriented swap process and last passage percolation
• Cutoff profile of ASEP on a segment
• 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)