  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_{\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.

Probability