Hostname: page-component-7b7567c8c-2n9c9 Total loading time: 0 Render date: 2026-11-16T17:57:47.014Z Has data issue: false hasContentIssue false

Mallows permutations as stable matchings

Published online by Cambridge University Press:  27 July 2020

Omer Angel
Affiliation:
University of British Columbia, Vancouver, Canada and University of Bristol, Bristol, United Kingdom e-mail: angel@math.ubc.ca a.e.holroyd@bristol.ac.uk
Alexander E. Holroyd
Affiliation:
University of British Columbia, Vancouver, Canada and University of Bristol, Bristol, United Kingdom e-mail: angel@math.ubc.ca a.e.holroyd@bristol.ac.uk
Tom Hutchcroft*
Affiliation:
University of Cambridge, Cambridge, United Kingdom
Avi Levy
Affiliation:
Microsoft Corporation, Redmond, United States e-mail: avi.levy@microsoft.com
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We show that the Mallows measure on permutations of $1,\dots ,n$ arises as the law of the unique Gale–Shapley stable matching of the random bipartite graph with vertex set conditioned to be perfect, where preferences arise from the natural total ordering of the vertices of each gender but are restricted to the (random) edges of the graph. We extend this correspondence to infinite intervals, for which the situation is more intricate. We prove that almost surely, every stable matching of the random bipartite graph obtained by performing Bernoulli percolation on the complete bipartite graph $K_{{\mathbb Z},{\mathbb Z}}$ falls into one of two classes: a countable family $(\sigma _n)_{n\in {\mathbb Z}}$ of tame stable matchings, in which the length of the longest edge crossing k is $O(\log |k|)$ as $k\to \pm \infty $, and an uncountable family of wild stable matchings, in which this length is $\exp \Omega (k)$ as $k\to +\infty $. The tame stable matching $\sigma _n$ has the law of the Mallows permutation of ${\mathbb Z}$ (as constructed by Gnedin and Olshanski) composed with the shift $k\mapsto k+n$. The permutation $\sigma _{n+1}$ dominates $\sigma _{n}$ pointwise, and the two permutations are related by a shift along a random strictly increasing sequence.

Information

Type
Article
Creative Commons
Creative Common License - CCCreative Common License - BY
This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted re-use, distribution, and reproduction in any medium, provided the original work is properly cited.
Copyright
© Canadian Mathematical Society 2020