Permutations with few inversions are locally uniform

Research output: Contribution to journalArticle

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) ≪ n2 inversions. If i < j are chosen uniformly at random from [n], then σ(i) < σ(j) asymptotically almost surely. However, if i and j are chosen so that j - im/n, and mn2/log2n, then limn→∞ P[σ(i) < σ(j)] = ½. Moreover, if k = k(n) ≪ √(m/n), then the restriction of σ to a random k-point interval is asymptotically uniformly distributed over Sk. Thus, knowledge of the local structure of σ reveals nothing about its global form. We establish that √(m/n) is the threshold for local uniformity and m/n the threshold for inversions, and determine the behaviour in the critical windows.
Original languageEnglish
Number of pages17
JournalDiscrete Analysis
Publication statusSubmitted - 20 Aug 2019

Keywords

  • permutations
  • inversions

Fingerprint Dive into the research topics of 'Permutations with few inversions are locally uniform'. Together they form a unique fingerprint.

  • Cite this

    Bevan, D. (2019). Permutations with few inversions are locally uniform. Manuscript submitted for publication.