Permutations with few inversions are locally uniform

MaRDI QIDQ6323924zbMATH OpenFDO

Authors David Bevan

Publication date 20 August 2019

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Asymptotic enumeration (05A16)

Abstract: We prove that permutations with few inversions exhibit a local-global dichotomy in the following sense. Suppose $$ 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 $$ asymptotically almost surely. However, if $i$ and $j$ are chosen so that $j-illm/n$, and $mll{n}^2/lo{g}^{2}n$, then $$. Moreover, if $k=k(n)llsqrtm/n$, then the restriction of $$ to a random $k$-point interval is asymptotically uniformly distributed over $mathcal{S}_k$. Thus, knowledge of the local structure of $$ reveals nothing about its global form. We establish that $sqrtm/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.

This page was built for publication: Permutations with few inversions are locally uniform

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