## 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*) ≪*n*^{2}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*-*i*≪*m*/*n*, and*m*≪*n*^{2}/log^{2}*n*, then lim_{n→∞}**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*S*. Thus, knowledge of the local structure of_{k}**σ**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 language | English |
---|---|

Number of pages | 17 |

Journal | Discrete Analysis |

Publication status | Submitted - 20 Aug 2019 |

## Keywords

- permutations
- inversions