Permutations with few inversions are locally uniform

Abstract

We prove that permutations with few inversions exhibit a local-global dichotomy in the following sense. Suppose $\mathbf{\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 $\mathbf{\sigma }(i)<\mathbf{\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}[\mathbf{\sigma }(i)<\mathbf{\sigma }(j)]=\frac{1}{2}$. Moreover, if $k=k(n)\ll \sqrt{m/n}$, then the restriction of $\mathbf{\sigma }$ to a random $k$-point interval is asymptotically uniformly distributed over ${\mathcal{S}}_k$. Thus, knowledge of the local structure of $\mathbf{\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. As pointed out by a referee, there are flaws in the proofs that do not seem easily rectifiable (see comments on pages 9 and 15). So the results stated above have not been established.

17 pages; there are flaws in the proofs, so the claimed results have not been established

Cited by in corpus (4)

• The feasible region for consecutive patterns of permutations is a cycle polytope
• Triangulations of simplices with vanishing local h-polynomial
• Splitting groups with cubic Cayley graphs of connectivity two
• Asymptotic normality of consecutive patterns in permutations encoded by generating trees with one-dimensional labels