Permutations with few inversions are locally uniform

David Bevan

Published 2019-08-20Version 1

We prove that permutations with few inversions exhibit a local-global dichotomy in the following sense. Suppose ${\boldsymbol\sigma}$ is a permutation chosen uniformly at random from the set of all permutations of $[n]$ with exactly $m=m(n)\ll n^2$ inversions. If $i<j$ are chosen uniformly at random from $[n]$, then ${\boldsymbol\sigma}(i)<{\boldsymbol\sigma}(j)$ asymptotically almost surely. However, if $i$ and $j$ are chosen so that $j-i\ll m/n$, and $m \ll n^2/\log^2 n$, then $\lim_{n\to\infty}\mathbb{P}\big[{\boldsymbol\sigma}(i)<{\boldsymbol\sigma}(j)\big]=\frac{1}{2}$. Moreover, if $k=k(n)\ll \sqrt{m/n}$, then the restriction of ${\boldsymbol\sigma}$ to a random $k$-point interval is asymptotically uniformly distributed over $\mathcal{S}_k$. Thus, knowledge of the local structure of ${\boldsymbol\sigma}$ reveals nothing about its global form. We establish that $\sqrt{m/n}$ is the threshold for local uniformity and $m/n$ the threshold for inversions, and determine the behaviour in the critical windows.