Mallows permutations as stable matchings

DOI10.4153/S0008414X20000590MaRDI QIDQ5021256zbMATH OpenOpenAlexFDO

Authors Omer Angel, A. E. Holroyd, Tom Hutchcroft, Avi Levy

Publication date 12 January 2022

Published in Canadian Journal of Mathematics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

complete bipartite graphinfinite volume limitsMallows permutationstable matching

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Combinatorial probability (60C05)

Abstract: We show that the Mallows measure on permutations of $1,ldots,n$ arises as the law of the unique Gale-Shapley stable matching of the random bipartite graph conditioned to be perfect, where preferences arise from a total ordering of the vertices 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_{mathbbZ,mathbbZ}$ falls into one of two classes: a countable family $(sigm{a}_n{)}_{ninmathbbZ}$ of tame stable matchings, in which the length of the longest edge crossing $k$ is $O(log|k|)$ as $kopminfty$, and an uncountable family of wild stable matchings, in which this length is $expOmega(k)$ as $ko+infty$. The tame stable matching $sigm{a}_n$ has the law of the Mallows permutation of $mathbbZ$ (as constructed by Gnedin and Olshanski) composed with the shift $kmapstok+n$. The permutation $sigm{a}_{n+1}$ dominates $sigm{a}_n$ pointwise, and the two permutations are related by a shift along a random strictly increasing sequence.

Recommendations

• Mallows and generalized Mallows model for matchings
• The ``stable roommates problem with random preferences
• A number of stable matchings in models of the Gale-Shapley type
• On likely solutions of a stable marriage problem
• On random stable matchings: cyclic ones with strict preferences and two-sided ones with partially ordered preferences

Cites work

• q-exchangeability via quasi-invariance
• Analysis of systematic scan Metropolis algorithms using Iwahori-Hecke algebra techniques
• College Admissions and the Stability of Marriage
• Lengths of monotone subsequences in a Mallows permutation
• Limit theorems for longest monotone subsequences in random Mallows permutations
• Mallows permutations and finite dependence
• Mixing times of the biased card shuffling and the asymmetric exclusion process
• Noisy sorting without resampling
• NON-NULL RANKING MODELS. I
• On the cycle structure of Mallows permutations
• Phase uniqueness for the Mallows measure on permutations
• Stochastic domination and comb percolation
• The length of the longest common subsequence of two independent Mallows permutations
• The length of the longest increasing subsequence of a random Mallows permutation
• The TASEP speed process
• The two-sided infinite extension of the Mallows model for random permutations
• Thermodynamic limit for the Mallows model on S_n

Cited in

(10)

• Strongly correlated random interacting processes. Abstracts from the workshop held January 28 -- February 3, 2018
• A central limit theorem for descents of a Mallows permutation and its inverse
• Stationary distributions of the multi-type ASEP
• Mallows permutations and finite dependence
• Limit distributions for Euclidean random permutations
• Cycles in Mallows random permutations
• Logical limit laws for Mallows random permutations
• A central limit theorem on two-sided descents of Mallows distributed elements of finite Coxeter groups
• The global and local limit of the continuous-time Mallows process
• Tangled paths: a random graph model from Mallows permutations

This page was built for publication: Mallows permutations as stable matchings

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