Geometry of Permutation Limits

Rahman, Mustazee; Virág, Bálint; Vizer, Máté

Abstract

This paper initiates a limit theory of permutation valued processes, building on the recent theory of permutons. We apply this to study the asymptotic behaviour of random sorting networks. We prove that the Archimedean path, the conjectured limit of random sorting networks, is the unique path from the identity to the reverse permuton having minimal energy in an appropriate metric. Together with a recent large deviations result (Kotowski, 2016), it implies the Archimedean limit for the model of relaxed random sorting networks.

Citation

Rahman, M., Virág, B., & Vizer, M. (2019). Geometry of Permutation Limits. Combinatorica, 39, 933-960. https://doi.org/10.1007/s00493-019-3817-6

• Journal Article Type: Article
• Acceptance Date: Oct 30, 2018
• Online Publication Date: Jul 9, 2019
• Publication Date: 2019-08
• Deposit Date: Sep 25, 2019
• Publicly Available Date: Oct 6, 2021
• Journal: Combinatorica
• Print ISSN: 0209-9683
• Electronic ISSN: 1439-6912
• Publisher: Springer
• Peer Reviewed: Peer Reviewed
• Volume: 39
• Pages: 933-960
• DOI: https://doi.org/10.1007/s00493-019-3817-6
• Public URL: https://durham-repository.worktribe.com/output/1290535