Discrete Geometry and Combinatorics Seminar

Alexander HolroydUniversity of Washington
Mallows permutations and stable marriage

Monday, October 30, 2017 - 2:30pm
Malott 206

The Mallows measure on the symmetric group $S_n$ assigns to each permutation a probability proportional to a parameter $q$ to the power of the inversion number. It was originally introduced in 1957 in the context of statistical ranking theory, and has been used in many areas including statistical physics, learning theory, mixing times, and finite dependence. Gale-Shapley stable marriage is a cornerstone of economic theory as well a mathematical gem. Introduced in 1962, it was the subject of the 2012 Nobel prize in economics, awarded to Roth and Shapley. I'll explain how the two objects are related. In particular, the former is an example of the latter. Among other things this gives a simple and elegant new description of the Mallows measure on the infinite line $\mathbb{Z}$, provided one does not get distracted by "wild matchings"!